Bài 11: Đồ thị `Hamilton`

Tham khảo Video sau đây :

1.Định nghĩa

Đường đi Hamilton là đường đi qua tất cả các đỉnh trong đồ thị, mỗi đỉnh đúng 1 lần
Chu trình Hamilton là đường đi hamilton đi bắt đầu từ 1 đỉnh và trở lại đúng đỉnh đó

💡 GHI NHỚ

⚠️ LƯU Ý

Cho đến nay, vẫn chưa tìm ra được điều kiện cần và đủ để tồn tại chu trình Hamilton

Các kết quả thu được phần lớn là các điều kiện đủ để một đồ thị Hamilton là có dạng "nếu G có số cạnh đủ lớn thì G là Hamilton"

💡 Đồ thị không phải Hamilton

Đồ thị có đỉnh treo không thể tạo ra chu trình Hamilton
Nếu một định có bậc 2 thì cả 2 cạnh liên thuộc với đỉnh này phải là một phần của chu trình Hamilton

⚠️ LƯU Ý

Chu trình Hamilton không thể chứa chu trình nhỏ hơn trong nó

Một đơn đồ thị vô hướng G=(V, E) với n đỉnh (n >= 3) có chu trình Hamilton nếu

deg(v) ≥ n/2 với ∀v ∈ V

Đồ thị vô hướng G=(V, E) với |V| ≥ 3 có chu trình Hamilton khi :

với ∀(u,v) ∉ E => deg(u) + deg(v) ≥ n

⚠️ LƯU Ý

Cả 2 định lý trên đều chỉ là điều kiện đủ để một đơn đồ thị liên thông có tồn tại chu trình Hamilton => không phải là điều kiện cần

==> Tồn tại một số đồ thị không thoả 2 định lý trên

==> Nếu thoả thì chắc chắn nó là Hamilton còn nếu không thoả thì không kết luận được gì

Tham khảo Video sau đây :