Hoạt động 7

Quan sát đồ thị ở Hình 10 và đường đi CABDCB, cho biết:

﷽a) Đường đi trên có đi qua tất cả các cạnh của đồ thị hay không?

b) Đường đi trên đi qua mỗi cạnh bao nhiêu lần? 

Phương pháp giải:

Lời giải chi tiết:

Quan sát đồ thị ở Hình 10 ta thấy:

🧸a) Đường đi CABDCB đi qua tất cả các cạnh của đồ thị.

b) Đường đi trên đi qua mỗi cạnh đúng một lần.

Luyện tập 7

Hãy chỉ ra hai đường đi Euler trong đồ thị ở Hình 11a.

Phương pháp giải:

Lời giải chi tiết:

Hình 11a💙 có đường đi Euler BEDBADCA và đường đi Euler BEDCADBA.

Luyện tập 8

Chứng minh rằng đồ thị ở Hình 11a không có chu trình Euler.

Phương pháp giải:

Lời giải chi tiết:

Ta có d(A) = 3, d(B) = 3 nên đồ thị ở Hình 11a có đỉnh bậc lẻ, do đó theo định lí Euler, đồ thị ở Hình 11a không có chu trình Euler.

Hoạt động 8

Quan sát đường đi màu đỏ trên đồ thị ở Hình 13🦩 và cho biết đường đi đó có đi qua tất cả các đỉnh của đồ thị hay không và mỗi đỉnh đi qua bao nhiêu lần.

Phương pháp giải:

Lời giải chi tiết:

Quan sát đường đi màu đỏ trên đồ thị ở Hình 13ꦕ ta thấy đường đi đó đi qua tất cả các đỉnh của đồ thị hay và mỗi đỉnh đi qua đúng một lần.

Luyện tập 9

 Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15.

Phương pháp giải:

Lời giải chi tiết:

Quan sát đồ thị Hình 15ও, ta thấy rằng hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị này là EACDB và ECDBA.

Luyện tập 10

Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton. 

Phương pháp giải:

Lời giải chi tiết:

Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17꧋ gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn \(\frac{5}{2}\) . Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.

Luyện tập 11

Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.

Phương pháp giải:

Lời giải chi tiết:

Đồ thị G ở Hình 19 ☂gồm 6 đỉnh, trong đó các đỉnh A, D, E có bậc 4, các đỉnh B, C có bậc 5 và đỉnh F có bậc 2 nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 6. Do đó, theo định lí Ore, đồ thị G có ít nhất một chu trình Hamilton.