Câu hỏi:
11/07/2024 982a) 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?
Sá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:
a) Một chu trình Euler của đồ thị G là: AB, a, b, BC, CD, DE, EA.
Ta có d(A) = 2; d(B) = 4; d(C) = 2; d(D) = 2; d(E) = 4.
Vậy đồ thị đã cho không có đỉnh nào là đỉnh bậc lẻ.
b) Đồ thị S không có chu trình Euler vì nếu một đường đi bắt đầu và kết thúc tại cùng một đỉnh thì cạnh CD bắt buộc phải đi qua ít nhất hai lần; nếu một đường đi bắt đầu tại đỉnh này và kết thúc tại đỉnh kia thì không được gọi là chu trình.
Tương tự như vậy, đồ thị T không có chu trình Euler.
Đồ thị S có: d(A) = 2; d(B) = 2; d(C) = 3; d(D) = 1. Suy ra đồ thị S có hai đỉnh bậc lẻ là C, D.
Đồ thị T có: d(A) = 3; d(B) = 2; d(C) = 3; d(D) = 2. Suy ra đồ thị T có hai đỉnh bậc lẻ là A, C.
Vậy cả hai đồ thị S và T đều có đỉnh bậc lẻ.
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 4:
Đồ 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 6:
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.
về câu hỏi!