Chu trình Hamilton

Gọi mỗi hình máy bay là một điểm trên mặt phẳng, vậy hình vẽ trên có phải là chu trình Hamilton không?

(a)  

Đồ thị nào có một chu trình Hamilton hay không?

• A,B,C

• B,C,D

• A,C,D

• A,B,C,D

Answer explanation

Hình a) có chu trình Hamilton là ABCDA.

Hình b) có chu trình Hamilton là ABCDEA.

Hình c) có một chu trình Hamilton là ABCDHGFEA.

Hình d) không có chu trình Hamilton vì có đỉnh A, B là đỉnh bậc 3.

 Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R.

(a)  

Bài 7: Chỉ ra một đường đi Hamilton ở hình sau, biết rằng đường đi xuất phát từ E đến D rồi kết thúc ở P

(a)  

Các đỉnh của đồ thị ở hình sau biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?

•  ABCDFEIKA

• BDIKFEACB

• DEFIKABCD

Khái niệm về đường đi và chu trình Hamilton được đưa ra bởi William Rowan Hamilton vào năm

• 1869

• 1859

• 1996

• 1969

Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15. (Nhiều lựa chọn)

• EACDB

• ECDBA

• EBDCA

• EDBCA

Hãy vẽ một đồ thị có bốn đỉnh sao cho chỉ có đúng hai đỉnh cùng có bậc là 1

Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21.

(a)  

Hình 19 có phải là chu trình Hamilton không

(a)