Khác biệt giữa bản sửa đổi của “Đường đi Hamilton”
Nội dung được xóa Nội dung được thêm vào
sửa thôi |
Đồ thị có là Halminton hay không hoàn toàn có thể xác định được bằng thuật toán tìm kiếm chiều sâu |
||
Dòng 50:
Đồ thị đủ luồn là đồ thị Hamilton, với n lẻ ≥ 3 thì Kn(Kn là đồ thị đủ với n đỉnh) có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung.
==Thuật toán xác định đồ thị Hamilton==
*Giả sử '''G=(X,E)''' là [[đồ thị vô hướng]] gồm n đỉnh với tập đỉnh '''X={x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>}''', nếu G là đồ thị Hamilton thì sẽ có chu trình Hamilton có dạng: '''x<sub>1</sub>--x<sub>i1</sub>--x<sub>i2</sub>--x<sub>i3</sub>... x<sub>i n-1</sub>--x<sub>1</sub>''',với '''{i<sub>1</sub>,i<sub>2</sub>,...,i<sub>n-1</sub>}''' 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<sub>i1</sub>, x<sub>i2</sub>, x<sub>i3</sub>,…}''' là dãy đỉnh tương ứng
| |||