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

Một cây có 14 cạnh. Nó có bao nhiêu đỉnh |V|?

Đúng một đỉnh của đồ thị có bậc 1. Hãy nhấp vào nó.

1. 1A
2. 2B
3. 3C
4. 4D
5. 5E

Đồ thị đầy đủ K₈ có bao nhiêu chu trình Hamilton khác nhau H? Các chu trình chỉ khác nhau ở đỉnh xuất phát hoặc chiều đi được tính là một.

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

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 4; 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ố.