Câu hỏi:
13/07/2024 672Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 140k).
Quảng cáo
Trả lời:
Lời giải:
Vì đồ thị Hình 2.35 là liên thông và các đỉnh đều có bậc chẵn (ở đây chỉ có đỉnh A và đỉnh F có bậc là 2, các đỉnh còn lại đều có bậc 4) nên đồ thị này có chu trình Euler.
Một chu trình Euler xuất phát từ đỉnh A là ABCDBEDFECA và tổng độ dài của nó là
3 + 5 + 8 + 6 + 4 + 2 + 3 + 9 + 7 + 4 = 51.
Vậy một chu trình cần tìm là ABCDBEDFECA và có độ dài là 51.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Câu 2:
Câu 3:
Câu 4:
Câu 5:
Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.
a) Hãy chỉ ra 2 đường đi từ A đến F và so sánh độ dài của hai đường đi đó.
b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C.
về câu hỏi!