Xem mẫu
- Đồ thị Hamilton
Trần Vĩnh Đức
Ngày 11 tháng 3 năm 2016
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 24
- Đi vòng quanh thế giới
10.5 Euler
(a) (b)
FIGU
FIGURE 8 Hamilton’s “A Voyage Round the the “A
World” Puzzle. World
Because the author cannot supply each reader with a wooden solid w
will consider the equivalent question: Is there a circuit in the graph sho
CuuDuongThanCong.com passes through each vertex exactly once? This solves the puzzle because
https://fb.com/tailieudientucntt 3 / 24 th
- Con Mã đi trên bàn cờ
CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 24
- Con Mã đi trên bàn cờ 2
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 24
- Solution: G1 has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in G
be seen by noting that any circuit containing every vertex must contain the edge {a
but G2 does have a Hamilton path, namely, a, b, c, d. G3 has neither a Hamilton c
Ví dụ path, because any path containing all vertices must contain one of the ed
Hamilton
{e, f }, and {c, d} more than once.
Đồ thị nào dưới đây là nửa Hamilton?
a b a b a b g
e c
d c d c e f
G1 G2 G3
d
FIGURE 10 Three Simple Graphs.
CONDITIONS FOR THE EXISTENCE OF HAMILTON CIRCUITS Is there a
to determine whether a graph has a Hamilton circuit or path? At first, it might seem
should be an easy way to determine this, because there is a simple way to answer
question of whether a https://fb.com/tailieudientucntt
CuuDuongThanCong.com
graph has an Euler circuit. Surprisingly, there are no kno
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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 24
- Solution: G1 has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in G
be seen by noting that any circuit containing every vertex must contain the edge {a
but G2 does have a Hamilton path, namely, a, b, c, d. G3 has neither a Hamilton c
Ví dụ path, because any path containing all vertices must contain one of the ed
Hamilton
{e, f }, and {c, d} more than once.
Đồ thị nào dưới đây là Hamilton?
a b a b a b g
e c
d c d c e f
G1 G2 G3
d
FIGURE 10 Three Simple Graphs.
CONDITIONS FOR THE EXISTENCE OF HAMILTON CIRCUITS Is there a
to determine whether a graph has a Hamilton circuit or path? At first, it might seem
should be an easy way to determine this, because there is a simple way to answer
question of whether a https://fb.com/tailieudientucntt
CuuDuongThanCong.com
graph has an Euler circuit. Surprisingly, there are no kno
9 / 24
- raphs 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
FIGURE 11 Two Graphs That Do Not Have a H
MPLE 6 Show that neither graph displayed in Figure 11 has a
CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 24
- Ví dụ
Chứng minh rằng đồ thị đầy đủ Kn có chu trình Hamilton với mọi
n ≥ 3.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 24
- Ví dụ
Đồ thị sau có phải là Hamilton không?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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:
v1 v2 vn−1 vn
...
CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 24
- Chứng minh (tiếp)
▶ Giả sử v1 kề với k đỉnh là: vi1 , vi2 , · · · , vik và
2 = i1 < i2 < · · · < ik
▶ Đỉnh vn không thể kề với đỉnh vij −1 nào (2 ≤ j ≤ k) vì nếu
không sẽ tồn tại chu trình Hamilton:
v1 v2 vij −1 vij vn−1 vn
... ...
CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 24
- Chứng minh (tiếp)
v1 v2 vij −1 vij vn−1 vn
... ...
▶ Vậy vn không kề với ít nhất k đỉnh {vi1 −1 , vi2 −1 , . . . , vik −1 , }.
Tức là
deg(vn ) ≤ n − 1 − k
▶ Nhưng vậy thì
n ≤ deg(v1 ) + deg(vn ) ≤ k + (n − 1 − k) = n − 1 7
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 24
nguon tai.lieu . vn
