Cho đồ thị G liên thông có 5 đỉnh. Hỏi cây khung của G có mấy cạnh, mấy đỉnh?
Đáp án đúng: B
Câu hỏi liên quan
* Kiểm tra phương án A: an = 4n + 1.
- Với n = 1, a1 = 4(1) + 1 = 5. Đúng.
- Với n = 2, a2 = 4(2) + 1 = 9. Đúng.
- Với n = 3, a3 = 4(3) + 1 = 13. Đúng.
Công thức này phù hợp với các số hạng đầu của dãy.
* Kiểm tra phương án B: an = 4n + 3.
- Với n = 1, a1 = 4(1) + 3 = 7. Sai. (Số hạng đầu tiên phải là 5)
* Kiểm tra phương án C: an = 4n - 1.
- Với n = 1, a1 = 4(1) - 1 = 3. Sai. (Số hạng đầu tiên phải là 5)
Vậy, công thức truy hồi đúng là an = 4n + 1.
Trong trường hợp này:
- Đỉnh 1 kề với 4 và 6.
- Đỉnh 2 kề với 5 và 6.
- Đỉnh 3 kề với 4, 5 và 6.
Giả sử tô đỉnh 1 màu Xanh. Vậy đỉnh 4 và 6 phải màu Đỏ.
Vì đỉnh 6 màu Đỏ, nên đỉnh 2 phải màu Xanh. Vậy đỉnh 5 phải màu Đỏ.
Vì đỉnh 4 màu Đỏ, nên đỉnh 3 phải màu Xanh.
Nhưng đỉnh 3 và 5 kề nhau và đều màu Đỏ. Điều này vi phạm quy tắc tô màu của đồ thị hai phía. Do đó, đồ thị này không phải là đồ thị hai phía.
Vậy đáp án đúng là B.
Sắp xếp topo là một thứ tự tuyến tính của các đỉnh trong đồ thị có hướng không chu trình (DAG) sao cho với mọi cung (u, v) trong đồ thị, đỉnh u đứng trước đỉnh v trong thứ tự đó. Một đồ thị có chu trình thì không có thứ tự topo.
Để tìm thứ tự topo của đồ thị đã cho, ta có thể sử dụng thuật toán duyệt đồ thị theo chiều sâu (DFS) kết hợp với việc đánh dấu các đỉnh đã được thăm và các đỉnh đã hoàn thành.
Trong đồ thị G = (V, E) với V = {1, 2, 3, 4, 5, 6} và E = {(1, 6), (2, 1), (2, 5), (2, 6), (3, 1), (3, 2), (5, 4), (5, 6), (6, 4)}:
- Đỉnh 3 không có cung vào, có thể là đỉnh bắt đầu.
- Từ 3 có các cung đến 1 và 2.
- Từ 2 có các cung đến 1, 5, 6.
- Từ 1 có cung đến 6.
- Từ 5 có các cung đến 4 và 6.
- Từ 6 có cung đến 4.
Duyệt theo DFS:
- Bắt đầu từ đỉnh 3.
- Thăm 3, sau đó thăm 1 (vì 3 -> 1).
- Thăm 1, sau đó thăm 6 (vì 1 -> 6).
- Thăm 6, sau đó thăm 4 (vì 6 -> 4).
- Thăm 4 (đã hoàn thành).
- Quay lại 6 (đã hoàn thành).
- Quay lại 1 (đã hoàn thành).
- Quay lại 3, thăm 2 (vì 3 -> 2).
- Thăm 2, sau đó thăm 5 (vì 2 -> 5).
- Thăm 5, sau đó thăm 4 (đã thăm rồi) và 6 (đã thăm rồi).
- 5 hoàn thành.
- 2 hoàn thành.
- 3 hoàn thành.
Như vậy, một thứ tự topo hợp lệ là: 3, 2, 1, 5, 6, 4.
trên X.
