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

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

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

Một cây có 2 đỉnh bậc 4, 4 đỉ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?

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

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

Thuật toán Kruskal xây dựng một cây khung nhỏ nhất. Hãy nhấp vào cạnh mà nó thêm vào là cạnh số 5; các cạnh bị bỏ qua không được tính.

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