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
Dòng 60:
*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
==> Đâ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.
| |||