[Chuyên đề] Chu trình Halminton

I - ĐỊNH NGHĨA:
- Trong một đồ thị, đường đi qua tất cả các đỉnh, mỗi đỉnh chỉ một lần, được gọi là đường đi Hamilton.
- Chu trình đi qua tất cả các đỉnh, mỗi đỉnh chỉ một lần (trừ đỉnh đầu trùng với đỉnh cuối) được gọi là chu trình Hamilton.
- Đồ thị có đường đi Hamilton được gọi là đồ thị bán Hamilton.
- Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton.

II - TÍNH CHẤT:
Cho đến nay, chưa tìm ra tiêu chuẩn để nhận biết một đồ thị có là đồ thị Hamilton không. Phần lớn tìm được là các điều kiện đủ để một đồ thị là một đồ thị Hamilton.
1. Định lý Dirac (1952): Đơn đồ thị vô hướng G có n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.
2. Cho đồ thị hữu hướng G liên thông mạnh có n>2 đỉnh. Nếu mọi đỉnh có bán bậc vào không nhỏ hơn n/2 và bán bậc ra không nhỏ hơn n/2 thì đồ thị đó là đồ thị Hamilton.
3. Đồ thị vô hướng G, tồn tại k đỉnh sao cho nếu xoá đi k đỉnh này và các cạnh liên thuộc của nó thì đồ thị nhận được sẽ có nhiều hơn k thành phần liên thông. Lúc đó, khẳng định được đồ thị đó không có chu trình Hamilton.
4. Định lý Ore (1960) : Đơn đồ thị liên thông G có n đỉnh (n >= 3), nếu bất kỳ 2 cặp đỉnh không liền kề u và v có tổng các bậc không nhỏ hơn n (deg(u) deg(v) >= n) thì đồ thị đó là đồ thị Hamilton.

III - CHƯƠNG TRÌNH LIỆT KÊ CHU TRÌNH HALMINTON:
Sử dụng phương pháp đệ quy quay lui để tìm một chu trình Hamilton:
Input : tập tin văn bản HAMILTON.IN có:
• dòng đầu : có 2 số nguyên dương n và m với n là số đỉnh (2 <= n <= 100) và m là số cạnh
• m dòng sau, mỗi dòng có 2 số nguyên dương u và v thể hiện u và v là 2 đỉnh kề nhau.

Code:

 
const  InputFile  = 'HAMILTON.IN';
OutputFile = 'HAMILTON.OUT';
max = 100;
var  fo: Text;
a: array[1..max, 1..max] of Boolean;   
Free: array[1..max] of Boolean;
x: array[1..max] of Integer;
n: Integer;
procedure Nhapdulieu;
var  i, u, v, m: Integer;
f: Text;
begin
Assign(f, InputFile);
Reset(f);
FillChar(a, SizeOf(a), False);
ReadLn(f, n, m);
for i := 1 to m do
begin
ReadLn(f, u, v);
a[u, v] := True;
a[v, u] := True;
end;
Close(f);
end;
procedure XuatKetQua;
var  i: Integer;
begin
for i := 1 to n do Write(fo, x[i], ' ');
WriteLn(fo, x[1]);
end;
procedure TimCT(i: Integer);
var  j: Integer;
begin
for j := 1 to n do
if Free[j] and a[x[i - 1], j] then
begin
x[i] := j;
if i < n then
begin
Free[j] := False;
TimCT(i  1);
Free[j] := True;
end
else  if a[j, x[1]] then XuatKetQua;
end;
end;
BEGIN
NhapDuLieu;
FillChar(Free, SizeOf(Free), True);
x[1] := 1;
Free[1] := False;
Assign(fo, OutputFile);
Rewrite(fo);
TimCT(2);
Close(fo);
END.


IV - BÀI TẬP:
Bài 1 : Mã đi tuần (Knight’s tour puzzle)
Tìm đường đi của quân mã qua tất cả các ô của bàn cờ vua, mỗi ô chỉ một lần.
Kết quả : Đường đi Hamilton (chu trình Hamilton) của quân mã trong bàn cờ

Bài 2 : Du lịch
Một công ty du lịch lên kế hoạch một tour du lịch thăm K ốc đảo (2<=K<=8) trong số N ốc đảo (2 <= N <= 1000000) ở sa mạc Sahara bằng lạc đà. Mỗi ốc đảo có thể được nối trực tiếp với ốc đảo khác không quá một con đường. Và mỗi ốc đảo có không quá 5 con đường nối với các ốc đảo khác. Các ốc đảo được đánh số thứ tự từ 1 đến N. Lạc đà không thể đi quá L con đường trong một ngày (1 <= L <= 10).

Tour du lịch bắt đầu hành trình từ ốc đảo a, sau đó thăm và nghỉ đêm tại từng ốc đảo trong K–1 ốc đảo cần thăm và trở về ốc đảo a trong đúng K ngày, không đi thăm bất kỳ một ốc đảo quá một lần.
Hãy giúp công ty du lịch lên kế hoạch hành trình đi thăm K ốc đảo.

Input : tập tin văn bản SAHARA.IN có các thông tin sau:
• dòng đầu tiên có 3 số nguyên dương N, K, L với P là số con đường
• N dòng tiếp theo thể hiện ma trận kề.
• Dòng cuối cùng có K số nguyên dương thể hiện các ốc đảo cần thăm với ốc đảo a là số nguyên đầu tiên.

Output : tập tin văn bản SAHARA.OUT có các thông tin sau :
• dòng đầu là số nguyên
–1 cho biết không thể thực hiện
M là số ốc đảo mà hành trình sẽ đi qua.
• Nếu sẽ thực hiện được hành trình thì M 1 dòng tiếp theo sẽ liệt kê số hiệu của các ốc đảo theo thứ tự hành trình đi qua (trong đó có K ốc đảo cần thăm).
*Ví dụ:
*Hướng dẫn : tìm chu trình Hamilton của đồ thị có K đỉnh (K ốc đảo cần đi thăm).