ĐẠi học sư phạM ĐÀ NẴng khoa toán lớp cao học phưƠng pháp toán sơ CẤp k25 Đề tài : ĐƯỜng đi hamilton
Định lý 1.4 (Bất đẳng thức Whiney)
tải về 220.16 Kb.
|
Định lý 1.4 (Bất đẳng thức Whiney). Với mọi đồ thị G ta có k(G)    (G)
CHƯƠNG II: ĐƯỜNG ĐI HAMILTON ***** 1. Định nghĩa : Cho đồ thị (có hướng) G=(V,E).
Như vậy mọi chu trình Hamilton có độ dài bằng số đỉnh, và mọi đường đi Hamilton có độ dài bằng số đỉnh trừ 1.
Ví dụ 2.1: 
Hình 2.1 Đồ thị trên có cả chu trình Euler và chu trình Hamilton:  .
2. Điều kiện cần
Giả sử đồ thị G có chu trình Hamilton C. Khi đó:
Giả sử đồ thị n đỉnh G có đường đi Hamilton P. Khi đó:
Ví dụ 2. : Xét đồ thị: 
Hình 2.2 Đồ thị có đường đi Hamilton: Đồ thị không có chu trình Hamilton Thật vậy, nếu tồn tại chu trình Hamilton C thì nó phải có 5 cạnh. Vì bậc deg(v2)=deg(v4)=3 nên phải có 1 cạnh tới v2 và 1 cạnh tới v4 không thuộc chu trình C. Số cạnh còn lại là 4 nên C không thể có 5 cạnh được, mâu thuẫn. Ta cũng có thể áp dụng trực tiếp định lý 2.4.1. Nếu bỏ đi 2 đỉnh v2 và v4 cùng các cạnh liên thuộc chúng thì đồ thị còn lại 3 đỉnh độc lập, có 3 thành phần liên thông. Như vậy theo mệnh đề (iii) của định lý 2.4.1 thì đồ thị không có chu trình Hamilton.
Ta lập đồ thị 9 đỉnh 1, 2, ...,9, đỉnh i chỉ người i. Ta đặt đỉnh 1 tại tâm và các đỉnh còn lại trên đường tròn như hình vẽ. Mỗi cách xếp là một chu trình Hamilton của đồ thị. Chu trình thứ nhất như hình vẽ là
Xoay lần lượt chu trình các góc 
Hình 2.4 
Hình 2.5 
Hình 2.6 3. Điều kiện đủ
Chứng minh : Tương tự như lời giải bài toán xếp 9 người trên bàn tròn, ta xây dựng cách xếp theo chu trình Hamilton trên đồ thị sau (n=2k+1): 
Hình 2.7 Xoay chu trình lần lượt một góc
Ví dụ 2.4 : 
Hình 2.9 Theo định lý Dirac, xét đồ thị W6 như hình vẽ. Trong đồ thị này ta có
Bao đóng C(G) của đồ thị G n đỉnh là đồ thị thu được từ G bằng cách : Theo quy nạp, nối tất cả các cặp đỉnh không kề nhau mà tổng số bậc ít nhất bằng n cho đến khi không còn cặp đỉnh nào như vậy nữa.
Ví dụ 2.5. Đồ thị W6 ở ví dụ trên cũng thỏa mãn định lý Ơre Ta có: nên đồ thị W6 có chu trình Hamilton.
Ta thêm vào đồ thị G một đỉnh x và nối x với mỗi đỉnh của G bởi một cạnh, ta thu được đồ thị G’ có n+1đỉnh. Bậc của mọi đỉnh trong G’ đều lớn hơn bậc cũ của nó một đơn vị (trừ z), còn bậc của z bằng n. Do đó trong G’thì ta có:
Theo ĐL Ore thì G’ có chu trình Hamilton, suy ra G có đường đi Hamilton.
Ví dụ 2.7 
Hình 2.10 Cho hai tập đỉnh V1 và V2 sao cho Ta có: với mọi đỉnh v của G đều có bậc ít nhất là 2, mà 4 5 6
7 8 9 Hình 2.11 Giả sử G có chu trình Hamilton H, theo qui tắc 1, tất cả các cạnh kề với đỉnh bậc 2 đều ở trong H: (1,2);(1,4);(2,3);(3,6);(4,7);(7,8);(6,9);(8,9). Ta có chu trình con là Vậy G không là đồ thị Hamilton.
Cho đồ thị có hướng G với n đỉnh. Ta có các kết quả phát biểu trong các định lý sau.
Định nghĩa (Đồ thị bắc cầu) : Đồ thị có hướng đủ G = (V, E) gọi là bắc cầu nếu (u,v), (v,w)  E suy ra (u,w) E.
Có một số dạng đồ thị mà ta có thể biết khi nào là đồ thị Hamilton. Ví dụ đồ thị đấu loại. Định nghĩa (Đồ 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:
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ụ :  
Đồ thị đấu loại D5 Đồ thị đấu loại liên thông mạnh D6 Hình 2.12 Hình 2.13
(Phần này được dịch từ tài tiệu tham khảo bằng tiếng anh)
Ví dụ : Đây là đồ thị 2-liên thông vì ta bỏ đi 2 đỉnh b,e thì đồ thị không còn liên thông nữa. Ta có bậc của đồ thi là n = 6.  : bậc nhỏ nhất bằng 3.
 : Chỉ số độc lập bằng 2 (tức là số đỉnh độc lập
Nhau lớn nhất bằng 2) Vậy ta có :
Ví dụ : T Đây là đồ thị 2-liên thông và không chứa đồ thị
Nên ta thấy G có chu trình Hamilton với mọi đỉnh.
V  í dụ : đồ thị (P)
Ta có : chỉ số liên thông đỉnh k(G) = 2, Vậy Mọi đỉnh.
Ví dụ : Ta có thể lấy đồ thị của Ví dụ trên. Ta cũng chứng minh được G là đồ thị Hamilton.
V  í dụ : 
Vậy G là đồ thị Hamilton
Định nghĩa (Độ co dãn đồ thị) : Cho w(G) là số thành phần liên thông của đồ thị G. Xét : 
Thì  được gọi là độ co dãn đồ thị G.
Định nghĩa (đồ thị t-khó) : Nếu tồn tại 1 số t sao cho :  thì đồ thị G được gọi là t-khó.
Nghĩa là : Cho G là đồ thị t-khó, nếu k>1 thì ta không thể chia G thành k thành phần liên thông bằng cách loại bỏ ít hơn t.k đỉnh. Ví dụ : Đồ thị Petersen là đồ thị 1-khó. 
Nếu ta bỏ đi 1.k = k đỉnh, ta sẽ thu được tối đa k thành phần liên thông. Qui ước : Các đồ thị hoàn chỉnh đều có độ co dãn vô hạn. Vaclav Chvatal là người đã đưa ra lý thuyết về độ co dãn đồ thị. Sau đó, Bauer, Broersma và Schmiechel đã phát triển với 99 định lý.
Định nghĩa (Tổng bậc dộc lập) : Cho đồ thị G, với  , ta có :
 { là các đỉnh độc lập}
Thì :  được gọi là : tổng bậc độc lập.
Ví dụ : 
Ta có : n=12, Vậy
|
) nếu 
2,và mỗi đỉnh đó có đúng 2 cạnh liên thuộc nằm trên đường đi P.
theo chiều kim đồng hồ ta nhận được các chu trình, cũng là các cách xếp sau:
3) có (n
1)/2 chu trình Hamilton từng đôi một không giao nhau (tức là không có cạnh chung).
theo chiều kim đồng hồ ta nhận được k chu trình.
. Nếu bậc 
với mọi đỉnh v của G, thì G có chu trình Hamilton.
. Khi đó đồ thị W6 có chu trình Hamilton.
với mọi đỉnh v của G, thì G có đường đi Hamilton.
.Khi đó G có chu trình Hamilton khi và chỉ khi đồ thị G+(u,v) (đồ thị G thêm cạnh (u,v)) có chu trình Hamilton.
G”.
với mọi cặp đỉnh không kề nhau 
với mọi cặp đỉnh không kề nhau của đồ thị G. CMR: G có đường đi Hamilton.
thì đồ thị G có chu trình Hamilton.
. Nếu bậc 
với mọi đỉnh v của G, thì G có chu trình Hamilton.
như hình vẽ.
, do đó G có chu trình Hamilton.
1 2 3
.
u, v
ịnh lý 2.17 (Nash – Williams, 1971) : Cho G là đồ thị 2-liên thông, bậc n. Nếu 
thì G là đồ thị Hamilton.
suy ra : Đồ thị trên là đồ thị Hamilton.
và 2-liên thông thì G là đồ thị Hamilton.
a xét đồ thị 
(đồ thị bánh xe) sau đây :
thì G có chứa chu trình Hamilton.
= 2.
nên G có chu trình Hamilton với
thì G là đồ thị Hamilton.
thì G là đồ thị Hamilton.
. Khi đó, G là đồ thị Hamilton.
và 
thì G là đồ thị Hamilton.
= 8 (Tổng 2 bậc độc lập bé nhất bằng 8).