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

Đú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
6. 6F

Đúng một đỉnh của đồ thị có bậc 3. 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 cây có 3 đỉnh bậc 3, 4 đỉnh bậc 4, 4 đỉnh bậc 5, và mọi đỉnh khác của nó đều là lá (bậc 1). Nó có bao nhiêu lá L?

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

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