|
Trong [[toán học]], ngành [[lý thuyết đồ thị]], một '''Đườngđường đi Hamilton''' cólà nguồnmột gốc[[đường từđi bàitrong toán:đồ "Xuấtthị|đường phátđi]] từ một đỉnh củatrong [[khốiđồ thậpthị nhịvô diện đềuhướng]] hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh kháccủa đồ thị, mỗi đỉnh đúng một lần. sauMột đó'''Chu quaytrình vềHamilton''' đỉnhlà xuấtmột phát."đường làđi gọiHamilton theosau tênđi qua tất cả các đỉnh của [[Williamđồ Rowanthị Hamilton]]thì pháttrở biểuvề vàođỉnh nămxuất 1859phát.
Một đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton, đồ thị có đường đi Hamilton được gọi là đồ thị nửa Hamilton.
[[Tập tin:Dodecahedron.gif|lớn|khung|300px|giữa|Khối thập nhị diện đều]]
'''- Đường đi Hamilton (Đáp án bài toán Hamilton ở trên)'''
[[Tập tin:220px-Hamiltonian path.png |lớn|khung|300px|giữa|Đường đi Hamilton]]
==Định nghĩa==
Cho đồ thị G = (V,E), có n đỉnh
Bài toán tìm đường đi và chu trình như vậy được gọi là bài toán Hamilton. Bài toán Hamilton là NP đầy đủ.
'''Đường đi''' x<sub>0</sub>,x<sub>1</sub>,... ,x<sub>n-1</sub>,x<sub>n</sub> là '''đường đi Hamilton''' nếu
V = {x<sub>0</sub>,x<sub>1</sub>,... ,x<sub>n-1</sub>,x<sub>n</sub>}
x<sub>i</sub>!=x<sub>j</sub>
, 0 ≤ i < j ≤ n
Tên gọi đường đi và chu trình Hamilton là gọi theo tên của [[William Rowan Hamilton]] .
'''Chu trình''' x<sub>0</sub>,x<sub>1</sub>,... ,x<sub>n</sub>,x<sub>0</sub> là '''chu trình Hamilton''' nếu x<sub>0</sub>,x<sub>1</sub>,...,x<sub>n</sub>,x<sub>0</sub>
là đường đi Hamilton
==Các ví dụ==
[[Tập tin:Haminton2.JPG|nhỏ|250px|phải|Đường đi của quân mã trên bàn cờ 3×4 là đường Hamilton.]]
[[Tập tin:Haminton.JPG|nhỏ|250px|phải|Các đồ thị Hamilton]]
*'''Dây chuyền Hamilton''' là dây chuyền đi qua các đỉnh của đồ thị và đi qua mỗi đỉnh đúng 1 lần.
*'''Chu trình Hamilton''' là dây chuyền Hamilton xuất phát từ một đỉnh, đi qua tất cả các đỉnh khác của đồ thị, mỗi đỉnh đúng một lần và quay trở về nơi xuất phát.
*'''Đồ thị Hamilton''' là đồ thị có chứa ít nhất một chu trình Hamilton.
==Ví dụ==
*Một [[đồ thị đầy đủ]] có nhiều hơn hai đỉnh là đồ thị Hamilton.
*Mọi [[đồ thị vòng]] là Hamilton.
*Đồ thị khối ba chiều là đồ thị Hamilton<ref>[http://mathworld.wolfram.com/HamiltonianGraph.html Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957]
</ref>.
[[Tập tin:Vidu.jpg |lớn|400x|giữa|Ví dụ]]
*(G1) Là đồ thị Hamilton (nên đương nhiên có chu trình và dây chuyền Hamilton).
*(G2) Chỉ có dây chuyền Hamilton nên không phải là đồ thị Hamilton ( và được gọi là đồ thị nữa Hamilton).
*(G3) Không có dây chuyền lẫn chu trình Hamilton nên không phải là đồ thị Hamilton.
- '''Một vài ví dụ về đồ thị Hamilton'''
[[Tập tin:Vidu new.png |nhỏ|khung|200x|giữa|Ví dụ đồ thị Hamilton]]
== Định lý Bondy-Chvátal==
==Một số kết quả liên quan đến đồ thị Hamilton==
Không giống như đồ thị Euler, hiện nay chưa có quy tắc cần và đủ để kiểm tra xem một đồ thị có là Hamilton không.
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ị phân đôi với hai tập đỉnh X1, X2 và |X1| = |X2| = n. 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/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.
* Giả sử G là đồ thị vô hướng đơn gồm n đỉnh và m cạnh. Nếu m ≥ <math>(n^2-3n+6)/2</math> thì G là đồ thị Hamilton.
Cho đồ thị ''G'' có ''n'' đỉnh, '''bao đóng ''' cl(''G'') được tạo ra từ ''G'' bằng cách bổ sung cho mỗi cặp đỉnh không kề nhau ''u'' và ''v'' với degree(v) + degree(u) ≥ n một cạnh mới ''uv''.
==Định lý==
* Cho đồ thị ''G'' có ''n'' đỉnh, '''bao đóng ''' cl(''G'') được tạo ra từ ''G'' bằng cách bổ sung cho mỗi cặp đỉnh không kề nhau ''u'' và ''v'' với degree(v) + degree(u) ≥ n một cạnh mới ''uv''.
'''Định lý Bondy-Chvátal''' (1972)
* '''Dirac''' (1952) Xét G là đơn đồ thị vô hướngvới n đỉnh (n ≥ 3). Nếu d(x) ≥ n/2 với mọi đỉnh x của G thì G là đồ thị Hamilton.
:Một đồ thị là Hamilton nếu và chỉ nếu bao đóng của nó là Hamilton.
* '''Ore''' (1960) MộtVì đồ thịthi cóđầy n đỉnh (n > 2)đủ là Hamilton, nếunên tổngtất cả các bậcđồ củathị haimà đỉnhbao khôngđóng kềlà nhauđầy đềuđủ bằnglà n hoặc lớn hơnHamilton.
'''Dirac''' (1952)
* '''Đị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.
:Một đơn đồ thị ''n'' đỉnh (''n'' > 2) là Hamilton nếu mọi đỉnh của nó có bậc không nhỏ hơn ''n''/2.
'''Ore''' (1960)
* '''Ghouila-Houiri''' (1960) Một đồ thị liên thông mạnh với n đỉnh là đồ thị Hamilton nếu mọi đỉnh có bậc ≥ n
: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.
* '''Meyniel'''(1973) Một đồ thị liên thông mạnh với n đỉnh là đồ thị Hamilton nếu d(x)+d(y) ≥ 2n-1 với mọi cặp đỉnh x,y không kề nhau.
Đồ 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==
*Hiện nay '''chưa có''' các qui tắc cần và đủ để kiểm tra xem một [[đồ thị]] có là Hamilton hay không, nên các nhà nghiên cứu hạ yêu cầu xuống là: Hãy đề xuất một thuật toán để xác định xem một đồ thị bất kì có phải là đồ thị Hamilton hay không.
*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
trong hoán vị của tập '''{2,3,…n}'''ta kiểm tra xem Z có tạo nên chu trình hay không, tức là phải kiểm tra '''(n-1)!''' tập (Z) khác nhau.
==> Đâ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.
*Cho đến nay, việc nghiên cứu tìm ra thuật toán hiệu quả, xác định xem một đồ thị Hamilton hay không vẫn đang là một thách thức lớn đối với các nhà toán học và tin học.
*Một số nhà nghiên cứu đã đề xuất các thuật toán [[Heuristic]] (nhờ vào việc vận dụng các thuật toán thông minh nhân tạo, mạng [[neural]], thuật toán [[gen]],...) để giải quyết gần đúng các bài toán Hamilton.
*Những thuật toán loại này khá nhanh và thông thường dừng với hai trường hợp sau:
1. Nếu khẳng định đồ thị đang xét là đồ thị Hamilton là đó là một khẳng định chính xác và có thể kiểm chứng dễ dàng.
2. Nếu khẳng định định không phải là đồ thị Hamilton: có thể bị sai lầm với một xác xuất nào đó(thật ra trường hợp này chính là "Không biết đồ thị đã cho có phải là đồ thị Hamilton không").
==Qui tắc để tìm chu trình Hamilton==
Hiện nay, dù '''chưa tìm ra''' [[thuật toán]] tổng quát, nhưng có một số qui tắc khá tốt để sử dụng trong quá trình tìm '''chu trình Hamilton''' trong đồ thị. Những qui tắc này có thể phối hợp với với nhận xét về các tính chất [[đối xứng]] hay về tính chất nào đó của một [[đồ thị]] cụ thể để khỏi phải xét nhiều trường hợp khác nhau.
Xét đồ thị G=(X,E) gồm n đỉnh, trong quá trình tìm chu trình Hamilton chúng ta có thể vận dụng 4 qui tắc<ref>Trần Đan Thư - Dương Anh Đức, '''Lý Thuyết Đồ Thị''', Đại Học Khoa Học Tự Nhiên - ĐHQGTP.HCM, tháng 9, năm 2008</ref> sau đây
'''Qui tắc 1''': Lấy hết các cạnh kề với đỉnh bậc 2.
'''Qui tắc 2''': Không cho phát sinh chu trình ít hơn n cạnh.
'''Qui tắc 3''': Nếu đã lấy 2 cạnh kề với định x thì có thể bỏ tất cả các cạnh còn lại kề với x.
'''Qui tắc 4''': Duy trì tính liên thông và bảo đảm bậc mỗi đỉnh luôn lớn hơn hay bằng 2.
[[File:Hamilton_QT.png|300px|nhỏ|giữa]]
Quy tắc 3 được minh họa trong hình,khi thực hiện qui tắc này thì bậc của một số đỉnh bị giảm xuống : nhờ vậy chúng ta có thể tận dụng trở lại qui tắc 1 và qui tắc 4.
== Áp dụng 4 quy tắc tìm đường đi Hamilton ==
'''Bài toán: Tìm chu trình Hamilton trong đồ thị sau:'''
[[Tập tin:VdBaiToan1.png|lớn|400x|giữa|Đồ thị]]
'''BÀI GIẢI:'''
Tại đỉnh 1, chỉ có thể 2 trong 5 cạnh kề với đỉnh 1, do tính chất đối xứng của đồ thị ta chỉ cần xét hai trường hợp:
-Lấy 1---2 và 1---6
-Lấy 1---2 và 1---4
Nếu 1 trong 2 trường hợp mà tìm được chu trình Hamilton thì dừng và không cần xét trường hợp còn lại, nếu cả 2 trường hợp đều không tìm được chu trình Hamilton thì kết luận đồ thị không phải là đồ thị Hamilton.</br>
* '''Bây giờ giả sử lấy 1---2 và 1---6:'''
-Theo quy tắc 3, có thể xóa cạnh 1---3, 1---4 và 1---5
[[Tập tin:VdBaiToan2.png|lớn|400x|giữa|Hình 1]]
-Các đỉnh 3, 4, 5 trở thành bậc 2: ta lấy them được 6 cạnh kề với chúng.
[[Tập tin:VdBaiToan3.png|lớn|400x|giữa|Hình 2]]
-Theo quy tắc 3, có thể xóa cạnh: 10---9, 10---11
[[Tập tin:VdBaiToan4.png|lớn|400x|giữa|Hình 3]]
-Lấy 7---8 sẽ tạo chu trình(chỉ có 5 cạnh): ta xóa cạnh này theo quy tắc 2.
[[Tập tin:VdBaiToan5.png|lớn|400x|giữa|Hình 4]]
- Nếu lấy cả 7---11 và 8---9 thì tạo chu trình chư đủ cạnh, theo quy tắc 2 thì chỉ lấy 1 trong 2 cạnh này, do tính
đối xứng ta lấy 8---9 và bỏ 7---11
[[Tập tin:VdBaiToan6.png|lớn|400x|giữa|Hình 5]]
-Theo quy tắc 3: bỏ 8---6, 9---2
[[Tập tin:VdBaiToan7.png|lớn|400x|giữa|Hình 6]]
-Bắt buộc phải lấy 2---7 và 6---11: đã tìm được chu trình Hamilton.
[[Tập tin:VdBaiToan8.png|lớn|400x|giữa|Hình 7]]
</br>
'''==> Kết luận: đồ thị đang xét là đồ thị Hamilton.'''
==Cài đặt chương trình tìm đường đi Hamilton==
Bài toán: Cho một đồ thị n đỉnh hãy tìm chu trình Hamilton từ 1 đỉnh sao cho tổng trọng số đi từ đỉnh đó là nhỏ nhất (3=<n<=10)
//Khai báo
#define MAX 100
struct GRAPH // ma trận kề
{
int n;
int L[MAX][MAX];
};
int flag_trongso=0;// cờ giữ trọng số đang giữ nhỏ nhất
int flag_duongdi[MAX];// lưu giữ đường đi hiện tại với trọng số nhỏ nhất
int danhdau[MAX];// mảng lưu các đỉnh đã được đánh dấu
int duongdi[MAX];// lưu đường đi đang xét
//Hàm đọc ma trận từ file input.txt
void DocMaTranKe(GRAPH &g)
{
int i;
int j;
FILE* f;
f = fopen("input.txt","rt");
if(f == NULL)
{
printf("\nKhong mo duoc file");
return;
}
fscanf(f,"%d",&g.n);
for(i = 0; i < g.n; i++)
{
for(j = 0; j < g.n; j++)
{
fscanf(f,"%d",&g.L[i][j]);
flag_trongso+=g.L[i][j];//Gán cho trọng số 1 con số ảo lớn
}
}
fclose(f);
}
//Hàm Hamilton sử dụng phuơng pháp quay lui để tính tất cả các đường xuất phát từ 1 đỉnh
void Hamilton(int lan,int x,GRAPH g,int dinhbatdau)
{
if(lan>g.n && g.L[x][dinhbatdau])
{
printf(".");
int ts = TinhTrongSo(g);
if(ts<flag_trongso)
{
flag_trongso=ts;
LuuDuongDiNganNhatNow(g);
}
return;
}
for(int i=1;i<=g.n;i++)
{
if(g.L[x-1][i-1]!=0 && XetDanhDau(i,g)==1)
{
duongdi[lan]=i;
danhdau[lan]=i;
Hamilton(lan+1,i,g,dinhbatdau);
BoDanhDau(i,g);
}
}
}
//Hàm main
void main()
{
GRAPH g;
DocMaTranKe(g);
Init(g);
int x;
do
{
printf("Nhap dinh bat dau: ");
scanf("%d",&x);
} while (x>g.n);
danhdau[1]=x; duongdi[1]=x;
Hamilton(2,x,g,x);
printf("\nDuong di ngan nhat tu dinh %d la: \n",x);
ShowPath(g);
printf("Voi trong so nho nhat la: %d",flag_trongso);
getch();
}
//Các hàm nhỏ liên quan
void Init(GRAPH g)
{
for(int i=0;i<=g.n;i++)
danhdau[i]=-1;
}
int TinhTrongSo(GRAPH g)
{
int tong=0;
int i=1;
while(i<g.n)
{
int i1 = duongdi[i];
int i2 = duongdi[i+1];
tong+=g.L[i1-1][i2-1];
i++;
}
int dinhbatdau = duongdi[1];
int dinhketthuc = duongdi[g.n];
tong+=g.L[dinhketthuc-1][dinhbatdau-1];
return tong;
}
int XetDanhDau(int dinhxet,GRAPH g)
{
for(int i=1;i<=g.n;i++)
{
if(danhdau[i]==dinhxet)
return 0;
}
return 1;
}
void BoDanhDau(int dinhxet,GRAPH g)
{
for(int i=0;i<=g.n;i++)
if(danhdau[i]==dinhxet)
danhdau[i]=-1;
}
void ShowPath(GRAPH g)
{
for(int i=1;i<=g.n;i++)
printf("-%d-",flag_duongdi[i]);
printf("\n");
}
'''Cho một file "input.txt"''' có nội dung như sau:
9
978 1281 1129 1288 534 1002 1086 516 1077
1281 834 1111 761 821 1490 799 1296 1320
1129 1111 1998 1152 621 1543 1475 1139 597
1288 761 1152 312 1081 1374 398 885 1247
534 821 621 1081 768 925 676 989 1335
1002 1490 1543 1374 925 1168 419 1544 1847
1086 799 1475 398 676 419 322 211 953
516 1296 1139 885 989 1544 211 136 644
1077 1320 597 1247 1335 1847 953 644 210
'''Kết quả đường đi có trọng số nhỏ nhất xuất phát từ đỉnh 1 có chu trình Hamilton là: '''
1 -> 6 -> 4 -> 2 -> 5 -> 3 -> 9 -> 8
Với trọng tổng trọng số là: 5779
==Ứng dụng==
Bài toán mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm [[đường đi Hamilton]] trong [[lý thuyết đồ thị]], là một bài toán [[NP-đầy đủ]]. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm [[chu trình Hamiltonian]].
Bài toán mã đi tuần trên bàn cờ 5x5
- Đặt một quân mã ở 1 ô bất kì trên bàn cờ vua, theo quy tắc di chuyển của cờ vua, tìm các bước đi của quân mã sao cho mỗi ô chỉ được đi qua 1 lần và đi hết bàn cờ.
[[Tập tin:Knights-Tour-Animation.gif|khung|lớn|400x|giữa|Mã đi tuần]]
==Xem thêm==
* [[Thuật ngữ lý thuyết đồ thị]]
* [[Định lý Dirac]]
==Liên kết ngoài==
* [http://www.densis.fee.unicamp.br/~moscato/Hamilton.html The Hamiltonian Page] - Hamiltonian cycle and path problems, their generalizations and variations.
* {{MathWorld|title=Hamiltonian Circuit|urlname=HamiltonianCircuit}}
== Tham khảo ==
{{Reflist}}
== Tài liệu ==
<!-- Vui lòng nên thêm các giáo trình khoa học, hội thảo khoa học, bài viết có chất lượng quốc gia, quốc tế -->
* [[Øystein Ore|Ore, O]] "A Note on Hamiltonian Circuits." [[American Mathematical Monthly]] 67, 55, 1960.
* DeLeon, Melissa, "''[http://www.rose-hulman.edu/mathjournal/archives/2000/vol1-n1/paper4/v1n1-4pd.PDF A Study of Sufficient Conditions for Hamiltonian Cycles]''". Department of Mathematics and Computer Science, [[Seton Hall University]]
* Hamilton, William Rowan, "''Account of the Icosian Calculus''". [[Proceedings of the Royal Irish Academy]], 6 [[1858]]
{{Commonscat|Hamiltonian paths}}
* Đường đi Euler và Hamilton (Euler & Hamilton Paths), TS. Trần Văn Hoài, "''[http://www.cse.hcmut.edu.vn/~hoai/download/discrete-mathematics/master-course/2009-2010/talk_graphs-euler-hamilton.pdf]''".
==Liên kết ngoài==
* {{MathWorld|title=Hamiltonian Cycle|urlname=HamiltonianCycle}}
* [http://www.graph-theory.net/euler-tour-and-hamilton-cycles/ Euler tour and Hamilton cycles]
[[Thể loại:Lý thuyết đồ thị trong các bài toán tính toán]]
[[Thể loại:Bài toán NP-đủ]]
| 