Trang chủ Lớp 11 Toán lớp 11 Chuyên đề học tập Toán 11 - Chân trời sáng tạo Thực hành 1 Bài 2 (trang 50, 51, 52, 53, 54) Chuyên...

Thực hành 1 Bài 2 (trang 50, 51, 52, 53, 54) Chuyên đề học tập Toán 11: 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

Giải Thực hành 1 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. Tham khảo: Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả.

Câu hỏi/Đề bài:

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.

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.

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ẻ.