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

Đồ thị hai phần đầy đủ K_4,9 có bao nhiêu cạnh |E|?

Đồ thị đầy đủ K₁₂ có bao nhiêu cạnh |E|?

Một đồ thị liên thông có 10 đỉnh và 11 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ó 2 đỉnh bậc 4, 3 đỉnh bậc 5, 2 đỉ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 Dijkstra chạy từ A. Hãy nhấp vào đỉnh được chốt (trở thành cố định) ở vòng 3; bản thân A là vòng 1.

1. 1A
2. 2B
3. 3C
4. 4D
5. 5E
6. 6F
7. 7G

Hãy dùng thuật toán Dijkstra để tìm độ dài d(F) của đường đi ngắn nhất từ A đến F trong đồ thị có trọng số.