Phiếu bài tập Lý thuyết đồ thị có đáp án

Một đồ thị đơn có 7 đỉnh với các bậc 3, 3, 2, 2, 2, 2, 2. Nó có bao nhiêu cạnh |E|?

Một đồ thị 2-đều có 8 đỉnh (mỗi đỉnh có bậc 2). Nó có bao nhiêu cạnh |E|?

Một đồ thị liên thông có 18 đỉnh và 18 cạnh. Phải bỏ bao nhiêu cạnh k để còn lại một cây khung?

Một cây có 3 đỉnh bậc 4, 3 đỉnh bậc 5, 3 đỉnh bậc 2, và mọi đỉnh khác của nó đều là lá (bậc 1). Nó có bao nhiêu lá L?

Thuật toán Prim xây dựng một cây khung nhỏ nhất bắt đầu từ đỉnh D. Hãy nhấp vào cạnh mà nó thêm vào là cạnh số 4.

1. 1cạnh AB
2. 2cạnh AC
3. 3cạnh CE
4. 4cạnh DE
5. 5cạnh DF
6. 6cạnh EF
7. 7cạnh GB
8. 8cạnh GD
9. 9cạnh GE

Có bao nhiêu đường đi độ dài 3 từ B đến A? Một đường đi có thể lặp lại đỉnh và cạnh. Gọi số đó là N.