Định lý và thuật toán liệt kê tất cả các chu trình Hamilton
Định lý 3.1 (Dirak 1952). Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton. Chứng minh: Thêm vào đồ thị G k đỉnh mới và nối chúng với tất cả ...
Định lý 3.1 (Dirak 1952).
Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.
Chứng minh:
Thêm vào đồ thị G k đỉnh mới và nối chúng với tất cả các đỉnh của G. giả sử k là số nhỏ nhất các đỉnh cần thêm vào để cho đồ thị thu được G’ là đồ thị Hamilton. Ta sẽ chỉ ra rằng k=0. Thực vậy, giả sử ngược lại là k >0. Ký hiệu
v, p, w, . . ., v là chu trình Hamilton trong G’, trong đó v, w là đỉnh của G còn p là một trong số các đỉnh mới. Khi đó w không kề với v vì nếu ngược lại, ta không cần sử dụng p và điều đó là mâu thuẫn với giả thiết k nhỏ nhất. Hơn thế nữa đỉnh (w’ chẳng hạn) kề với w không thể đi liền sau đỉnh v’ (kề với v) vì rằng khi đó có thể thay
v → p→ w → . . . → v’→ w’ → . . . → v
bởi v → v’ → . . . → w → w’ → . . . → v bằng cách đảo ngược đoạn của chu trình nằm giữa w và v’. Từ đó suy ra là số đỉnh của đồ thị G’ không kề với w là không nhỏ hơn số đỉnh kề với v (tức là ít nhất cũng là bằng n/2+k), đồng thời số đỉnh của G’ kề với w ít ra là phải bằng n/2+k. Do không có đỉnh nào của G’ vừa không kề, lại vừa kề với w, cho nên tổng số đỉnh của đồ thị G’ (G’ có n+k đỉnh) không ít hơn n+2k. Mâu thuẫn thu được đã chứng minh định lý.
Định lý sau là tổng quát hoá của định lý Dirak cho đồ thị có hướng:
Định lý 3.2
Giả sử G là đồ có hướng liên thông với n đỉnh.
Nếu deg+ (v) ≥ n/2, deg – (v) ≥ n/2, ∀ ∀v thì G là Hamilton.
Có một số dạng đồ thị mà ta có thể biết khi nào là đồ thị Hamilton. Một ví dụ như vậy là đồ thị đấu loại. Đồ thị đấu loại là đồ thị có hướng mà trong đó hai đỉnh bất kỳ của nó được nối với nhau bởi đúng một cung. Tên đấu loại xuất hiện như vậy vì đồ thị như vậy có thể dùng để biểu diễn kết quả thi đấu bóng chuyền, bóng bàn hay bất cứ một trò chơi nào mà không cho phép hoà. Ta có định lý sau:
Định lý 3.3
i) Mọi đồ thị đấu loại là nửa Hamilton.
ii) Mọi đồ thị đấu loại liên thông mạnh là Hamilton.
Ví dụ 3.2
Đồ thị đấu loại D5, D6 được cho trong hình 3.2
Hình 3.2 Đồ thị đấu loại D 5 , đấu loại liên thông mạnh D 6 .
Thuật toán liệt kê tất cả các chu trình Hamilton của đồ thị
Thuật toán sau đây được xây dựng dựa trên cơ sở thuật toán quay lui cho phép liệt kê tất cả các chu trình Hamilton của đồ thị.
Procedure Hamilton(k);
(* liet ke cac chu trinh Hamilton thu duoc bang viec phat trien day dinh (X[1],. . . , X[k-1]) cua do thi G=(V,E) cho boi danh sach ke: Ke(v), v ∈ V *)
begin
for y ∈ Ke(X[k-1]) do
if (k =N+1) and (y=v 0 ) then Ghinhan(X[1],. . . , X[n], v 0 )
else
if Chuaxet[y] then
begin
X[k]:=y;
Chuaxet[y]:=false;
Hamilton(k+1);
Chuaxet[y]:=true;
end;
end;
(* Main program*)
begin
for v ∈ V do Chuaxet[v]:=true;
X[1]:=0; (* v0 la mot dinh nao do cua do thi *)
Chuaxet[v0]:=false;
Hamilton(2);
end.
Ví dụ 3.3
Hình 3.3 dưới đây mô tả cây tìm kiếm theo thuật toán vừa mô tả.
Hình 3.3 Đồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui.
Trong trường hợp đồ thị có không quá nhiều cạnh thuật toán trên có thể sử dụng để kiểm tra đồ thị có phải là Hamilton hay không.
