Chuyên đề Đồ thị Hamilton

Chuyên đề 
ĐỒ THỊ 
HAMILTON 
Khái niệm đường đi Hamilton được xuất phát từ bài toán : 
 “ Xuất phát từ một đỉnh của khối thập nhị diện đều , hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnhkhác , mỗi đỉnh đi qua đúng một lần , sau đó trở về đỉnh xuất phát ” 
Bài toán này được nhà toán học Hamilton đưa ra vào năm 1859 
Giới thiệu : 
Nhà toán học Hamilton 
 Đường đi Hamilton là đường qua tất cả các đỉnh của đồ thị và đi qua mỗi đỉnh đúng một lần 
Hay đường đi (x[1],x[2],, x[n ]) được gọi là đường đi Hamilton nếu x[i] ≠x[j ] (1≤i< j ≤n ) 
Định nghĩa : 
a 
d 
b 
c 
G2 
Ví dụ : Đường đi Hamilton của đồ thị G2 là : a b c d 
Định nghĩa : 
 Chu trình Hamilton là đường đi Hamilton có một cạnh trong đồ thị nối đỉnh đầu với đỉnh cuối của đường đi 
 Hay chu trình (x[1],x[2],,x[n],x[1]) được gọi là chu trình Hamilton nếu x[i]≠x[j ] (1≤i< j≤n ) 
a 
b 
e 
c 
d 
G1 
Ví dụ : Chu trình Hamilton của đồ thị G1 là : a b c d e a 
 Đồ thị Hamilton là đồ thị có chứa một chu trình Hamilton 
 Đồ thị nửa Hamilton là đồ thị có chứa một đường đi Hamilton 
Định nghĩa : 
a 
d 
b 
c 
g 
a 
d 
b 
c 
e 
f 
a 
b 
e 
c 
d 
G1 
G2 
G3 
Một số ví dụ 
Đồ thị G1 là đồ thị Hamilton 
Đồ thị G2 là đồ thị nửa Hamilton 
Đồ thị G3 không có chu trình hay đường đi Hamilton 
Không giống như đồ thị Euler, chúng ta chưa có điều kiện cần và đủ để kiểm tra xem một đồ thị có là Hamilton hay không 
Cho đến nay chỉ có các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có đường đi Hamilton. 
Chú ý: 
Đồ thị đầy đủ 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 . 
Định lý về đồ thị Hamilton: 
Đồ thị đầy đủ K4 
2. Đơn đồ thị vô hướng G với n>2 đỉnh , mỗi đỉnh có deg(v ) ≥ n/2 th ì G là đồ thị Hamilton ( Dirak 1952) 
Định lý về đồ thị Hamilton: 
a 
b 
e 
c 
d 
G 
3. Giả sử G là đồ thị có hướng liên thông mạnh với n đỉnh . Nếu với mỗi đỉnh thuộc đồ thị thoả : 
 deg+(v ) ≥ n/2 và deg-(v) ≥ n/2 
 thì G là đồ thị Hamilton. 
Định lý về đồ thị Hamilton: 
Đồ thị G có hướng liên thông mạnh 
Ví dụ : Đồ thị G là đồ thị có hướng liên thông mạnh thỏa mãn 
 các điều kiện trên G là đồ thị Hamilton 
Định lý về đồ thị Hamilton ( tt ): 
4. Đồ thị đấu loại : là đồ thị có hướng mà trong đó 2 đỉnh bất kỳ của nó được nối với nhau bởi đúng một cung . 
Mọi đồ thị đấu loại là nửa Hamilton 
Mọi đồ thị đấu loại liên thông mạnh là Hamilton 
Đồ thị đấu loại D5 
Đồ thị đấu loại liên thông mạnh D6 
Định lý về đồ thị Hamilton ( tt ): 
5. Đơn đồ thị vô hướng G gồm n đỉnh với n ≥ 3. Nếu deg(v ) ≥(n-1)/2 với mọi đỉnh v của G thì G có đư ờ ng đi Hamilton. 
6. Đơn đồ thị vô hướng G gồm n đỉnh với n ≥ 3. Nếu deg(x)+deg(y ) ≥n với mọi cặp đỉnh x,y không kề nhau của G thì G là đồ thị Hamilton. 
7. Đơn đồ thị vô hướng G gồm n đỉnh và m cạnh . Nếu m ≥ (n2-3n+6)/2 thì G là đồ thị Hamilton. 
a 
b 
e 
c 
d 
G 
Cho tới nay, vẫn chưa tìm ra phương pháp với độ phức tạp đa thức để tìm chu trình cũng như đường đi Hamilton trong trướng hợp đồ thị tổng quát . 
Có thể sử dụng thuật toán quay lui để liệt kê chu trình Hamilton 
Tìm chu trình Hamiloton của đồ thị : 
Cấu trúc dữ liệu 
Lưu trữ đồ thị đã cho dưới dạng danh sách kề Ke(v ) 
Liệt kê các chu trình Hamilton thu được bằng việc phát triển dãy đỉnh 
(X[1],,X[k-1]) 
Mô tả thuật toán : 
Bước 1: Bắt đầu đi từ đỉnh 1, x[1]:=1 
Bước 2: Tìm và lưu đỉnh có cạnh nối với x[i ] và đỉnh j này 
 chưa thăm trước đó . 
Bước 3: Nếu đỉnh j này là x[n ] và giữa j và x[1] có cạnh nối 
	 thì xuất ra đồ thị Hamilton. 
 Nếu đỉnh j vẫn chưa phải là x[n ] thì tiếp tục bước 2. 
Mã giả của thuật toán 
Procedure Hamilton(k ); 
Begin 
 for y Ke(X[k-1]) do 
 if (k=n+1) and (y=v0) then ghinhan(X[1],,X[n],v0) 
 else 
 if chuaxet[y ] then 
 begin 
 X[k ]:=y; 
 chuaxet[y ]:=false; 
 Hamilton(k+1); 
 chuaxet[y ]:=true; 
 end; 	 
End; 
Đồ thị vô hướng G gồm 5 đỉnh và 6 cạnh 
 5 6 
 1 2 
 1 3 
	1 4 
	2 4 
 	2 5 
	3 5 
1 
2 
3 
4 
5 
Dữ liệu vào : (input) 
1 
2 
3 
4 
5 
1 
2 
3 
4 
5 
X = 
1 
 2 
3 
4 
5 
1 
3 
 6 
1 
4 
5 
1 
2 
1 
Chu trình Hamilton 
Mô tả quá trình tìm chu trình Hamilton 
Nhận xét 
Với đồ thị có số cạnh lớn thuật tóan trên sẽ không thể đáp ứng hai yêu cầu : 
Thời gian thực hiện : độ phức tạp của thuật toán trong trường hợp xấu nhất là O(n *m) ( với n là số cạnh và m là số đỉnh của đồ thị ) 
Kích thước bộ nhớ : do thuật toán sử dụng là thuật toán quay lui nên việc xử lý đồ thị lớn sẽ gây tràn bộ nhớ . 
 Thuật toán này chỉ có khả năng làm việc với đồ thị có số cạnh nhỏ 
5 
6 
9 
4 
8 
2 
3 
1 
7 
Đây có là đồ thị hamilton không ? 
Bài tập 
Một số bài toán có liên quan đến đồ thị Hamilton 
Bài toán mã đi tuần : Trên bàn cờ tổng quát n*n (n chẵn , 6≤n≤20), có đặt quân mã ở một ô nào đó . Hãy tìm một hành trình của quân mã từ ô xuất phát , đi qua tất cả các ô đúng 1 lần . 
XIN CẢM ƠN SỰ CHÚ Ý THEO DÕI 
 CỦA THẦY VÀ CÁC BẠN 
NHÓM THỰC HIỆN CHUYÊN ĐỀ: 
 Nguyễn Tuấn Hùng 
 Nguyễn Quốc Huy 
 Bùi Hoàng Việt