Khác biệt giữa bản sửa đổi của “Đường đi Hamilton”

Các kết quả có được hiện nay chỉ là các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có dây chuyền Hamilton.

* Đồ thị đủ luôn là đồ thị Hamilton. Với n lẻ và n ≥ 3 thì Kn có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung.

* Giả sử G là đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3. Nếu d(x) ≥ n/2 với mọi đỉnh x của G thì G là đồ thị Hamilton.

* Giả sử G là đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3. Nếu d(x) ≥ (n-1)/2 với mọi đỉnh x của G thì G có dây chuyền Hamilton.

* Giả sử G là đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3. Nếu d(x) + d(y) ≥ n với mọi cặp đỉnh x,y không kề nhau của G thì G là đồ thị Hamilton.

 

==Định lý==

* '''Ore''' (1960) Một đồ thị có n đỉnh (n > 2) là Hamilton nếu tổng các bậc của hai đỉnh không kề nhau đều bằng n hoặc lớn hơn.

* '''Định lý Bondy-Chvátal'''(1972) Một đồ thị là Hamilton nếu và chỉ nếu bao đóng của nó là Hamilton. Vì đồ thi đầy đủ là Hamilton, nên tất cả các đồ thị mà bao đóng đầy đủ là Hamilton.

*Giả sử '''G=(X,E)''' là [[đồ thị vô hướng]] gồm n đỉnh với tập đỉnh '''X={x₁,x₂,...,x_n}''', nếu G là đồ thị Hamilton thì sẽ có chu trình Hamilton có dạng: '''x₁--x_i1--x_i2--x_i3... x_{i n-1}--x₁''',với '''{i₁,i₂,...,i_n-1}''' là một hoán vị của tập hợp '''{2,3,...,n}'''

==> Từ đó, ta có một thuật toán hiển nhiên là: Đặt '''Z={x_i1, x_i2, x_i3,…}''' là dãy đỉnh tương ứng

 

==> Đây là một [[thuật toán vét cạn]], có độ phức tạp không khả thi khi n chỉ từ 20,30 đỉnh trở lên.