Câu hỏi trong đề:
Chuyên đề Toán 11 CTST Chuyên đề 2. Lí thuyết đồ thị có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
⦁ Hình 21a:
Đồ thị ở Hình 21a có các đỉnh A, F có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh AB, AD, FD, FC trong đồ thị ở Hình 21a.
Do đó h không thể đi qua các cạnh BD, DC.
Nếu xóa đi hai cạnh này thì đỉnh B, C trở thành có bậc 2.
Vì vậy h phải đi qua cạnh BC.
Khi đó ta được chu trình Hamilton h: ADFCBA.
⦁ Hình 21b:
Đồ thị ở Hình 21b có các đỉnh F, I có bậc 2.
Suy ra chu trình Hamilton h (nếu có) phải đi qua các cạnh FE, FB, IA, IC.
Do đó ta được chu trình Hamilton h: AICBFEDA (hoặc AICDEFBA).
Vậy cả hai đồ thị đã cho đều có chu trình Hamilton.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.
Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.
Xem đáp án »
13/07/2024
2,588
Câu 2:
Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Xem đáp án »
13/07/2024
1,044
Câu 3:
a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?
b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?
a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?
b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?
Xem đáp án »
11/07/2024
1,013
Câu 5:
Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy.
Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy.
Xem đáp án »
13/07/2024
985
Câu 7:
Mỗi đồ thị trong Hình 23 có chu trình Euler không? Nếu có hãy chỉ ra một chu trình như vậy.
Mỗi đồ thị trong Hình 23 có chu trình Euler không? Nếu có hãy chỉ ra một chu trình như vậy.
Xem đáp án »
12/07/2024
872
về câu hỏi!