Câu hỏi:
23/07/2023 582Mỗ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.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
⦁ Đồ thị G:
Ta có d(A) = d(B) = d(C) = d(D) = 4.
Suy ra đồ thị G có tất cả các đỉnh đều có bậc chẵn.
Vậy đồ thị G có chu trình Euler.
Chẳng hạn, ta có chu trình Euler: AabACDBcdBA.
⦁ Đồ thị H:
Ta có d(A) = d(B) = d(E) = 4; d(C) = d(D) = 3.
Suy ra đồ thị H có hai đỉnh C, D có bậc lẻ.
Vậy đồ thị H không có chu trình Euler.
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.
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.
Câu 3:
Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy.
Câu 5:
Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?
Câu 6:
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?
về câu hỏi!