›
›

Giáo trình Toán rời rạc - Bài 11: Đồ thị Hamilton - Trần Vĩnh Đức

Download
Đồ thị Hamilton  
Trần Vĩnh Đức  
Ngày 11 tháng 3 năm 2016  
1 / 24  
Tài liệu tham khảo  
▶
Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, NXB ĐHQG Hà  
Nội, 2004.  
▶
▶
Douglas B. West. Introduction to Graph Theory. 2nd Edition,  
2000.  
K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch  
Tiếng Việt)  
2 / 24  
Đi vòng quanh thế giới  
(a)  
(b)  
3 / 24  
Con Mã đi trên bàn cờ  
4 / 24  
Con Mã đi trên bàn cờ 2  
5 / 24  
Định nghĩa (Đồ thị nửa Hamilton)  
▶
Một đường đi trong đồ thị G được gọi là đường đi Hamilton  
nếu nó chứa tất cả các đỉnh của G.  
▶
Một đồ thị được gọi là đồ thị nửa Hamilton nếu nó có đường  
đi Hamilton.  
Nói cách khác, đồ thị nửa Hamilton là đồ thị có đường đi bao  
trùm.  
6 / 24  
Ví dụ  
Đồ thị nào dưới đây là nửa Hamilton?  
g
a
b
a
b
a
b
c
e
c
d
c
d
e
f
G1  
G2  
G3  
d
7 / 24  
Định nghĩa (Đồ thị Hamilton)  
▶
Một chu trình trong đồ thị G được gọi là chu trình Hamilton  
nếu nó chứa tất cả các đỉnh của G.  
▶
Một đồ thị được gọi là đồ thị Hamilton nếu nó có chu trình  
Hamilton.  
Nói cách khác, đồ thị Hamilton là đồ thị có chu trình bao trùm.  
8 / 24  
Ví dụ  
Đồ thị nào dưới đây là Hamilton?  
g
a
b
a
b
a
b
c
e
c
d
c
d
e
f
G1  
G2  
G3  
d
9 / 24  
Ví dụ  
Đồ thị nào dưới là Hamilton? Nếu không, có là nửa Hamilton?  
a
d
e
a
d
c
b
c
b
e
G
H
10 / 24  
Ví dụ  
Chứng minh rằng đồ thị đầy đủ Kn có chu trình Hamilton với mọi  
n ≥ 3.  
11 / 24  
Mệnh đề  
Nếu G = (V, E) có chu trình Hamilton, vậy thì với mọi tập đỉnh  
khác rỗng S ⊆ V, đồ thị thu được từ G bằng cách xóa các đỉnh  
thuộc S chỉ có nhiều nhất |S| thành phần liên thông.  
Chứng minh.  
12 / 24  
Ví dụ  
Đồ thị sau có phải là Hamilton không?  
13 / 24  
Ví dụ  
Đồ thị sau đây chỉ ra rằng điều kiện cần trước không phải điều  
kiện đủ. Tại sao?  
14 / 24  
Bài tập  
Alice và Bob nhìn trộm đề thi Toán Rời Rạc của thầy Đức. Alice  
thấy thầy đang mô tả một đồ thị với 17 đỉnh và 129 cạnh; còn  
Bob thấy thầy hỏi xem đồ thị này có chu trình Hamilton không.  
- Bob nói rằng: ”không cần biết chi tiết đồ thị thầy đang vẽ thế  
nào, chắc chắn đồ thị này có chu trình Hamilton.”  
- Còn Alice nói: ”Nếu không biết chi tiết thì không thể quyết định  
được đồ thị này có chu trình Hamilton hay không.”  
Ai đúng, ai sai? Bạn hãy giải thích.  
15 / 24  
Định lý (Ore)  
Giả sử G là một đơn đồ thị với n ≥ 3 đỉnh thỏa mãn: với mọi cặp  
đỉnh không liền kề u và v, ta có  
deg(u) + deg(v) ≥ n,  
khi đó G là đồ thị Hamilton.  
16 / 24  
Chứng minh định lý Ore  
▶
Giả sử định lý không đúng.  
▶
Tồn tại đồ thị G = (V, E) với n đỉnh và có nhiều cạnh nhất  
thỏa mãn điều kiện của định lý Ore nhưng không là Hamilton.  
Tại sao?  
▶
▶
Vì G có nhiều cạnh nhất có thể nên đồ thị thu được bằng  
cách thêm một cạnh mới nối hai đỉnh không kề nhau phải có  
chu trình Hamilton chứa cạnh thêm đó. Tại sao?  
Vậy giữa hai đỉnh bất kỳ trong G có thể nối với nhau bằng  
một đường Hamilton.  
17 / 24  
Chứng minh (tiếp)  
▶
Vì đồ thị Kn có chu trình Hamilton nên G = Kn.  
̸
Vậy tồn tại hai đỉnh v1 và vn không kề nhau trong G,  
và tồn tại đường Hamilton:  
▶
▶
vn−1  
v1  
v2  
vn  
. . .  
18 / 24  
Chứng minh (tiếp)  
▶
Giả sử v1 kề với k đỉnh là: vi , vi , · · · , vi và  
1
2
k
2 = i1 < i2 < · · · < ik  
▶
Đỉnh vn không thể kề với đỉnh vi −1 nào (2 ≤ j ≤ k) vì nếu  
không sẽ tồn tại chu trình Hamiljton:  
v
ij−1  
v
ij  
vn−1  
v1  
v2  
vn  
. . .  
. . .  
19 / 24  
Chứng minh (tiếp)  
v
ij−1  
v
ij  
vn−1  
v1  
v2  
vn  
. . .  
. . .  
▶
▶
Vậy vn không kề với ít nhất k đỉnh {vi −1, vi −1, . . . , vi −1, }.  
1
2
k
Tức là  
deg(vn) ≤ n − 1 − k  
Nhưng vậy thì  
n ≤ deg(v1) + deg(vn) ≤ k + (n − 1 − k) = n − 1 ꢀ  
20 / 24  
Tải về để xem bản đầy đủ
pdf 24 trang Thùy Anh 18520 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 11: Đồ thị Hamilton - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_toan_roi_rac_bai_11_do_thi_hamilton_tran_vinh_duc.pdf