Trả lời Khám phá 3 Bài 2. Đường đi Euler và đường đi Hamilton (trang 50, 51, 52, 53, 54) – Chuyên đề học tập Toán 11 Chân trời sáng tạo. Gợi ý: Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất.
Câu hỏi/Đề bài:
Hãy chỉ ra một đường đi Euler trên mỗi đồ thị sau. Mỗi đồ thị có bao nhiêu đỉnh bậc lẻ?
Hướng dẫn:
– Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
– Đỉnh có bậc là số chẵn gọi là đỉnh bậc chẵn, đỉnh có bậc là một số lẻ là đỉnh bậc lẻ.
Lời giải:
Một đường đi Euler (từ A đến D) trên đồ thị G là: ACBDAD.
Một đường đi Euler (từ E đến F) trên đồ thị H là: EABFCDEF.
Đồ thị G có: d(A) = 3; d(B) = 2; d(C) = 2; d(D) = 3.Suy ra đồ thị G có hai đỉnh bậc lẻ là A, D.
Đồ thị H có: d(A) = 2; d(B) = 2; d(C) = 2; d(D) = 2; d(E) = 3; d(F) = 3.Suy ra đồ thị H có hai đỉnh bậc lẻ là E, F.
Vậy đồ thị G có 2 đỉnh bậc lẻ, đồ thị H có 2 đỉnh bậc lẻ.