Định lý 2.24 (Bigalke và Jung, 1979)

Ta có : n=12, (Chỉ số độc lập)

Vậy : .Suy ra : G là đồ thị Hamilton.

5. 
   Một số kết quả cho đồ thị k-chính quy :
   

• 
  Định lý 2.25 (Ước lượng bậc của Bauer-Broersma-Veldman) :
  

Nếu tồn tại thì đồ thị trở thành đồ thị Hamilton k-chính quy, 1-khó, f(k) đỉnh.

Vậy n là số đỉnh nhỏ nhất để tồn tại Đồ thị-(n,k)

Ví dụ : Sau đây là Đồ thị-(18,4).



Chứng minh ước lượng trên :

Trường hợp 1 : , ta sử dụng Định lý 2.3 (Dirac)

Trường hợp 2 :

• 
  Định lý 2.26 (Nash-Williams, 1969) : Cho G là đồ thị k-chính quy, có 2k+1 đỉnh thì G là đồ thị Hamilton.
  
• 
  Định lý 2.27 (Erdos and Hobbs, 1978) : Cho G là đồ thị 2-liên thông, k-chính quy thì có 2k+4 đỉnh () thì G là đồ thị Hamilton. (
  
• 
  Định lý 2.28 (Bollobas and Hobbs, 1978) : Cho G là đồ thị 2-liên thông, k-chính quy, có n đỉnh sao cho : thì G là đồ thị Hamilton.
  
• 
  Định lý 2.29 (Jackson, 1980) : Cho G là đồ thị 2-liên thông, k-chính quy có nhiều nhất 3k đỉnh thì G là đồ thị Hamilton.
  

• 
  Định lý 2.30 (Hilbig 1986) : Cho G là đồ thị 2-liên thông, k-chính quy nhiều nhất 3k+3 đỉnh thì G thỏa mãn 1 trong các mệnh đề sau :
  
  • 
    G là đồ thị Hamilton.
    
  • 
    G là đồ thị Petersen, P (Ví dụ 2.19)
    
  • 
    G là đồ thị P’ sinh ra bằng cách thay 1 đỉnh của P thành 1 tam giác 3 đỉnh.
    

Ta chỉ xét các đồ thị sau : [16,2][16,3][16,4][17,2][17,3][17,4]

Ví dụ : Đồ thị [16,4] và [17,4]

Đây là các đồ thị 4-liên thông chặt (cũng là 4 liên thông hoặc 2-liên thông), 1-khó và 4 chính quy.

• 
  Định lý 2.31 (Tutte, 1956) : Mọi đồ thị phẳng 4-liên thông đều có chu trình Hamilton.
  

• 
  Định lý 2.32 (Ước lượng đỉnh, Haggkvist) : Cho G là đồ thị m-liên thông, k-chính quy, có tối đa (m+1)k đỉnh thì G là đồ thị Hamilton.
  
• 
  Định lý 2.33 (Haggkvist, 1976) : Cho G là đồ thị lưỡng phân 2-liên thông, k-chính quy có tối đa 6k đỉnh thì G là đồ thị Hamilton.
  
• 
  Định lý 2.34 (Haggkvist, 1979) : Cho G là đồ thị 2-liên thông, có nhiều nhất 3k+2 đỉnh với dãy bậc tương ứng là (k, k, …, k+1, k+1) thì G là đồ thị Hamilton.
  
• 
  Định lý 2.35 (Jackson and Jung) : Cho. G là đồ thị 3-liên thông, k-chính quy có tối đa 4k đỉnh thì G là đồ thị Hamilton.
  

Đường đi và chu trình Hamilton có nhiều ứng dụng trong thực tế, đặc biệt là trong tin học và Toán tối ưu. Nhưng vì lý do hạn chế của 1 tiểu luận nên chúng em chỉ xin trình bày một số dấu hiệu nhận biết 1 đồ thị cho trước có thể có đường đi, chu trình Hamilton hay không? Cũng như tìm ra những đường đi (nếu có).

• 
  Qui tắc để xây dựng một chu trình Hamilton H hoặc chỉ ra đồ thị vô hướng không là Hamilton
  

Qui tắc 2. Không có chu trình con(chu trình có chiều dài

Qui tắc 3. Khi chu trình Hamilton mà ta đang xây dựng đi qua đỉnh i thì xoá tất cả các cạnh kề với i mà ta chưa dùng (vì không được dùng đến nữa).

Điều này lại có thể cho ta một số đỉnh bậc 2 và ta lại dùng qui tắc 1.

Qui tắc 4. Không có đỉnh cô lập hay cạnh treo nào được tạo nên sau khi áp dụng qui tắc 3.

• 
  Bài toán 1 : Hãy xác định đường đi, chu trình Hamilton của các đồ thị sau :
  

a)

b)

c
a b c

d e f

g k
) d)

e) f)

(Julius Petersen)

****

Giải :

a) Áp dụng điều kiện cần, chú ý ta sẽ dùng phương pháp phản chứng.

Ta bỏ đi 4 đỉnh : o, j, q, m và các cạnh liên thuộc thì ta có hình a’.

Theo điều kiện cần :

• 
  Giả sử đồ thị trên có chu trình Hamilton. Khi đó, nếu bỏ 4 đỉnh thì ta chỉ có tối đa là 4 thành phần liên thông.
  
• 
  Giả sử đồ thị trên có đường đi Hamilton. Khi đó, nếu bỏ 4 đỉnh thì ta chỉ có tối đa là 5 thành phần liên thông.
  

Vậy ta có 5 đỉnh cô lập : i, k, p, l, n là 5 thành phần liên thông và {a, b, c, h, g, f, e, d, a} là 1 thành phần liên thông. Tổng cộng có 6 thành phần liên thông (mâu thuẫn).

Hay : Đồ thị trên không có đường đi, chu trình Hamilton.

b)

Đồ thị này không có dấu hiệu nhận biết nhưng ta có thể dễ dàng chỉ ra những chu trình Hamilton như sau :

* 1 2 12 3 13 14 4 5 15 6 7 8 9 10 11 1

Giả sử đồ thị có đường đi Hamilton (P).

đường đi (P) có 19 cạnh. (*)

Theo điều kiện cần, ta có 20 đỉnh thì đồ thị có

ít nhất 20-2=18 đỉnh có bậc 2, mỗi đỉnh

có đúng 2 cạnh liên thuộc trên (P).

Tất cả các đỉnh đều có bậc 3 nên mỗi đỉnh có

1 cạnh không thuộc đường đi (P).

Ngoài 18 đỉnh trên, ta giả sử 2 đỉnh còn lại

luôn luôn có ít nhất 1 cạnh nối chúng với nhau

hoặc nối vào 1 trong 18 đỉnh trên nhưng không nằm trên (P)

Vậy số cạnh ít nhất không thuộc (P) là : (18.1)/2+1 = 10 (cạnh)

Suy ra số cạnh thuộc (P) của đồ thị là : 25-10 = 15 cạnh.( không thỏa mãn (*)).

Vậy đồ thị không có đường đi Hamilton và chu trình Hamilton.

Giả sử đồ thị có đường đi Hamiton (P), khi đó : đường đi (P) có 8 cạnh.

Theo điều kiện cần, số cạnh ít nhất không thuộc (P) là : (7.1)/2+1= 4.5 (cạnh).

Vậy số cạnh còn lại của đồ thị là : 9 – 4.5 = 4.5 (cạnh) < 8 cạnh (vô lý).

Suy ra : đồ thị không có đường đi Hamilton và chu trình Hamilton.

e)

d

Từ đồ thị ta có thể chỉ ra những đường đi Hamilton sau :

1. dagebhfc

2. cbhfegad

Nhưng đồ thị không có chu trình Hamilton. Chứng minh :

Giả sử đồ thị có chu trình Hamilton thì ta bỏ đi các đỉnh b và f thì đồ thị có tối đa 2 thành phần liên thông.

Xem đồ thị thấy có 3 thành phần liên thông (mâu thuẫn).

f) Ta có đường đi Hamilton như sau :

1276511891043

Nhưng không có chu trình Hamilton vì :

Đồ thị có 11 đỉnh. Giả sử đồ thị có chu trình Hamilton

(P) thì (P) phải có đúng 11 cạnh.

Xét 6 đỉnh không kề nhau : 1, 5, 7, 8, 10, 3. Mỗi đỉnh

này phải có đúng 2 cạnh liên thuộc (P). Vậy ta có :

6.2 = 12 cạnh >11 cạnh (vô lý).

g) Đồ thị petesen có đường đi Hamilton như sau :

abcdegkhfi

nhưng không có chu trình Hamilton vì :

Giả sử đồ thị có chu trình Hamilton (P)

Thì (P) phải có đúng 9 cạnh.

Xét 6 đỉnh không kề nhau : a, d, c, f, i, h. Mỗi đỉnh phải có đúng 2 cạnh liên thuộc (P). Vậy ta có 6.2=12 cạnh > 9 cạnh (vô lý).

Chú ý : Nếu bỏ bất kỳ 1 đỉnh của đồ thị Petersen, ta luôn có được chu trình Hamilton.

V

* Khi đó ta có chu trình Hamilton với 5 đỉnh vòng ngoài là :

a

b

e
edhkgicba


g

k
cigkhdeabc


g

b

f

k

*
e

hdegkbcifh

fhdegkbcif

• 
  Bài toán 2 : Tìm điều kiện của m, n để có đường đi Hamilton, chu trình Hamilton.
  

a) Đồ thị K_m,n có chu trình Hamilton khi và chỉ khi m = n.

Đồ thị K_m,n có m+n đỉnh và có thể chia thành 2 tập V₁ và V₂ , trong đó :

V₁ = , V₂ = và mỗi đỉnh u_iV₁ là đỉnh kề

của tất cả các đỉnh thuộc V₂ và ngược lại.

- Nếu m = n khi đó đồ thị K_n,n có chu trình Hamilton như sau:

- Nếu m n, không mất tính tổng quát ta giả sử m > n. Khi đó ta bỏ đi các đỉnh thuộc tập V₂ và các cạnh liên thuộc của các đỉnh này ta được m (>n ) thành phần liên thông. Suy ra K_m,n không có chu trình Hamilton.

Đồ thị K_m,n có m+n đỉnh và có thể chia thành 2 tập V₁ và V₂ , trong đó :

V₁ = , V₂ = và mỗi đỉnh u_iV₁ là đỉnh kề của tất cả các đỉnh thuộc V₂ và ngược lại.

- Nếu , không mất tính tổng quát ta giả sử m > n hay m – n = 1, khi đó ta có đường đi Hamilton như sau :

- Nếu , không mất tính tổng quát ta giả sử m > n hay m – n > 1

Khi đó ta bỏ đi các đỉnh thuộc tập V₂ và các cạnh liên thuộc của các đỉnh này ta được m (>n+1 ) thành phần liên thông. Suy ra K_m,n không có đường đi Hamilton.

Dù đã có nhiều cố gắng nhưng có lẽ tiểu luận không thể tránh được những sai sót nhất định. Kính mong thầy và các bạn học viên K25 Phương Pháp Toán Sơ Cấp có những đóng góp để Tiểu luận được hoàn chỉnh hơn.

Nhóm chúng em xin gửi lời cảm ơn sâu sắc đến PGS.TSKH Trần Quốc Chiến đã có những buổi dạy nhiệt tình, hết mình để chúng em có những kiến thức nhất định về môn học rất hay này.
*****

Tài liệu tham khảo :

[1] Giáo trình Lý Thuyết Đồ Thị dành cho lớp Cao học, PGS.TSKH Trần Quốc Chiến, Đà Nẵng – 2012.

[2] A study of sufficient Conditions for Hamilton Cycle, Melissa de Leon, Seton Hall University South Orange, New Jersey, USA.

[3] Sách hướng dẫn bài tập Toán Rời Rạc, Ths. Nguyễn Duy Phương, HV Công nghệ bưu chính viễn thông, Hà Nội – 2006.

[4] Đề tài Toán Rời Rạc, Ths. Lê Đình Huy, TP.HCM - 2011.

[5] Bài tập Lý Thuyết Đồ Thị, Giảng viên : Nguyễn Ngọc Trung.