Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy

Giải Chuyên đề Toán 11 Chân trời sáng tạo Bài 2: Đường đi Euler và đường đi Hamilton

Thực hành 2 trang 54 Chuyên đề Toán 11: Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.

Lời giải:

Ta có d(A) = d(B) = d(C) = d(D) = 4 và d(E) = d(F) = 3.

Suy ra đồ thị H có đúng 2 đỉnh bậc lẻ là E, F.

Do đó đồ thị H có đường đi Euler.

Chẳng hạn, bắt đầu từ đỉnh E, ta có thể đi theo đường đi Euler: EAabADcdDFCBEF.

Lời giải:

a) Đồ thị G:

Ta có d(A) = d(B) = d(C) = d(D) = d(E) = 4.

Vậy đồ thị G có chu trình Euler vì các đỉnh của đồ thị G đều có bậc chẵn.

Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo chu trình Euler: ABECAEDCBDA.

b) Đồ thị H:

Ta có d(A) = d(D) = 4; d(B) = d(C) = 3; d(E) = 2.

Vậy đồ thị H không có chu trình Euler vì hai đỉnh B, C có bậc lẻ.