Trắc nghiệm về Đường đi Hamilton

Định nghĩa nào dưới đây mô tả đúng nhất về đường đi Hamilton?

• Một đường đi trong đồ thị đi qua mỗi đỉnh đúng một lần

• Một chu trình đi qua mỗi cạnh đúng một lần

• Một đường đi đi qua tất cả các cạnh ít nhất một lần

• Một chu trình có số đỉnh chẵn

Chu trình Hamilton là gì?

• Một đường đi đi qua tất cả các cạnh đúng một lần

• Một chu trình đi qua mỗi đỉnh đúng một lần rồi quay lại đỉnh xuất phát

• Một đồ thị vô hướng có ít nhất một cạnh

• Một đồ thị liên thông

Đồ thị Hamilton : Một thị được gọi là đồ thị Hamilton nếu nó có chứa …………….nhất………..chu trình Hamilton.

• ít/một

• nhiều /2

• ít / hai

• tối đa /2

Đường đi và chu trình Hamilton đi qua mỗi cạnh của đồ thị nhiều nhất …. lần

• 1

• 2

• Không biết

• vô số

Từ chu trình Hamilton, bỏ đi cạnh cuối cùng, ta được……………..

• chu trình euler

• đường đi euler

• đường đi Hamilton

• đường đi Hanilton

Định lý Dirac đảm bảo một đồ thị có chu trình Hamilton nếu:

• Đồ thị có ít nhất một chu trình

• Đồ thị có số cạnh lớn hơn số đỉnh

• Mọi đỉnh có bậc ≥ n/2

• Đồ thị có ít nhất một đường đi Euler

Định lý Ore mở rộng định lý Dirac bằng cách yêu cầu:

• Tổng bậc của mọi cặp đỉnh không kề nhau ≥ n

• Mọi đỉnh có bậc ≥ n/3

• Đồ thị có đường đi Euler

• Đồ thị là đồ thị đầy đủ

Điều kiện đủ để có chu trình Hamilton: Đồ thị liên thông G có n đỉnh……… Nếu mọi đỉnh của G bậc lớn hơn hoặc bằng n2 thì đồ thị G có chu trình Hamilton.

• (n<1).

• (n≥3)

• (n≤3).

• (n≥2).

Nhận biết đường đi Hamilton Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.

• CEDAA

• EABCD

• ABCEE

• ABDEB

Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G.

• SUKTRNHOMR

• SUKTRNHTMS

• SUOTRNHOMS

• SUKTRNHOMS