ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN NGỌC HẢI
LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP
LUẬN VĂN THẠC SĨ TOÁN HỌC
HÀ NỘI, NĂM 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN NGỌC HẢI
LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60 46 40
NGƯỜI HƯỚNG DẪN KHOA HỌC:
GS. TS. ĐẶNG HUY RUẬN
HÀ NỘI, NĂM 2014
Mục lục
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 Các khái niệm và định lý cơ bản 7
1.1 Các ví dụ về đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Biểu diễn đồ thị bằng hình học . . . . . . . . . . . . . . . . . . 12
1.4 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . . . . . 13
1.5 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Đồ thị và một số bài toán phổ thông 16
2.1 Bài toán liên quan đến bậc của đồ thị . . . . . . . . . . . . . . . 16
2.1.1 Bậc của đỉnh . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Nửa bậc . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Bài toán liên quan đến chu trình . . . . . . . . . . . . . . . . . 28
2.2.1 Xích, Chu trình . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2 Đường, Vòng . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 29
2.2.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Bài toán liên quan đến tính liên thông . . . . . . . . . . . . . . 38
2.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.2 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 39
2.3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3
2.4 Đồ thị Euler - Đồ thị Hamilton . . . . . . . . . . . . . . . . . . 50
2.4.1 Đường đi Euler và đồ thị Euler . . . . . . . . . . . . . . 50
2.4.2 Đường đi Hamilton và đồ thị Hamilton . . . . . . . . . . 55
2.4.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.5 Bài toán liên quan đến đồ thị tô màu . . . . . . . . . . . . . . . 70
2.5.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.5.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.5.3 Thuật toán tìm sắc số . . . . . . . . . . . . . . . . . . . 74
2.5.4 Lớp đồ thị có chu trình tam giác cùng màu . . . . . . . . 75
2.5.5 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.6 Bài toán về cây . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
2.6.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 85
2.6.2 Đặc điểm của cây và bụi . . . . . . . . . . . . . . . . . . 85
2.6.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Lời kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Mở đầu
Lý thuyết đồ thị (lý thuyết graph) là một ngành toán học hiện đại, một lĩnh
vực khá trẻ của toán học mặc dù những vấn đề của lý thuyết đồ thị đã có từ
vài trăm năm trước đây.
Những ý tưởng cơ bản về lý thuyết đồ thị được đưa ra vào năm 1736 bởi
nhà toán học Thụy Sĩ Leonhard Euler với bài toán nổi tiếng về 7 cây cầu ở
thành phố K¨onigsberg. Những công trình nghiên cứu về lý thuyết đồ thị gắn
liền với những tên tuổi các nhà toán học lớn như Euler, Hamilton,... Cuốn sách
giáo khoa đầu tiên về lý thuyết đồ thị được K¨onig viết và xuất bản tại Leipzig
năm 1936. Mãi 22 năm sau, cuốn sách giáo khoa thứ hai về đồ thị mới được ra
đời bởi nhà toán học Berge viết và in tại Paris.
Vả lại, do đặc trưng rất “gần gũi” với thực tế của mình, lý thuyết đồ thị
ngày càng khẳng định được vị trí quan trọng trong việc áp dụng để giải các
bài toán trong cuộc sống. Nó có nhiều ứng dụng quan trọng trong nhiều ngành
khoa học, kĩ thuật hiện đại: vật lý, hóa học, sinh học, tin học,... Ngày nay, lý
thuyết đồ thị đã trở thành một công cụ không thể thiếu được khi phải giải
quyết những vấn đề có tính chất phải xem xét cả tổng thể.
Được sự hướng dẫn tận tâm, sự chỉ bảo tận tình và những bài giảng tâm
huyết của NGND.GS.TS Đặng Huy Ruận. Tác giả xin đóng góp một phần nhỏ
tìm hiểu của bản thân về lý thuyết đồ thị qua luận văn: “Lý thuyết đồ thị và
ứng dụng để giải toán sơ cấp”.
Luận văn gồm phần mở đầu, kết luận, tài liệu tham khảo và 2 chương.
Chương 1. Các khái niệm và định lý cơ bản.
Chương 1 trình bày một số bài toán dẫn đến khái niệm đồ thị, một số khái
niệm và định lý hay dùng trong lý thuyết đồ thị. Các lý thuyết này đã được
GS.TS Đặng Huy Ruận tích lũy trong cuốn sách “Lý thuyết đồ thị và ứng
dụng” bao gồm:
- Khái niệm về lý thuyết đồ thị.
5
- Các cách biểu diễn đồ thị.
- Một số dạng đồ thị đặc biệt.
Chương 2. Đồ thị và một số bài toán phổ thông.
Chương 2 trình bày một số ứng dụng của lý thuyết đồ thị để giải quyết 6
dạng toán:
1. Các bài toán liên quan đến bậc của đồ thị.
2. Các bài toán liên quan đến chu trình.
3. Các bài toán liên quan đến đồ thị liên thông.
4. Các bài toán ứng dụng đồ thị Euler và đồ thị Hamilton.
5. Các bài toán ứng dụng đồ thị tô màu.
6. Các bài toán ứng dụng cây.
Tác giả xin bày tỏ lòng biết ơn sâu sắc đến NGND.GS.TS Đặng Huy Ruận,
người Thầy đã tận tình hướng dẫn, giúp đỡ tác giả trong suốt quá trình học
tập và hoàn thành luận văn. Kính chúc thầy mạnh khoẻ, hạnh phúc để thế hệ
học trò chúng con được học hỏi nhiều hơn nữa từ tấm gương của thầy.
Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo Sau đại
học, Khoa Toán - Cơ - Tin học, các thầy giáo, cô giáo và các bạn của seminar
“Phương pháp Toán sơ cấp” Trường Đại học Khoa học Tự nhiên - ĐHQGHN
đã giúp đỡ và góp ý cho luận văn được hoàn chỉnh.
Do trình độ còn hạn chế, chắc chắn luận văn không tránh khỏi thiếu sót.
Tác giả mong nhận được nhiều đóng góp từ các bạn đọc để luận văn được hoàn
thiện hơn.
Xin trân trọng cảm ơn.
Học viên
6
Nguyễn Ngọc Hải
Chương 1
Các khái niệm và định lý cơ bản
1.1 Các ví dụ về đồ thị
Ví dụ 1.1.1. Một đoàn khách du lịch đến Hà Nội và muốn đi thăm các danh
lam thắng cảnh của Hà Nội. Sơ đồ các danh lam thắng cảnh cũng như hệ thống
giao thông ở Hà Nội cho phép đi từ địa điểm này sang địa điểm khác được cho
theo sơ đồ ở hình 1.1. Trong đó các điểm biểu thị các nơi khách cần đến, các
đoạn thẳng biểu thị các con đường có thể đi được. Bạn hãy giao cho Công ty
du lịch Hà Nội lập hành trình sao cho khách có thể đi tới thăm mọi địa điểm,
mỗi địa điểm đi qua không quá một lần và chỉ đi theo các đường có trong sơ
Hình 1.1
đồ. Thêm vào đó con đường bắt đầu từ A và kết thúc ở K.
Theo sơ đồ thì đến C và E, mỗi điểm chỉ có hai con đường. Vì thế hành
trình thoả mãn yêu cầu bài toán phải đi đến bằng một đường và ra bằng con
đường còn lại. Do vậy một đoạn hành trình khi đến C phải là I → C → B
7
hoặc B → C → I. Tương tự hành trình qua E phải là B → E → F hoặc
F → E → B. Nhưng trong hành trình, mỗi địa điểm chỉ đi qua không quá một
lần nên một đoạn của hành trình phải là I → C → B → E → F hoặc ngược
lại F → E → B → C → I (hình 1.2).
Do con đường bắt đầu từ A nên một đoạn đầu của hành trình là A → I →
Hình 1.2
C → B → E → F .
Đoạn còn lại chỉ có thể là F → M → H → D → K.
Vậy hành trình phải tìm là:
A → I → C → B → E → F → M → H → D → K.
Từ lời giải suy ra rằng hành trình thoả mãn bài ra là duy nhất.
Ví dụ 1.1.2. Một mảnh giấy được xé làm 3 phần nhỏ. Đến lượt thứ hai ta lại
xé một vài mảnh giấy nhỏ, mỗi lần một mảnh giấy nhỏ được xé làm 3 phần
nhỏ hơn. Tiếp tục lặp lại quá trình đó. Chứng minh rằng, sau k (với k là số
nguyên dương) lần xé ta thu được số mảnh giấy là một số lẻ.
Ta biểu thị mỗi mảnh giấy như một dấu chấm chấm tròn. Sự kiện mỗi mảnh
giấy sau mỗi lần xé được thành ba mảnh, mô tả trên hình 1.3, trong đó dấu
chấm tròn đen biểu thị mảnh giấy ban đầu không còn nữa và dấu chấm tròn
trắng biểu thị các mảnh giấy nhận được.
Hình 1.3 giúp ta thấy rằng sau mỗi lần xé được thêm hai mảnh giấy (3
mảnh giấy mới thay cho mảnh giấy cũ) và một ví dụ cho 4 lần xé.
8
• Lượt thứ nhất xé mảnh ban đầu: được 3 mảnh giấy nhỏ.
Hình 1.3
• Lượt thứ hai xé 2 mảnh: được 7 mảnh giấy nhỏ.
• Lượt thứ ba xé 4 mảnh: được 15 mảnh giấy nhỏ.
• Lượt thứ tư xé 1 mảnh: được 17 mảnh giấy nhỏ.
Có được 17 dấu chấm tròn trắng, tương ứng 17 mảnh giấy được nhận.
Khi một mảnh giấy bị xé thành 3 mảnh giấy nhỏ hơn, ta thấy rằng mỗi
mảnh giấy mất đi ta được thêm 2 mảnh giấy mới. Cứ như vậy, sau k lần xé,
mất đi l mảnh giấy, ta được số mảnh giấy sẽ là: 2l + 1.
Vậy số mảnh giấy là một số lẻ.
Ví dụ 1.1.3. Có thể có một nhóm 5 người mà mỗi người quen đúng với hai
Hình 1.4
người khác trong nhóm hay không ?
Biểu thị mỗi một người là một điểm còn nếu hai người quen nhau thì ta nối
hai điểm tương ứng lại, nếu không quen nhau thì giữa hai điểm không được
9
nối.
Xét một ngũ giác thông thường trên hình 1.4. Rõ ràng mỗi đỉnh ngũ giác
được nối với đúng hai đỉnh khác. Vì thế có thể có 5 người mà mỗi người quen
với đúng hai người khác trong số 4 người còn lại.
Trong bài toán này có thể thay số 5 bởi một số tự nhiên n > 2 tuỳ ý. Lúc
đó tương ứng thay ngũ giác bởi đa giác n cạnh.
Tuy nhiên ta cũng có thể thử suy nghĩ xem có hay không một nhóm 5 người
mà mỗi người quen đúng với 3 người còn lại trong nhóm ?
Ví dụ 1.1.4. Hãy phân nhóm học tập cho lớp học sao cho những người trong
cùng một nhóm là bạn thân với nhau.
Chọn đỉnh của sơ đồ cần lập là những em học sinh trong lớp. Trong sơ đồ
biểu diễn, ta nối những cặp hai em học sinh thân nhau bằng một đoạn thẳng
(hoặc một đoạn cong).
Bằng cách như vậy, ta sẽ có một sơ đồ gồm các đỉnh (các em học sinh) và
các cạnh (các đường nối hai em khi và chỉ khi hai em này thân nhau).
Những mô hình quy về các tập đỉnh và các cạnh nối đỉnh là những đồ thị.
Ví dụ 1.1.5. Bẩy cây cầu ở thành phố K¨onigsberg năm 1736 (theo [1]).
Thành phố K¨onigsberg của nước Đức (bây giờ là thành phố Kaliningrad
của liên bang Nga) có dòng sông Pregel chảy qua, giữa sông có cù lao Kneiphof
Hình 1.5
và 7 cây cầu như Hình 1.5a
Từ khi xuất hiện 7 cây cầu, người dân ở đây đã đặt ra vấn đề: “Liệu có cách
nào đi qua được cả bẩy cây cầu và qua mỗi cây cầu đúng một lần được không
10
?”.
Đến năm 1736 nhà toán học Euler đã chứng minh bài toán trên không giải
được. Bằng cách dùng các đỉnh A, B, C, D để biểu thị các miền đất ở hai bên
cầu; các cây cầu được biểu thị bằng các cạnh nối giữa các đỉnh tương ứng với
các miền đất hai bên cầu. Euler đã chứng minh được rằng không thể vẽ tất cả
các cạnh của đồ thị Hình 1.5b bằng một nét bút. Từ đó, những đường một nét
trong lý thuyết đồ thị được mang tên ông.
Trong 5 ví dụ nói trên và nhiều bài toán khác, người ta thường dùng các
sơ đồ (hay hình vẽ) gồm các điểm và các đoạn nối các điểm này để giải toán,
hoặc làm sáng tỏ các lập luận, hoặc minh họa cho các tình huống. Đó là những
minh hoạ của đồ thị.
1.2 Định nghĩa đồ thị
Tập hợp X (cid:54)= ∅ các đối tượng và bộ E các cặp sắp thứ tự và không sắp
thứ tự các phần tử của X được gọi là một đồ thị, đồng thời được ký hiệu bằng
G(X, E) (hoặc bằng G = (X, E)) hoặc G(X).
Các phần tử của X được gọi là các đỉnh. Cặp đỉnh không sắp thứ tự được
gọi là cạnh, cặp đỉnh sắp thứ tự được gọi là cạnh có hướng hay cung.
Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng, đồ thị chỉ chứa các
cung được gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung được gọi
là đồ thị hỗn hợp hay đồ thị hỗn tạp.
Một cặp đỉnh có thể được nối với nhau bằng hai hoặc nhiều hơn hai cạnh
(hai hoặc nhiều hơn hai cung). Các cạnh (cung) này được gọi là các cạnh (cung)
bội.
Một cung (hoặc một cạnh) có thể bắt đầu và kết thúc tại cùng một đỉnh.
Cung (cạnh) này được gọi là khuyên.
Cặp đỉnh x, y được nối với nhau bằng cạnh (hoặc cung) a thì x, y được gọi
là các đỉnh hay hai đầu của cạnh (cung) a và a được gọi là cạnh (cung) thuộc
11
đỉnh x, đỉnh y.
Nếu cung b xuất phát từ đỉnh u và đi vào đỉnh v, thì u được gọi là đỉnh
đầu, còn v được gọi là đỉnh cuối của cung b.
Cặp đỉnh x, y được gọi là hai đỉnh kề nhau, nếu x (cid:54)= y và x, y là hai đầu
của cùng một cạnh hay một cung.
Đối với mọi đỉnh x, ta dùng D(x) để chỉ tập đỉnh, mà mỗi đỉnh này được nối với x bằng ít nhất một cạnh; D+(x) để chỉ tập đỉnh, mà mỗi đỉnh này từ x có cung đi tới; D−(x) để chỉ tập đỉnh, mà mỗi đỉnh này có cung đi tới x.
Hai cạnh (cung) a, b được gọi là kề nhau nếu:
1. Chúng khác nhau.
2. Chúng có đỉnh chung (nếu a, b là cung, thì không phụ thuộc vào đỉnh
chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh cuối của
cung b).
1.3 Biểu diễn đồ thị bằng hình học
Giả sử có đồ thị G(X, E).
Biểu diễn đỉnh: Lấy các điểm trên mặt phẳng hoặc trong không gian
tương ứng với các phần tử thuộc tập X và dùng ngay kí hiệu các phần tử này
để ghi tên các điểm tương ứng.
Biểu diễn cạnh: Nếu cạnh a với hai đỉnh đầu là x và y thì nó được biểu
diễn là bằng đoạn thẳng hay một đoạn cong nối giữa hai điểm x, y và không
đi qua các điểm tương ứng trung gian khác.
Biểu diễn cung: Nếu cung a có đỉnh đầu là x, đỉnh cuối là y, thì nó được
biểu diễn bằng một đoạn thẳng hoặc một đoạn cong được xác định hướng đi
từ x sang y và không đi qua các điểm tương ứng trung gian khác.
Hình nhận được gọi là dạng biểu diễn hình học của đồ thị G(X, E). Đôi khi
12
người ta cũng gọi dạng biểu diễn hình học là một đồ thị.
1.4 Một số dạng đồ thị đặc biệt
Trong trường hợp không cần phân biệt giữa cạnh và cung ta quy ước dùng
cạnh thay cho cả cung.
Đồ thị G(X, E) không có khuyên và mỗi cặp đỉnh được nối với nhau bằng
không quá một cạnh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường
được gọi là đồ thị.
Đồ thị G(X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với
nhau bằng từ hai cạnh trở lên được gọi là đa đồ thị.
Đồ thị vô hướng (hoặc có hướng) G(X, E) được gọi là đồ thị - đầy đủ, nếu
mỗi cặp đỉnh được nối với nhau bằng đúng một cạnh (hoặc một cung với chiều
tùy ý).
Đồ thị vô hướng (hoặc có hướng) G(X, E) được gọi là đồ thị k - đầy đủ,
nếu mỗi cặp đỉnh được nối với nhau bằng đúng k cạnh (hoặc k cung với chiều
tùy ý).
Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) hai mảng, nếu tập
đỉnh X của nó được phân thành hai tập con rời nhau X1, X2 (với X1 ∪ X2 = X và X1 ∩ X2 = ∅) và mỗi cạnh đều có một đầu thuộc X1, còn đầu kia thuộc X2. Khi đó G(X, E) còn được ký hiệu bằng G(X1, X2, E).
Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) phẳng, nếu nó có
ít nhất một dạng biểu diễn hình học trải trên một mặt phẳng nào đó, mà các
cạnh của đồ thị chỉ cắt nhau ở đỉnh.
Đồ thị (đa đồ thị) G(X, E) được gọi là đồ thị (đa đồ thị) hữu hạn, nếu số
đỉnh của nó hữu hạn, nghĩa là tập X có lực lượng hữu hạn.
Đồ thị (đa đồ thị) với tập đỉnh vô hạn, được gọi là đồ thị (đa đồ thị) vô
hạn.
Đồ thị (đa đồ thị) với số cạnh thuộc mỗi đỉnh đều hữu hạn được gọi là đồ
thị (đa đồ thị) hữu hạn địa phương.
Trong các phần tiếp theo, nếu chúng tôi không chú ý gì thêm, thì các đồ
13
thị, đa đồ thị được xét đều hữu hạn.
Cho Y ⊆ X, Y (cid:54)= ∅; H ⊆ E, F = E ∩ (Y × Y ); V = (X × X)/E với
X × X = {(x, y) : x, y ∈ X}; Y × Y = {(x, y) : x, y ∈ Y ⊆ X}.
Đồ thị G1(Y, F ) được gọi là đồ thị con, còn đồ thị G2(X, H) được gọi là đồ
thị bộ phận của đồ thị G(X, E).
Đồ thị G(cid:48)(X, V ) được gọi là đồ thị bù của đồ thị G(X, E).
Đồ thị có hướng G(X, E) được gọi là đồ thị đối xứng, nếu
∀ x, y ∈ X : (x, y) ∈ E ⇒ (y, x) ∈ E.
Trong đồ thị đối xứng tùy ý hai đỉnh kề nhau x, y luôn được nối bằng hai
cung ngược chiều nhau. Để đơn giản, trong trường hợp này ta quy ước thay
hai cung nói trên bằng một cạnh nối giữa x và y.
Đồ thị có hướng G(X, E) được gọi là đồ thị phản đối xứng, nếu
∀ x, y ∈ X : (x, y) ∈ E ⇒ (y, x) /∈ E.
1.5 Phương pháp đồ thị
Về thực chất, phương pháp đồ thị là cách giải toán thông qua công cụ trung
gian là đồ thị. Phương pháp đồ thị bao gồm 3 bước:
Bước 1 : Xây dựng đồ thị (G) mô tả toàn bộ quan hệ được cho trong bài toán
T
• Đỉnh: Lấy các điểm trên mặt phẳng hoặc trong không gian tương ứng
với các đối tượng được cho trong bài toán. Dùng ngay tên các đối tượng
để ghi trên các điểm tương ứng.
• Cạnh: Hai đỉnh x, y tùy ý được nối bằng một cạnh (hay cung) khi và chỉ
khi hai đối tượng x, y có một quan hệ tương ứng nào đó.
Đồ thị G mô tả toàn bộ các quan hệ được cho trong bài toán T . Lúc này
bài toán T đã được phát biểu dưới dạng tính chất của đồ thị.
Bước 2 : Căn cứ vào đồ thị G, trên cơ sở các kết quả của lý thuyết đồ thị, mà
14
ta suy ra đáp án của bài toán T bằng ngôn ngữ đồ thị.
Bước 3 : Căn cứ vào sự đặt tương ứng, đặc thù của cạnh và cung mà “dịch” đáp
15
án từ ngôn ngữ đồ thị sang ngôn ngữ thông thường.
Chương 2
Đồ thị và một số bài toán phổ thông
2.1 Bài toán liên quan đến bậc của đồ thị
2.1.1 Bậc của đỉnh
Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng hoặc không có hướng.
Số cạnh và cung thuộc đỉnh x được gọi là bậc của đỉnh x và ký hiệu bằng m(x).
Đỉnh có bậc bằng 0 được gọi là đỉnh biệt lập.
Đỉnh có bậc bằng 1 được gọi là đỉnh treo.
Cạnh (cung) có ít nhất một đầu là đỉnh treo được gọi là cạnh (cung) treo.
2.1.2 Nửa bậc
Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng.
Số cung đi vào đỉnh x được gọi là nửa bậc vào của đỉnh x và ký hiệu bằng
m(cid:48)(x) hoặc bằng m−(x).
Số cung đi ra khỏi đỉnh x được gọi là nửa bậc ra của đỉnh x và ký hiệu bằng
m(cid:48)(cid:48)(x) hoặc bằng m+(x).
Ký hiệu tập cung đi vào đỉnh x bằng E−(x), tập cung đi ra khỏi đỉnh x
16
bằng E+(x).
2.1.3 Một số tính chất
Một số kết quả nhận được từ [5] như sau:
Định lý 2.1.1. Trong một đồ thị hay đa đồ thị tùy ý, tổng số bậc của tất cả
các đỉnh bao giờ cũng gấp đôi số cạnh.
Định lý 2.1.2. Trong một đồ thị hay đa đồ thị tùy ý, số đỉnh bậc lẻ luôn luôn
là một số chẵn.
Chứng minh.
Giả sử đồ thị (đa đồ thị) G(X, E) có n đỉnh, m cạnh
X = {x1, x2, x3, . . . , xk, xk+1, . . . , xn−1, xn},
các đỉnh x1, x2, . . . , xk bậc lẻ và xk+1, . . . , xn−1, xn bậc chẵn.
Theo định lý 2.1.1 ta có đẳng thức:
= 2m. (cid:124) m(x1) + m(x2) + . . . + m(xk) (cid:124) (cid:123)(cid:122) (cid:125) A + m(xk+1) + . . . + m(xn−1) + m(xk) (cid:123)(cid:122) (cid:125) B
Vì B là tổng của các số chẵn nên B là một số chẵn. Do đó A = 2m − B là một
số chẵn.
Số A là tổng của k số lẻ nên k phải là số chẵn. Bởi vậy, số đỉnh bậc lẻ trong
đồ thị hay đa đồ thị bất kỳ phải là một số chẵn.
(cid:3)
Định lý 2.1.3. Trong một đồ thị với n (n (cid:62) 2) đỉnh có ít nhất 2 đỉnh cùng
bậc.
Chứng minh.
Giả sử đồ thị G(X, E) có n đỉnh với n (cid:62) 2. Ta xét 2 khả năng:
1) Nếu đồ thị có đỉnh bậc 0:
Khi đó trong đồ thị không có một đỉnh nào kề với tất cả các đỉnh còn lại,
nên mỗi đỉnh của đồ thị có bậc là một trong n − 1 số nguyên: 0, 1, ..., n − 2.
17
2) Nếu đồ thị có đỉnh bậc n − 1:
Khi đó đồ thị không có đỉnh bậc 0. Do đó, bậc của mỗi đỉnh thuộc đồ thị
là một trong n − 1 số nguyên: 1, ..., n − 2, n − 1.
Từ kết quả lý luận trên khẳng định được rằng, đồ thị G(X, E) với n đỉnh,
nhưng chỉ có không quá n − 1 loại bậc. Bởi vậy, phải có ít nhất 2 đỉnh cùng
bậc.
(cid:3)
Định lý 2.1.4. Nếu đồ thị với n (n > 2) đỉnh có đúng 2 đỉnh cùng bậc thì hai
đỉnh này không thể đồng thời có bậc 0 hoặc n − 1.
Chứng minh.
Với n = 3, định lý hiển nhiên đúng.
Ta xét với n (cid:62) 4.
Giả sử là hai đỉnh cùng bậc của đồ thị G(X, E) và đều có bậc 0 hoặc bậc
n − 1. Loại x, y và tất cả các cạnh thuộc chúng khỏi đồ thị G, ta được đồ thị
con G1 có n − 2 đỉnh. Theo định lý 2.1.3, trong G1 có hai đỉnh cùng bậc, giả
sử là u, v.
1) Nếu x, y cùng bậc 0 thì u, v trong G không kề với x, y nên u, v đồng thời
là hai đỉnh cùng bậc trong đồ thị G. Như vậy, đồ thị G phải có ít nhất 2 cặp
đỉnh cùng bậc.
2) Nếu x, y cùng bậc n − 1. Khi đó mỗi đỉnh u, v đều kề đồng thời với x, y
nên trong đồ thị G các đỉnh u, v cũng cùng bậc . Như vậy, đồ thị G phải có ít
nhất 2 cặp đỉnh cùng bậc.
Cả hai trường hợp đều dẫn tới mâu thuẫn với tính chất: đồ thị G có duy
nhất một cặp đỉnh cùng bậc nên x, y không thể cùng bậc 0 hoặc bậc n − 1.
Khẳng định được chứng minh.
(cid:3)
Định lý 2.1.5. Số đỉnh bậc n − 1 trong đồ thị G với n (n (cid:62) 4) đỉnh, mà 4
đỉnh tùy ý có ít nhất một đỉnh kề với 3 đỉnh còn lại, không nhỏ hơn n − 3.
Chứng minh.
18
1) Nếu G đầy đủ thì khẳng định là hiển nhiên.
2) Nếu G có cặp đỉnh duy nhất không kề nhau. Khi đó trong G có n − 2
đỉnh bậc n − 1.
3) Nếu G có 2 cặp đỉnh không kề nhau.
Khi đó, 2 cặp đỉnh này phải có đỉnh chung. Thật vậy, giả sử A, B; I, D là
hai cặp đỉnh không kề nhau. Nếu hai cặp đỉnh này không có đỉnh chung thì
trong 4 đỉnh A, B, I, D không có đỉnh nào kề với 3 đỉnh còn lại, như vậy mâu
thuẫn với giả thiết. Do đó, hai cặp A, B; I, D phải có hai đỉnh trùng nhau, giả
sử là B ≡ I.
Lấy đỉnh C tùy ý khác A, B, D. Trong bộ bốn đỉnh A, B, C, D đỉnh C kề
với cả 3 đỉnh A, B, D
Loại D ra khỏi bộ bốn đỉnh trên và thay vào đó là đỉnh E tùy ý khác với
A, B, C, D. Trong bộ bốn đỉnh A, B, C, E hoặc C hoặc E phải kề với 3 đỉnh
còn lại, nếu E kề với 3 đỉnh còn lại thì C kề với E. Do đó C kề với cả 3 đỉnh
A, B, E.
Do E là đỉnh tùy ý trong n − 4 đỉnh còn lại (khác A, B, C, D), nên C có
bậc n − 1.
C là đỉnh tùy ý trong n − 3 đỉnh khác A, B, D nên đồ thị có n − 3 đỉnh bậc
n − 1. Khẳng định được chứng minh.
(cid:3)
Định lý 2.1.6. Với mọi số tự nhiên n (n > 2), luôn tồn tại đồ thị n đỉnh mà
3 đỉnh bất kì của đồ thị đều không cùng bậc.
Chứng minh.
1) Với n = 3 đồ thị G3 gồm một đỉnh bậc 0 và hai đỉnh bậc 1.
2) Giả sử khẳng định đúng với đồ thị Gn có n đỉnh.
Đồ thị Gn+1 được xây dựng như sau:
a) Nếu Gn có đỉnh bậc n − 1. Khi đó Gn không có đỉnh bậc 0. Nếu ta ghép
vào Gn đỉnh x bậc 0 và được Gn+1 gồm n + 1 đỉnh. Việc ghép thêm đỉnh x vẫn
bảo toàn tính chất của Gn: ba đỉnh bất kỳ đều không cùng bậc và đồ thị Gn
19
không có đỉnh bậc 0, nên trong Gn+1 ba đỉnh bất kỳ đều không cùng bậc.
b) Nếu Gn không có đỉnh bậc n − 1. Khi đó tất cả các đỉnh của Gn đều có
bậc không vượt quá n − 2. Nếu ta ghép vào Gn đỉnh x (không thuộc Gn) và
nối x với từng đỉnh của Gn bằng một cạnh, được Gn+1 gồm n + 1 đỉnh. Đỉnh x
có bậc bằng n, còn bậc của mỗi đỉnh thuộc Gn trong Gn+1 được tăng thêm 1
đơn vị, nhưng đều không vượt quá n − 1 và trong bậc mới ba đỉnh bất kỳ của
Gn vẫn không cùng bậc.
Khẳng định được chứng minh.
(cid:3)
Định lý 2.1.7. Đồ thị hai mảng G(Y, Z; E) với mọi đỉnh y ∈ Y đều có m(y) (cid:62)
1, đồng thời có tính chất: bất kỳ hai cặp đỉnh y1, y2 ∈ Y ; z1, z2 ∈ Z nào cũng thỏa
mãn điều kiện: Nếu y1 kề với z1, y2 kề với z2 thì trong hai cặp đỉnh y1, z2; y2, z1
có ít nhất một cặp đỉnh kề nhau. Khi đó trong tập Z có ít nhất một đỉnh kề với
tất cả các đỉnh thuộc Y .
Chứng minh.
Ký hiệu |Y | = m, |Z| = n. Xét ba khả năng có thể xảy ra:
1) m = 1: Do Y có phần tử duy nhất y, mà m(y), nên trong tập Z có ít
nhất phần tử z kề với y. Bởi vậy m(z) = 1 = |Y |.
2) m > 1, n = 1, theo giả thiết, với mọi y ∈ Y đều có m(y) (cid:62) 1, nên đỉnh z
duy nhất của tập Z phải kề với tất cả cá đỉnh thuộc Y hay m(z) = |Y |.
3) m > 1, n > 1. Gọi z là đỉnh có bậc lớn nhất trong tập Z.
a) Nếu m(z) = |Y |, khẳng định được chứng minh.
b) Giả sử m(z) = k < m = |Y |. Ký hiệu y1, y2, . . . , yk là các đỉnh kề với z và
yk+1 phải kề với đỉnh t ∈ Z và t (cid:54)= z.
Xét hai cặp đỉnh (z, yi), (t, yk+1) với i = 1, 2, . . . , k ⇒ t kề với y1, y2, . . . , yk.
Ngoài ra t còn kề với yk+1 nên m(t) = k + 1 > k = m(z). Điều này mâu thuẫn
với m(z) cực đại.
Khẳng định được chứng minh.
(cid:3)
Định lý 2.1.8. Trong đồ thị G(X, E) với ít nhất kn + 1 đỉnh, mỗi đỉnh có bậc
20
không nhỏ hơn (k − 1)n + 1, luôn tồn tại một đồ thị con đầy đủ gồm k + 1 đỉnh.
Chứng minh.
Khẳng định được chứng minh bằng quy nạp theo k như sau:
1) Với k = 1, khẳng định hiển nhiên đúng.
2) Với k = 2 có thể làm chặt hơn giả thiết: Nếu đồ thị có 2n + 1 đỉnh, mà mỗi
đỉnh có bậc không nhỏ hơn n + 1 thì nó có đồ thị con đầy đủ gồm 3 đỉnh.
Thật vậy, xét đỉnh x tùy ý, còn y là một trong những đỉnh kề với x. Tổng số
đỉnh kề với x và y không nhỏ hơn 2n, nhưng số đỉnh khác x và y chỉ là 2n − 1.
Vậy phải có ít nhất một đỉnh z được tính 2 lần. Khi đó x, y, z tạo thành một
đồ thị con đầy đủ gồm 3 đỉnh.
3) Giả sử khẳng định đúng với k. Ta cần chỉ ra tính đúng đắn của khẳng định
với k + 1.
Theo giả thiết, trong đồ thị G gồm (k + 1)n + 1 đỉnh, số đỉnh kề với đỉnh x
tùy ý không nhỏ hơn kn + 1, nên số đỉnh của G không kề với x sẽ không vượt
quá n. Bởi vậy, mỗi đỉnh y kề với x, thì nó sẽ kề với nhiều nhất n đỉnh không
kề với đỉnh x. Do đó đỉnh y phải kề với ít nhất kn + 1 − n = (k − 1)n + 1 đỉnh
kề với x. Xét đồ thị con G1 gồm các đỉnh kề với x. Đồ thị con G1 gồm ít nhất
kn + 1 đỉnh và mỗi đỉnh của nó kề với ít nhất (k − 1)n + 1 đỉnh thuộc G1, nên
theo giả thiết quy nạp, trong G1 có đồ thị con đầy đủ G2 gồm k + 1 đỉnh. Vì
đỉnh x kề với từng đỉnh thuộc G2, nên đỉnh x kết hợp với các đỉnh thuộc G2
lập thành một đồ thị đầy đủ gồm k + 2 đỉnh trong đồ thị G.
Khẳng định được chứng minh.
(cid:3)
2.1.4 Ứng dụng
Bài toán 2.1.1. (xem [2]) Một tổ học sinh lớp 10 chuyên toán có 11 học sinh.
Buổi họp đầu tiên của tổ vào dịp đầu năm học. Bạn tổ trưởng đã phát hiện ra
điều thú vị rằng mỗi bạn trong tổ đã quen đúng 3 bạn khác. Ngay lập tức bạn
Chi đứng lên bác bỏ phát hiện đó. Vậy trong hai bạn ai nói đúng? Vì sao?
Giải.
21
Đưa bài toán trên về ngôn ngữ đồ thị, trong đó các đỉnh của đồ thị tương
ứng với các bạn học sinh, cụ thể có 11 học sinh đặt tương ứng với 11 đỉnh của
đồ thị; nếu hai bạn quen nhau nối 2 đỉnh tương ứng bởi 1 cạnh.
Theo giả thiết của bài toán ta thấy mỗi học sinh đều có quan hệ quen với 3
bạn khác điều đó ứng với trong đồ thị tại mỗi đỉnh đều có cạnh nối tới 3 đỉnh
khác hay tất cả các đỉnh đều có bậc 3.
Trong đồ thị đó, ta thấy mỗi đỉnh của đồ thị đều có bậc là 3 (do theo bài
toán mỗi bạn đều quen đúng 3 bạn).
Theo định lý 2.1.1, số cạnh của đồ thị là = 16, 5. Vô lý. 33 2
Vậy phát hiện của bạn tổ trưởng về số người quen của mỗi bạn trong tổ là
sai. Do đó, bạn Chi nói đúng.
Hình 2.1
Hình 2.1 mô tả bài toán
Bài toán 2.1.2. (xem [6]) Trong giải thi đấu bóng đá theo thể thức đấu vòng
tròn có 29 đội tham gia. Chứng tỏ rằng tại mỗi thời điểm luôn có một đội đã
đấu ở trong giải được một số chẵn trận hoặc chưa đấu trận nào.
Giải.
Đưa bài toán về ngôn ngữ đồ thị, trong đó các đỉnh của đồ thị tương ứng
với các đội bóng, có 29 đội bóng tương ứng với 29 đỉnh của đồ thị; ta nối hai
22
đỉnh của đồ thị bằng một cạnh nếu hai đội bóng tương ứng đã đấu với nhau.
Nếu giả sử không có đội bóng nào đấu một số chẵn trận thì tất cả các đỉnh
trong 29 đỉnh của đồ thị đã cho đều có bậc lẻ. Điều này mâu thuẫn với định lý
2.1.2. Điều giả sử là sai.
Vậy tại mỗi thời điểm luôn có một đội đã đấu ở trong giải được một số chẵn
trận, kể cả đội chưa đấu trận nào.
Bài toán 2.1.3. Trong phòng có 6 người chứng minh rằng tồn lại 3 người đôi
một quen nhau hoặc đôi một không quen nhau.
Giải.
Đưa bài toán về ngôn ngữ đồ thị, trong đó các đỉnh của đồ thị tương ứng
với một trong sáu người; ta dùng một đoạn thẳng nối giữa các đỉnh thể hiện
sự quen nhau và dùng đoạn nối nét đứt giữa các đỉnh thể hiện sự không quen
giữa hai người.
Bây giờ ta xét 6 điểm O, A, B, C, D, E lấy O làm tâm. Trong 5 điểm còn
lại, ta thấy 2 người bất kì hoặc là quen nhau, hoặc là không quen nhau.
Theo nguyên lí Dirichlet thì tồn tại ít nhất 3 đoạn thẳng nét liền hoặc 3
đoạn thẳng nối nét đứt từ O đến 5 điểm A, B, C, D, E.
Giả sử OA, OB, OC là các nét liền.
Từ A lại tiếp tục nối với B và C.
- Nếu AB, hoặc AC là các nét liền, ta có điều phải chứng minh.
- Nếu AB và AC là các nét đứt. Khi đó, BC là nét liền hoặc nét đứt ta đều
có điều phải chứng minh.
Vậy luôn tìm được 3 người đôi một quen nhau hoặc không quen nhau.
Bài toán 2.1.4. (xem [6]) Có 17 đội bóng đá gặp nhau trong một đợt tranh
giải theo thể thức thi đấu vòng tròn nghĩa là hai đội bất kỳ phải gặp nhau
đúng một trận. Chứng tỏ rằng tại một thời điểm bao giờ cũng có ít nhất hai
đội đã thi đấu trong giải có cùng một số trận.
Giải.
Đánh số các đội bóng theo thứ tự từ 1 đến 17. Biểu thị các đội bóng tham
23
dự giải trong đồ thị G có 17 đỉnh x1, x2, . . . , x17 như sau:
- Đội bóng đánh số i cho tương ứng đỉnh xi.
- Tại thời điểm nào đó nếu hai đội bóng thứ i và thứ j đã gặp nhau thì ta
nối xixj làm một cạnh đồ thị.
Rõ ràng tại mỗi thời điểm ta có một đồ thị 17 đỉnh.
Theo định lý 2.1.3, luôn tồn tại ít nhất 2 đỉnh cùng bậc. Nghĩa là, tại mỗi
thời điểm luôn có ít nhất 2 đội đấu cùng một số trận.
Bài toán 2.1.5. Chín người chơi cờ gặp nhau trong một lần thi đấu theo thể
thức đấu vòng tròn. Tại thời điểm nào đó có đúng hai người đã đấu được cùng
một số trận. Chứng tỏ rằng tại thời điểm đó hoặc có đúng một người chưa chơi
một trận nào, hoặc có đúng một người đã chơi tất cả mọi trận của mình.
Giải.
Đưa bài toán trên về ngôn ngữ đồ thị, trong đó đỉnh của đồ thị là người
chơi cờ, còn mỗi cạnh tương ứng với hai người chơi đã gặp nhau. Từ điều kiện
bài toán suy ra rằng đồ thị 9 đỉnh đó có đúng hai đỉnh cùng bậc.
Ta cần chứng minh rằng, đồ thị 9 đỉnh đó hoặc có một đỉnh bậc 0, hoặc
một đỉnh bậc 8.
Trong đồ thị, bậc của mỗi đỉnh là một trong các số nguyên: 0, 1, 2, 3, 4, 5,
6, 7, 8. Vì có đúng hai đỉnh A và B cùng bậc nên mọi đỉnh còn lại có bậc khác
nhau.
Theo định lý 2.1.4, hai đỉnh A và B không thể có cùng bậc 0 hoặc cùng bậc
8. Suy ra m(A) = m(B) = a với a là một số nguyên nằm giữa 1 và 7.
Trong 7 đỉnh còn lại nếu không có đỉnh nào bậc 0 hoặc bậc 8 thì suy ra 7
đỉnh còn lại chỉ nhận 6 giá trị về bậc từ 1 đến 7 (trừ ra giá trị a). Do vậy, ắt
có hai đỉnh khác nhau cùng bậc. Vô lý.
Do đó đồ thị có đúng một đỉnh bậc 0, hoặc một đỉnh bậc 8. Bài toán được
giải.
Bài toán 2.1.6. Trong số các học sinh chuyên toán của Trường THPT Chuyên
24
KHTN, mỗi nam sinh đều quen với ít nhất một nữ sinh. Với bất kì hai nữ sinh
x, y và nam sinh a, b trong trường luôn thỏa mãn điều kiện: nếu cặp x, a quen
nhau và cặp y, b quen nhau thì ít nhất một trong hai cặp x, b; y, a quen nhau.
Chứng minh rằng có ít nhất một nữ sinh quen với tất cả các nam sinh.
Giải.
Đưa bài toán trên về ngôn ngữ đồ thị, trong đó đỉnh của đồ thị là học sinh
của trường, còn mỗi cạnh tương ứng với hai bạn nam, nữ quen nhau. Từ điều
kiện bài toán ta có một đồ thị hai mảng G(Y, Z; E) với Y là tập hợp các đỉnh
biểu diễn cho các nam sinh, Z là tập hợp các đỉnh biểu diễn cho các bạn nữ
sinh, E là tập các cạnh của đồ thị mô tả sự quen biết giữa hai bạn khác giới
trong trường.
Theo định lý 2.1.7, trong tập Z có ít nhất một đỉnh kề với tất cả các đỉnh
thuộc Y . Vì vậy, có ít nhất một nữ sinh quen với tất cả các nam sinh.
Bài toán được chứng minh.
Bài toán 2.1.7. Trong Lễ kỉ niệm 55 năm thành lập Khoa Toán – Cơ – Tin
học, Trường ĐHKHTN, có 5001 đại biểu tham dự. Biết mỗi đại biểu có số
người quen không nhỏ hơn 4001 người. Chứng minh rằng, luôn tồn tại một bộ
6 đại biểu mà các đại biểu quen nhau từng đôi một.
Giải.
Đưa bài toán trên về ngôn ngữ đồ thị, trong đó mỗi đỉnh của đồ thị biểu
diễn cho 1 đại biểu, còn mỗi cạnh tương ứng với hai đại biểu quen nhau.
Từ điều kiện bài toán ta có một đồ thị G gồm 5001 đỉnh mà mỗi đỉnh có
bậc không nhỏ hơn 4001.
Theo định lý 2.1.8, với n = 1000, k = 5, đồ thị G luôn tồn tại một đồ thị
con đầy đủ gồm 6 đỉnh. Như vậy, luôn tồn tại một bộ 6 đại biểu mà các đại
biểu quen nhau từng đôi một.
Bài toán được giải.
Bài toán 2.1.8. (xem [5]) Chứng minh rằng: Trong n - giác lồi G, không tồn
tại tập U chứa hơn n cạnh hay đường chéo, sao cho 2 đoạn bất kỳ trong U đều
25
có điểm chung.
Giải.
Giả sử trong G chọn được tập U gồm k cạnh hay đường chéo, sao cho hai
đoạn bất kỳ trong chúng đều có điểm chung. Cần chứng minh k (cid:54) n.
Coi mỗi đỉnh của G là một đỉnh của đồ thị. Hai đỉnh là kề nhau, nếu chúng
là đầu mút của một đoạn thuộc U . Ta cũng nói đỉnh x có bậc i nếu x kề với i
đỉnh khác. Ký hiệu mi là số đỉnh bậc i (i = 1, 2, ...). Ta có
(2.1) n = m0 + m1 + m2 + . . . nên m1 + m2 + . . . (cid:54) n.
Xét đỉnh x bậc i > 2 và D(x) gồm các đỉnh x1, x2, . . . , xi. Không giảm tính
tổng quát, có thể coi (x, x1); (x, xi) là các cạnh của đồ thị tương ứng với cạnh
hay đường chéo ngoài cùng của G trong i cạnh nói trên. Khi đó đỉnh xj với
1 < j < i, có bậc 1 (vì bất kỳ cạnh hay đường chéo (xj, y) nào, với y khác x,
đều không có điểm chung với một trong hai cạnh (x, x1) hoặc x, xj, nghĩa là
(xj, y) không thuộc U ). Do vậy mỗi đỉnh bậc i > 2 kề với ít nhất i − 2 đỉnh bậc
1, suy ra, mi đỉnh bậc i (i = 3, 4, ...) kề với không ít hơn (i − 2)mi đỉnh bậc
1. Mặt khác, nếu x và x là hai đỉnh khác nhau, thì không thể kề với cùng một
đỉnh bậc 1, nghĩa là các đỉnh bậc 1 kề với các đỉnh bậc i đôi một khác nhau.
Ta có bất đẳng thức sau:
(2.2) m1 (cid:62) m3 + 2m4 + 3m5 + . . .
Mỗi cạnh gồm 2 đầu mút, nên k cạnh thuộc U có 2k đầu mút, mỗi đỉnh bậc i
kề với i đỉnh trong 2k đỉnh này nên ta có:
(2.3) 2k = m1 + 2m2 + 3m3 + . . .
Từ (2.1), (2.2), (2.3) suy ra:
2k = m1 + 2m2 + 3m3 + . . .
= (m1 + m2 + m3 + . . .) + (m2 + 2m3 + 3m4 + . . .) (cid:54) (m1 + 2m2 + 2m3 + . . .) + m1 = 2(m1 + m2 + m3 + . . .) (cid:54) 2n.
26
Ta có k (cid:54) 2n. Đó là điều phải chứng minh.
Bài toán 2.1.9. Cho 2n điểm A1, A2, A3, . . . , A2n (n > 1) trong không gian không có 3 điểm nào thẳng hàng. Gọi M là tập hợp gồm n2 + 1 đoạn thẳng có
đầu mút tại các điểm đã cho. Chứng minh rằng:
1. Có ít nhất một tam giác có đỉnh tại những điểm Ar, As, At nào đó và các
cạnh đều thuộc M . 2. Nếu số phần tử của M không vượt quá n2 thì có thể không tồn tại một tam
giác như vậy.
Giải.
Chứng minh bằng quy nạp theo n:
Nếu trong đồ thị có 2n đỉnh không có ba cạnh nào lập thành một tam giác
thì số cạnh của đồ thị không vượt quá n2.
Mệnh đề trên đúng với n = 1, vì lúc đó đồ thị có 2 đỉnh và số cạnh không
vượt quá 1 = n2.
Giả sử mệnh đề đúng với k, ta chứng minh nó cũng đúng với k + 1.
Thật vậy, xét một đồ thị G có 2(k + 1) đỉnh, trong đó không có ba cạnh nào
Hình 2.2
lập thành một tam giác. Ta lấy một cạnh bất kỳ của G gọi cạnh đó là AB.
Mỗi đỉnh trong 2k đỉnh còn lại chỉ có thể nối nhiều nhất là một trong hai
đỉnh A, B (vì trong G không có tam giác nào) do đó số cạnh trong G có đỉnh
tại A hoặc B nhiều nhất là 2k + 1 (kể cả AB).
Theo giả thiết quy nạp, đồ thị với 2k đỉnh (trong đó không có 3 cạnh nào
lập thành một tam giác) có không quá k2 cạnh.
27
Vậy đồ thị G có nhiều nhất là: 1 + 2k + k2 = (k + 1)2 cạnh.
Điều phải chứng minh. Trong trường hợp G có số cạnh không lớn hơn n2: Xét hai tập hợp con rời
nhau M1, M2 mỗi tập này chứa không quá n phần tử. Mỗi đỉnh thuộc M1 nối
Hình 2.3
với các đỉnh thuộc M2 và ngược lại.
Ta có đồ thị với số cạnh không lớn hơn n2 và không có ba cạnh nào lập
thành một tam giác. Điều phải chứng minh.
2.2 Bài toán liên quan đến chu trình
2.2.1 Xích, Chu trình
Giả sử G(X, E) là một đồ thị hay đa đồ thị vô hướng.
Dãy α các đỉnh của G(X, E):
α = [x1, x2, . . . , xi, xi+1, . . . , xn−1, xn]
được gọi là một xích hay một dây chuyền, nếu ∀i (i (cid:54) i (cid:54) n − 1) cặp đỉnh
xi, xi+1 kề nhau.
Tổng số vị trí của tất cả các cạnh xuất hiện trong xích α được gọi là độ dài
xích α, đồng thời được ký hiệu bằng |α|.
Các đỉnh x1, xn được gọi là hai đỉnh đầu của xích α. Ngoài ra, còn nói rằng
xích α nối giữa các đỉnh x1 và xn. Để chỉ rõ đỉnh đầu và đỉnh cuối ta còn ký
hiệu α bằng α[x1, xn].
28
Một xích với hai đầu trùng nhau, được gọi là một chu trình.
Xích (chu trình) α, được gọi là xích (chu trình) đơn (sơ cấp hay cơ bản),
nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần.
Hai xích (chu trình) được gọi là rời nhau nếu chúng không có cạnh chung.
Ta gọi chu trình có độ dài 3, 4, 5, ..., n là chu trình tam giác, tứ giác, ngũ
giác, ..., n - giác.
2.2.2 Đường, Vòng
Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng.
Dãy β các đỉnh của G(X, E):
β = [x1, x2, . . . , xi, xi+1, . . . , xm−1, xm]
được gọi là một đường hay một đường đi, nếu ∀i (1 (cid:54) i (cid:54) m − 1) đỉnh xi là đỉnh đầu, còn xi+1 là đỉnh cuối cùng của một cung nào đó.
Tổng số vị trí của tất cả các cung xuất hiện trong β được gọi là độ dài của
đường β, đồng thời được ký hiệu bằng |β|.
Đỉnh x1 được gọi là đỉnh đầu, còn đỉnh xm được gọi là đỉnh cuối của đường
β. Ngoài ra, còn nói rằng đường β xuất phát từ đỉnh x1 và đi tới đỉnh xm.
Đường β còn được ký hiệu bằng β[x1, xm].
Một đường có đỉnh đầu và đỉnh cuối trùng nhau, được gọi là vòng.
Đường (vòng) β, được gọi là đường (vòng) đơn (sơ cấp hay cơ bản), nếu nó
đi qua mỗi cạnh (mỗi đỉnh) không quá một lần.
Hai đường (vòng) được gọi là rời nhau nếu chúng không có cung chung.
2.2.3 Một số tính chất
Một số kết quả nhận được từ [5] như sau:
Định lý 2.2.1. Trong một đồ thị vô hướng với n (n (cid:62) 3) đỉnh và các đỉnh đều
29
có bậc không nhỏ hơn 2 luôn luôn tồn tại chu trình sơ cấp.
Chứng minh.
Vì đồ thị hữu hạn, mà mỗi xích sơ cấp qua từng đỉnh không quá một lần,
nên số xích sơ cấp trong đồ thị G(X, E) là một số hữu hạn. Bởi vậy luôn luôn
xác định được xích sơ cấp có độ dài cực đại trong đồ thị G(X, E).
Giả sử α = (x1, x2, . . . , xk−1, xk) là một trong những xích có độ dài cực đại.
Do bậc của mỗi đỉnh không nhỏ hơn 2 nên x1 phải kề với một đỉnh y nào đó (khác x2). Ngược lại, nếu đỉnh y khác xi (3 (cid:54) i (cid:54) k) thì xích sơ cấp:
|α(cid:48)| = |α| + 1 > |α|. α(cid:48) = (y, x1, x2, . . . , xk−1, xk) có độ dài
Điều đó dẫn tới mâu thuẫn với tính độ dài cực đại của xích α, nên y ≡ xi (3 (cid:54) i (cid:54) k) và trong đồ thị có chu trình sơ cấp α = (x1, x2, . . . , xi−1, xi, x1). (cid:3)
Định lý 2.2.2. Trong một đồ thị vô hướng với n (n (cid:62) 4) đỉnh và các đỉnh đều
có bậc không nhỏ hơn 3 luôn luôn tồn tại chu trình sơ cấp có độ dài chẵn.
Chứng minh.
Giả sử α là một trong những xích sơ cấp có độ dài cực đại.
α = (x1, x2, . . . , xi−1, xi+1, . . . , xj−1, xj, xj+1, . . . , xk−1, xk).
Vì α có độ dài cực đại và bậc của x1 không nhỏ hơn 3 nên x1 phải kề với hai đỉnh khác nhau thuộc α: xi (3 (cid:54) i (cid:54) k), xj (3 (cid:54) j (cid:54) k). Khi đó được hai chu trình sơ cấp:
α1 = (x1, x2, . . . , xi−1, xi, x1)
α2 = (x1, x2, ..., xi−1, xi, xi+1, ..., xj−1, xj, x1)
1) Nếu một trong hai chu trình α1, α2 có độ dài chẵn, khẳng định được chứng
minh.
2) Ngược lại, nếu cả hai chu trình α1, α2 có độ dài lẻ.
Khi đó xích α3 = (x1, x2, ..., xi−1, xi) có độ dài chẵn và xích α4 = (xi, ..., xj−1,
xj, x1) có độ dài lẻ.
Khi đó, chu trình α5 = (x1, xi, . . . , xj−1, xj, x1) có độ dài chẵn. Điều phải
chứng minh.
30
(cid:3)
Nhận xét 2.2.1. Trong một đồ thị vô hướng G, các tính chất:
(1) Đồ thị G không có chu trình độ dài lẻ
(2) Đồ thị G không có chu trình sơ cấp độ dài lẻ
tương đương với nhau.
Chú ý 2.2.1. Nếu trong đồ thị G mọi chu trình đơn đều chẵn thì đồ thị đó
không có chu trình nào lẻ.
Chứng minh.
Giả sử mọi chu trình đều đơn thì định lý rõ ràng đúng.
Nếu trong đồ thị có chu trình không đơn và lẻ, thì nhất định một đỉnh thuộc
chu trình được đi qua ít nhất là 2 lần. Đỉnh này chia chu trình làm 2 chu trình
khác và rõ ràng có một chu trình lẻ. Ta tiếp tục xét như vậy chừng nào mà chu
trình lẻ không đơn. Quá trình này phải kết thúc sau một số lần nhất định nào
đó, và ta có một chu trình lẻ mà lại đơn. Điều này trái với giả thiết.
Suy ra rằng đồ thị không có chu trình lẻ. Định lý được chứng minh.
(cid:3)
2.2.4 Ứng dụng
Bài toán 2.2.1. Một cuộc họp có ít nhất 4 đại biểu đến dự. Mỗi đại biểu quen
ít nhất 3 đại biểu khác. Chứng minh rằng có thể xếp được một số đại biểu ngồi
xung quanh một bàn tròn có xếp một số chẵn ghế, để mỗi người ngồi giữa hai
người mà đại biểu đó quen.
Giải.
Xây dựng đồ thị:
Đỉnh: Lấy các điểm trên mặt phẳng hoặc trong không gian tương ứng với
các đại biểu đến dự cuộc họp.
Cạnh: Hai điểm x, y được nối bằng một cạnh khi và chỉ khi hai đại biểu x, y
quen nhau.
Đồ thị G nhận được mô tả quan hệ quen nhau của các đại biểu.
31
Vận dụng kết quả các định lý để suy ra kết luận:
Vì mỗi đại biểu quen ít nhất 3 người đến dự họp nên bậc của mỗi đỉnh của
đồ thị G không nhỏ hơn 3. Theo định lý 2.2.2, trong đồ thị G luôn luôn tồn
tại một chu trình sơ cấp có độ dài chẵn. Khi đó dựa theo một trong những chu
trình này mà ta sắp xếp các đại biểu tương ứng ngồi xung quanh một bàn tròn
có số ghế chẵn mà mỗi đại biểu sẽ ngồi giữa hai người mà họ quen.
√ Bài toán 2.2.2. (xem [4]) Một đỉnh của một đồ thị đơn vô hướng G với n đỉnh có bậc (cid:62) m > n, với m, n là các số tự nhiên lẻ. Chứng minh rằng G có
một chu trình có độ dài 4.
Giải.
Do trong một đồ thị, số đỉnh bậc lẻ là số chẵn, cho nên tồn tại một đỉnh A
của đồ thị có bậc d(A) là số chẵn (vì đồ thị có một số n lẻ đỉnh).
Theo giả thiết bài toán, d(A) (cid:62) m nên d(A) (cid:62) m + 1, vì m là một số lẻ.
m+1 (cid:88)
Kí hiệu Bi là tập hợp các đỉnh kề khác A của đỉnh Ai, theo giả thiết bài
i=1
toán ta có |Bi| (cid:62) m − 1. Do |Bi| (cid:62) (m + 1)(m − 1) = m2 − 1 nên tồn tại
hai chỉ số i0 (cid:54)= j0 sao cho Bi0 ∩ Bj0 (cid:54)= ∅.
Gọi đỉnh chung của Bi0 và Bj0 là B. Ta có ABi0Bj0B có độ dài 4.
Bài toán 2.2.3. (xem [4]) Có n × n gian phòng triển lãm hình tam giác đều
được biểu diễn trong hình bên. Hai phòng triển lãm được gọi là hai phòng láng
giềng khi và chỉ khi chúng có cạnh chung. Biết rằng từ mỗi phòng triễn lãm
người ta có thể đi sang phòng láng giềng của nó.
Một người tham quan muốn đi xem tất cả các phòng triển lãm. Hãy tính
số phòng lớn nhất mà anh ta có thể tham quan sao cho mỗi phòng chỉ đi qua
đúng một lần.
Giải.
Trước tiên, ta có thể tô màu các tam giác đều nhỏ bằng hai màu trắng đen xen kẽ nhau như trong Hình 2.4. Với n (cid:62) 2 có thể thấy số ô màu đen nhỏ hơn
số ô màu trắng ít nhất là 2. Trong quá trình đi thăm triển lãm, ta luôn đi từ
căn phòng ô màu trắng sang bên căn phòng ô màu đen hoặc ngược lại.
32
Xây dựng đồ thị:
Hình 2.4
Đỉnh: Tương ứng là tên các phòng trong triển lãm.
Cạnh: Hai điểm x, y được nối bằng một cạnh khi và chỉ khi người tham
quan đi từ phòng x sang phòng y.
Khi đó, việc đi thăm các căn phòng cho ta một xích sơ cấp.
Giả sử có thể đi sao cho mỗi phòng qua đúng một lần, thì trên dãy cạnh
kế tiếp này các căn phòng màu đen và căn phòng màu trắng xen kẽ nhau và
số căn phòng màu đen chỉ ít hơn số căn phòng màu trắng không quá 1 đơn vị,
mâu thuẫn với điều đã chứng minh ở trên. Vậy, không thể đi thăm tất cả các
phòng sao cho sao cho mỗi phòng chỉ đi qua đúng một lần.
Hơn nữa, số căn phòng màu trắng ở mỗi dòng hơn số căn phòng màu
đen ở dòng ấy là 1, do đó tổng số phòng màu trắng hơn tổng số phòng màu
đen là n. Số căn phòng màu trắng là: và số căn phòng màu đen là n(n + 1) 2
− n = . n(n − 1) 2
n(n + 1) 2 Trên đường đi thăm các căn phòng của người tham quan thỏa mãn yêu cầu
đặt ra, số căn phòng màu trắng chỉ có thể hơn số căn phòng màu đen nhiều
nhất là 1 phòng nên số căn phòng có thể tham quan bởi một lần đi duy nhất
+ 1 = n2 − n + 1. sao cho không có căn phòng nào đi qua 2 lần là 2 n(n − 1) 2
Dễ dàng thấy rằng, chỉ bằng một lần đi duy nhất sao cho không có hai căn
phòng nào đi qua quá một lần, ta có thể xuất phát từ một căn phòng màu
trắng, đi qua tất cả các căn phòng màu đen và trở về một căn phòng màu trắng
33
như sau: Xuất phát từ căn phòng trắng trên cùng, trên mỗi dòng ta đi qua tất
cả các căn phòng màu đen trên trên dòng này rồi xuống tiếp dòng dưới và kết
Hình 2.5
thúc tại một căn phòng màu trắng ở dòng dưới cùng.
Ví dụ với n = 4 trên Hình 2.5. Cách đi này cho ta đi qua tất cả các căn
phòng đen và dẫn ta đi qua tất cả n2 − n + 1 căn phòng (theo [4]).
Bài toán 2.2.4. Hãy chứng minh rằng:
a. Một đồ thị đơn với 2n + 1 đỉnh không có chu trình chẵn cạnh nào thì nó chỉ
có không quá 3n cạnh.
b. Một đồ thị đơn với 2n đỉnh không có chu trình chẵn cạnh nào thì nó chỉ có
không quá 3n − 2 cạnh.
Giải.
Trước tiên ta chứng minh khẳng định:
Trong một đồ thị đơn G không có chu trình độ dài chẵn thì không có hai
chu trình nào có cạnh chung.
Thật vậy, giả sử tồn tại hai chu trình C1 và C2 có cạnh chung trong đồ thị G
thỏa mãn giả thiết có chu trình độ dài chẵn. Gọi độ dài phần chung của chúng
là x, độ dài của C1 không nằm trên phần chung là y và độ dài của C2 không
nằm trên phần chung là z. Ta có x + y và x + z là số lẻ, và y + z là số chẵn,
do đó 2x + y + z là số chẵn, mâu thuẫn với giả thiết G không có chu trình độ
dài chẵn.
Do chu trình lẻ cạnh có ít nhất là 3 cạnh. Nếu đồ thị G có 2n + 1 đỉnh thì
số cạnh của nó không vượt quá 3n (trường hợp số cạnh lớn nhất là khi n tam
34
giác có chung nhau một đỉnh).
Hình 2.6
Còn khi G có 2n đỉnh, ta có thể thấy tương tự là G chỉ có không quá 3n − 2
cạnh (trường hợp số cạnh lớn nhất là khi có n − 1 tam giác có chung một đỉnh
x và đỉnh còn lại y được nối với x).
Bài toán 2.2.5. Giữa n (n (cid:62) 4) thành phố có các đường ôtô liên hệ với nhau,
hai đường bất kỳ chỉ gặp nhau tại một trong n thành phố đã cho. Từ một
thành phố có thể đi tới ít nhất 3 thành phố khác mà không qua một thành phố
trung gian nào cả; độ dài mỗi đường đi giữa 2 thành phố là một số nguyên lẻ
(km). Chứng minh rằng có một thành phố mà từ đó theo các tuyến đường ta
đi qua một số thành phố khác rồi quay về thành phố ban đầu mà các đường
đi không lặp lại, đồng thời độ dài đường đi này là một số chẵn (km).
Giải.
Xây dựng đồ thị:
Đỉnh: Lấy các điểm trên mặt phẳng hoặc trong không gian tương ứng với
các thành phố.
Cạnh: Hai điểm x, y được nối bằng một cạnh khi và chỉ khi hai thành phố
x, y có đường ôtô.
Đồ thị G nhận được mô tả hệ thống giao thông giữa các thành phố.
Vận dụng kết quả các định lý để suy ra kết luận:
Vì mỗi thành phố có thể đi tới ít nhất 3 thành phố khác nên bậc của mỗi
đỉnh của đồ thị G không nhỏ hơn 3. Theo định lý 2.2.2, trong đồ thị G luôn
luôn tồn tại một chu trình sơ cấp có độ dài chẵn. Khi đó từ một chu trình có
35
độ dài chẵn, ta có một tuyến đường thỏa mãn yêu cầu đề bài.
Bài toán 2.2.6. Giữa n thành phố có các đường giao thông liên hệ với nhau,
hai đường bất kỳ chỉ gặp nhau tại một trong n thành phố đã cho. Biết rằng
từ mỗi thành phố có thể đi tới ít nhất k thành phố khác mà trên mỗi đường
đi đều không qua một thành phố nào cả. Chứng minh rằng có thể tìm ra một thành phố để từ đó theo các tuyến đường đã cho ta đi qua (cid:62) k thành phố khác
rồi quay về thành phố ban đầu mà các đường đi không lặp lại.
Nói cách khác, hãy chứng tỏ rằng trong một đồ thị mà mỗi đỉnh đều có bậc
(cid:62) k thì tồn tại một chu trình độ dài (cid:62) k + 1.
Giải.
Lấy một đỉnh bất kỳ của G, ký hiệu đỉnh này là A1 và xây dựng dãy đỉnh
như sau:
A1 → A2 → A3 → . . . → Ak−1 → Ak → Ak+1 . . .
sao cho Ak+1 được nối tiếp từ Ak nếu như thỏa mãn hai điều kiện:
a) Có cạnh AkAk+1 trong đồ thị.
b) Cạnh AkAk+1 chưa gặp lần nào từ trước trong dãy đỉnh kể trên.
Vì số đỉnh của G là hữu hạn nên quá trình này phải kết thúc ở bước nào
đó (có thể chưa qua hết các đỉnh của G) và ta thu được dãy đỉnh:
A1 → A2 → . . . → An.
Như vậy vì m(An) (cid:62) k nên tất cả các đỉnh kề với An đều nằm trong dãy trên và có (cid:62) k đỉnh như vậy. Gọi i là chỉ số nhỏ nhất để Ai kề với An. Khi đó ta có n − i (cid:62) k. Chu trình Ai → Ai+1 → . . . → An → Ai có độ dài n − 1 + i (cid:62) k + 1.
Điều phải chứng minh.
Bài toán 2.2.7. (xem [5]) Cho một tập hợp n > 3 điểm trong mặt phẳng,
trong đó không có 3 điểm nào thẳng hàng và một số tự nhiên k(k < n).
, thì cứ mỗi điểm của tập hợp đã cho có thể vẽ các đoạn thẳng Chứng minh rằng: a. Nếu k (cid:54) n 2 nối với ít nhất k điểm khác sao cho trong đó không có 3 đoạn nào tạo thành
36
một tam giác.
b. Nếu k > và mỗi điểm của tập hợp đã cho được nối bằng những đoạn n 2 thẳng với k điểm khác, thì trong các đoạn thẳng đó bao giờ cũng có 3 cạnh
của một tam giác.
Giải.
, chọn trong tập X (chứa n điểm), một tập con A gồm [ ] điểm, Xét k (cid:54) n 2 n 2
B = X\A chứa [ ] điểm nếu n chẵn và chứa [ ] + 1 điểm nếu n lẻ. n 2 n 2
], do đó A, B chứa không ít hơn k điểm. Xây dựng Vì k nguyên nên k (cid:54) [ n 2 đồ thị 2 mảng: mỗi đỉnh thuộc tập này kề mọi đỉnh thuộc tập kia thì giả thiết
phần a được thực hiện, tuy nhiên không có chu trình tam giác nào (đồ thị 2
mảng thì 2 sắc nên không có chu trình với độ dài lẻ). Có thể phát biểu tổng
quát hơn: không có đa giác lẻ đỉnh.
và mỗi điểm trong X được nối với k điểm khác bởi các đoạn Xét k > n 2 thẳng. Giả sử (x, y) là một trong số các đoạn thẳng này. Theo giả thiết, x và
y mỗi điểm được nối với k điểm; nên ngoài (x, y) ra, mỗi điểm x, y đều được
nối với k − 1 điểm nữa, tổng cộng số đoạn thẳng có ít nhất một đầu mút x
hoặc y là 2k − 1. Nhưng số điểm còn lại (khác x, y) là n − 2. Do k > nên n 2 2k − 2 > n − 2; suy ra trong 2k − 1 đoạn thẳng nói trên có hai đoạn thẳng
trùng đầu mút z. Ta được một chu trình tam giác (x, y, z).
Tổng quát của bài toán
Cho tập X có n > 3 điểm, trong chúng không có 3 điểm nào thuộc một
đường thẳng và các số tự nhiên p, k thỏa mãn: 3 (cid:54) p < n; k < n.
a. Nếu < , thì mỗi điểm của X có thể được nối bằng các đoạn thẳng k n p − 2 p − 1
đến ít nhất k điểm khác của X, sao cho bất kỳ tập con Y (chứa p điểm) nào
của X, cũng có 2 điểm không được nối bằng đoạn thẳng.
b. Nếu > , và mỗi điểm của X được nối bởi các đoạn thẳng với k k n p − 2 p − 1
điểm khác của X, thì có một tập con A chứa p điểm của X, sao cho 2 điểm
bất kỳ trong chúng đều được nối bằng một đoạn thẳng.
Bài toán 2.2.8. Trên mỗi ô của bảng vuông n × n (n > 1) viết một chữ cái.
37
Biết rằng tất cả các dòng bảng đều khác nhau. Chứng minh rằng trong đó có
một cột, mà sau khi xóa nó, bảng còn lại cũng không có dòng nào trùng nhau
(về chữ viết và thứ tự viết).
Giải.
Nếu tồn tại một chỉ số i (1 (cid:54) i (cid:54) n) mà không có hai dòng nào chỉ khác
nhau ở phần tử thứ i, thì sau đó khi xóa cột i đi, hai dòng nào cũng khác nhau
ở một vị trí nữa và khi đó bài toán đã giải xong.
Xét trường hợp: với mỗi i = 1, 2, 3, . . . , n bao giờ cũng tồn tại ít nhất một
cặp dòng chỉ khác nhau ở phần tử thứ i duy nhất (1).
Xây dựng đồ thị như sau: mỗi dòng của bảng là một đỉnh của đồ thị, như
vậy đồ thị có n đỉnh. Với mỗi chỉ số có thể có nhiều cặp dòng có tính chất (1),
song ta chỉ chọn một cặp dòng có tính chất này làm cạnh của đồ thị, như vậy,
mỗi i cho ta một dòng, nên có tất cả n dòng. Đồ thị này có n > 2 đỉnh và có
ít nhất n cạnh, nên nó có ít nhất một chu trình. Ta ký hiệu chu trình này là
(a, b, c, . . . , e, f, a), trong đó a, b, c, . . . , e, f là các đỉnh của đồ thị (là các dòng
của bảng). Với cách xây dựng đồ thị trên ta có: a kề b tức là hai dòng a, b (và
cũng chỉ có hai dòng này, khác nhau ở phần tử thứ i). Các cặp dòng khác có
giá trị trùng nhau ở vị trí thứ i, nghĩa là: b, c; c, d; . . . ; e, f ; f, a tại vị trí thứ i
trùng nhau; suy ra b, a trùng nhau tại vị trí thứ i. Điều này hoàn toàn vô lý,
vì hai dòng a, b vừa khác nhau, vừa trùng nhau tại vị trí thứ i. Từ đây suy ra
khẳng định của bài toán được chứng minh.
2.3 Bài toán liên quan đến tính liên thông
2.3.1 Định nghĩa
Hai đỉnh x, y được gọi là cặp đỉnh liên thông, nếu hoặc giữa x và y có ít
nhất một xích nối với nhau, hoặc tồn tại ít nhất một đường đi từ x sang y hoặc
từ y sang x.
Đồ thị vô hướng G(X, E) được gọi là đồ thị liên thông nếu mọi cặp đỉnh
38
của nó đều liên thông.
Đồ thị có hướng G = G(X, E) được gọi là đồ thị liên thông mạnh nếu mọi
cặp đỉnh của nó đều liên thông.
Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của
nó là liên thông.
Giả sử a là đỉnh bất kì thuộc đồ thị G. Dùng Ca để ký hiệu tập con các
đỉnh của G, gồm đỉnh a và tất cả các đỉnh liên thông với a trong đồ thị G.
Đồ thị con của G, có tập đỉnh là Ca, được gọi là một thành phần liên thông
của đồ thị G.
Đỉnh x trong đồ thị liên thông G được gọi là điểm khớp, nếu đồ thị con G1
nhận được từ G bằng cách bỏ đỉnh x, là đồ thị không liên thông. Điểm khớp
x, mà nó được nối với mỗi thành phần liên thông của G1 bằng đúng một cạnh,
được gọi là điểm khớp đơn.
Việc xoá đỉnh khớp khỏi một đồ thị liên thông sẽ tạo ra một đồ thị con
không liên thông.
Một cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị có nhiều thành phần liên
thông hơn so với đồ thị xuất phát được gọi là cạnh khớp (hay là cầu).
2.3.2 Một số tính chất
Một số kết quả nhận được từ [5] như sau:
Định lý 2.3.1. Đồ thị với n đỉnh (n (cid:62) 2), mà tổng bậc của hai đỉnh tuỳ ý đều
không nhỏ hơn n, là đồ thị liên thông.
Chứng minh.
Giả sử đồ thị G(X, E) có n đỉnh (n (cid:62) 2). Với mọi cặp đỉnh a, b của đồ thị
G đều có:
m(a) + m(b) (cid:62) n (2.4)
nhưng a, b không liên thông. Khi đó trong đồ thị G tồn tại hai thành phần liên
thông là G1 có n1 đỉnh và chứa đỉnh A, G2 chứa đỉnh b và có n2 đỉnh.
39
Vì G1, G2 là các thành phần liên thông của G nên n1 + n2 (cid:54) n.
Khi đó:
(2.5) m(a) + m(b) (cid:54) (n1 − 1) + (n2 − 1) = n1 + n2 − 2 (cid:54) n − 2 < n.
Do sự mâu thuẫn của các đẳng thức (2.4) và (2.5), suy ra kết luận: Đồ thị G
phải liên thông. Khẳng định được chứng minh.
(cid:3)
Từ định lý 2.3.1, ta suy ra các hệ quả sau:
Hệ quả 2.3.1. Đồ thị mà bậc của mỗi đỉnh của nó không nhỏ hơn một nửa số
đỉnh là đồ thị liên thông.
Định lý 2.3.2. Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải
liên thông, tức là có một đường đi nối chúng.
Chứng minh.
Giả sử đồ thị G(X, E) có đúng hai đỉnh bậc lẻ, chẳng hạn hai đỉnh này là
a và b. Giả sử a và b không liên thông với nhau. Khi đó chúng phải thuộc hai
thành phần liên thông nào đó của đồ thị G, G1 chứa a và G2 chứa b.
Bậc của đỉnh a trong G1 cũng chính là bậc của a trong G, nên trong G1
đỉnh a vẫn có bậc lẻ và G1 có duy nhất một đỉnh bậc lẻ. Điều này mâu thuẫn.
Vậy hai đỉnh a và b phải liên thông.
(cid:3)
Phân hoạch: Giả sử có tập M (cid:54)= ∅. Dãy các tập con của M :
X1, X2, ..., Xm−1, Xm
được gọi là một phân hoạch của tập M , nếu nó thỏa mãn đồng thời 3 điều kiện
sau:
m (cid:91)
1) ∀i (1 (cid:54) i (cid:54) m).Xi (cid:54)= ∅ 2) ∀i, j (1 (cid:54) i, j (cid:54) m; i (cid:54)= j), Xi ∩ Xj = ∅
i=1
3) Xi = X.
Định lý 2.3.3. Dãy các tập đỉnh của các thành phần thuộc đồ thị G(X, E) lập
40
thành một phân hoạch của tập đỉnh X.
Chứng minh.
Giả sử G1(Ca1, E), G2(Ca2, E), ..., Gm(Cam, E) là tất cả các thành phần liên
thông của đồ thị G(X, E).
Theo định nghĩa Cai bao gồm đỉnh Ai và tất cả các đỉnh thuộc X liên thông
với ai nên Cai ⊆ X (1 (cid:54) i (cid:54) m).
Vì ai ∈ Cai nên ∀i (1 (cid:54) i (cid:54) m), Cai (cid:54)= ∅.
m (cid:91)
Giả sử i (cid:54)= j nhưng Cai ∩ Caj (cid:54)= ∅. Khi đó tồn tại đỉnh x, mà x ∈ Cai và x ∈ Caj , nên x liên thông với cả ai, aj. Vì vậy ai và aj liên thông. Bởi vậy ai liên thông với mọi đỉnh của Caj và ngược lại aj liên thông với mọi đỉnh của Cai. Do đó Cai = Caj . Điều này mâu thuẫn với tính chất Cai (cid:54)= Caj nên Cai ∩ Caj = ∅.
i=1
Do ai ∈ Cai và Cai ⊆ X (1 (cid:54) i (cid:54) m) nên X = Cai.
Định lý được chứng minh.
(cid:3)
Định lý 2.3.4. Đồ thị G(X, E) liên thông khi và chỉ khi nó có một thành phần
liên thông duy nhất.
Chứng minh.
1) Điều kiện cần: Giả sử đồ thị G(X, E) liên thông nhưng lại có không có
ít hơn hai thành phần liên thông. Giả sử G1(Ca, E), G2(Cb, E) là hai trong các
thành phần liên thông của G. Khi đó, tồn tại x ∈ Ca, y ∈ Cb và x, y không liên
thông với nhau. Bởi vậy đồ thị G(X, E) không liên thông. Điều này mâu thuẫn
với giả thiết nên G(X, E) chỉ có một thành phần liên thông duy nhất.
2) Điều kiện đủ: Giả sử đồ thị G(X, E) có một thành phần liên thông
duy nhất. Khi đó thành phần liên thông này chứa tất cả các đỉnh của đồ thị
G(X, E).
Do mọi đỉnh của thành phần liên thông đều liên thông với nhau, nên mọi
cặp đỉnh của đồ thị liên thông với nhau, nên G(X, E) là đồ thị liên thông.
Khẳng định được chứng minh.
41
(cid:3)
Định lý 2.3.5. Giả sử G(X, E) là một đồ thị liên thông. Khi đó một đỉnh của
G(X, E) là điểm khớp khi và chỉ khi trong G(X, E) tồn tại hai đỉnh u và v sao
cho mỗi xích nối u và v đều phải đi qua đỉnh này.
Chứng minh.
1) Điều kiện cần: Giả sử đỉnh x là điểm khớp trong đồ thị G(X, E). Khi đó
đồ thị con G1(X\{x}, E) của G(X, E) là đồ thị nhận được bằng cách xoá x và
các cạnh liên thuộc với nó là không liên thông. Giả sử G2, G3 là hai trong các
thành phần liên thông của G1. Lấy u là đỉnh trong G2 và v là đỉnh trong G3.
Do u, v thuộc hai thành phần liên thông khác nhau, nên trong G1 các đỉnh u, v
không liên thông. Nhưng trong G các đỉnh u, v lại liên thông, nên mọi xích nối
u, v đều phải đi qua đỉnh x.
2) Điều kiện đủ : Giả sử mọi xích nối u, v đều đi qua đỉnh x, nên nếu bỏ
đỉnh x và các cạnh liên thuộc với x thì đồ thị con G1 nhận được từ G chứa hai
đỉnh u, v không liên thông. Do đó G1 là đồ thị không liên thông hay đỉnh x là
điểm khớp của G.
(cid:3)
Định lý 2.3.6. Giả sử đồ thị G có n đỉnh, m cạnh và k thành phần liên thông.
Khi đó ta có bất đẳng thức:
n − k (cid:54) m (cid:54) (n − k)(n − k + 1) . 2
Chứng minh.
Bất đẳng thức n − k (cid:54) m được chứng minh bằng quy nạp theo m.
Nếu m = 0 thì k = n nên bất đẳng thức đúng.
Giả sử bất đẳng thức đúng đến m − 1, với m (cid:62) 1. Gọi G(cid:48) là đồ thị con
bao trùm của G có số cạnh m0 là nhỏ nhất sao cho nó có k thành phần liên thông. Do đó việc loại bỏ bất cứ cạnh nào trong G(cid:48) cũng tăng số thành phần
liên thông lên 1 và khi đó đồ thị thu được sẽ có n đỉnh, k + 1 thành phần liên thông và m0 − 1 cạnh. Theo giả thiết quy nạp, ta có m0 − 1 (cid:62) n − (k + 1) hay m0 (cid:62) n − k.
42
Vậy m (cid:62) n − k.
Bổ sung cạnh vào G để nhận được đồ thị G(cid:48)(cid:48) có m1 cạnh sao cho k thành phần liên thông là những đồ thị đầy đủ. Ta có m (cid:54) m1 nên chỉ cần chứng minh:
.
ni) + (C 2
nj−1 − C 2 (cid:105)
m1 (cid:54) (n − k)(n − k + 1) 2 Giả sử Gi và Gj là hai thành phần liên thông của G(cid:48)(cid:48) với ni và nj đỉnh và ni (cid:62) nj > 1 (*). Nếu ta thay Gi và Gj bằng đồ thị đầy đủ với ni + 1 và nj − 1 đỉnh thì tổng số đỉnh không thay đổi nhưng số cạnh tăng thêm một lượng là:
nj ) (cid:104)(nj − 1)(nj − 2) 2
(cid:105) + − − = (C 2 ni+1 − C 2 (cid:104)(ni + 1)ni 2 ni(ni − 1) 2 nj(nj − 1) 2
= ni − nj + 1.
Thủ tục này được lặp lại khi hai thành phần nào đó có số đỉnh thoả mãn (*).
Vì vậy m1 là lớn nhất (n, k là cố định) khi đồ thị gồm k − 1 đỉnh cô lập và một
n−k+1.
đồ thị đầy đủ với n − k + 1 đỉnh.
Vậy m1 là lớn nhất bằng C 2 Từ đó suy ra bất đẳng thức cần tìm.
(cid:3)
Hệ quả 2.3.2. Nếu đồ thị G có n đỉnh và số cạnh lớn hơn (n − 1)(n − 2) thì 1 2 nó liên thông.
Chứng minh.
Dùng k để ký hiệu số thành phần liên thông của G. Khi đó theo định lý
2.3.6 số cạnh m của đồ thị thỏa mãn các bất đẳng thức:
(cid:54) m (cid:54) (n − k)(n − k + 1) . (n − 1)(n − 2) 2 2
Bất đẳng thức thỏa mãn khi k = 1. Theo Định lý 2.3.4 đồ thị G liên thông. (cid:3)
2.3.3 Ứng dụng
Bài toán 2.3.1. Một lớp học có 40 học sinh về nghỉ hè. Biết rằng mỗi em có
43
địa chỉ của ít nhất 20 bạn, và nếu bạn này có địa chỉ của bạn kia thì bạn kia
cũng có địa chỉ của bạn này. Chứng minh rằng bất cứ hai em nào trong lớp
cũng có thể nhắn tin cho nhau.
Giải.
Ta cho tương ứng mỗi học sinh với mỗi đỉnh của đồ thị, còn hai học sinh có
trao đổi địa chỉ cho nhau thì hai đỉnh tương ứng được nối bởi một cạnh; mỗi
em có địa chỉ của ít nhất 20 bạn nghĩa là mỗi đỉnh có bậc ít nhất bằng 20. Khi
đó hai bạn có thể nhắn tin cho nhau nếu trên đồ thị tồn tại một đường đi nối
giữa hai đỉnh tương ứng. Ta ký hiệu đồ thị trên là G.
Theo hệ quả 2.3.1 đồ thị G liên thông, nên hai đỉnh tùy ý đều có đường nối
với nhau. Bởi vậy hai bạn bất kỳ trong lớp đều có thể nhắn tin cho nhau.
Bài toán 2.3.2. Trong 6 học trò bất kì trong số 41 học sinh của một lớp học
luôn có 2 học trò sinh cùng một tháng. Chứng minh rằng luôn tìm được 9 học
trò trong lớp nói trên sinh cùng một tháng.
Giải.
Ta biểu diễn một đồ thị G có đỉnh tương ứng với các học trò. Hai đỉnh được
nối với nhau bằng một cạnh nếu hai em tương ứng sinh cùng một tháng.
Đồ thị thu được có số thành phần liên thông không vượt quá 5. Vì nếu số
thành phần liên thông vượt quá 5, ta có thể chọn từ mỗi thành phần liên thông
của nó một đỉnh và khi đó có ít nhất 6 học trò tương ứng sao cho không có hai
em nào sinh cùng một tháng.
Do đồ thị G thu được có 41 đỉnh nên luôn tồn tại một thành phần liên
thông có ít nhất 9 đỉnh. Do đó, tồn tại ít nhất 9 học trò sinh cùng một tháng.
Bài toán 2.3.3. (xem [8]) Trong một cuộc họp có đúng hai đại biểu không
quen nhau và mỗi đại biểu trong hai đại biểu này có đúng một số lẻ người quen
cùng đến dự họp. Chứng minh rằng luôn có thể sắp xếp một số đại biểu ngồi
chen giữa hai đại biểu nói trên để mỗi đại biểu ngồi giữa hai người mà họ quen.
Giải.
44
Ta xây dựng đồ thị G như sau:
- Đỉnh: là các điểm trong mặt phẳng tương ứng với các đại biểu, dùng mã
số của mỗi đại biểu để ghi trên các đỉnh tương ứng.
- Cạnh: hai đỉnh được nối với nhau bằng một cạnh khi và chỉ khi hai đại
biểu tương ứng thuộc hai đỉnh đó quen nhau.
Khi đó ta được một đồ thị G mô tả toàn bộ quan hệ quen biết giữa các đại
biểu. Vì đồ thị G có đúng hai đỉnh bậc lẻ a, b không kề nhau nên theo định lý
2.3.2, hai đỉnh a, b liên thông. Khi đó, giữa a, b có một đường đi và ta có thể
sắp xếp các đại biểu ngồi giữa hai đại biểu a, b không quen biết nhau để các
đại biểu này ngồi giữa hai đại biểu họ quen.
Bài toán 2.3.4. (xem [5]) Tại mỗi đỉnh của một đồ thị liên thông ta viết một
số thực sao cho số viết mỗi đỉnh bằng trung bình cộng của các số viết tại mỗi
đỉnh kề với đỉnh này. Chứng minh rằng tất cả các số được viết đều bằng nhau.
Giải.
Để cho gọn, ta ký hiệu số ghi tại đỉnh x cũng là x.
Giả sử a là số nhỏ nhất trong các số được viết tại tất cả các đỉnh và b là số
viết tại đỉnh b bất kỳ, ta sẽ chứng minh a = b.
Vì đồ thị liên thông, nên tồn tại đường đi (a, a1, a2, . . . , ak, b). Nếu a được
nối với m đỉnh x, y, . . . , z thì:
a = . x + y + . . . + z m
Song a (cid:54) x; y; . . . ; z nên a = x = y = . . . = z.
Điều đó cũng có nghĩa là a = a1.
Cho a1 đóng vai trò của a (điều này hoàn toàn có thể được vì a1 = a nên
cũng là số nhỏ nhất trong các số đã viết) thì a1 = a2, ..., cuối cùng ta có kết
quả là a = a1 = a2 = . . . = ak = b.
Bài toán 2.3.5. (xem [3]) Chứng minh rằng đối với đồ thị liên thông G tùy ý
có n cạnh luôn luôn có thể đánh số các cạnh của G bằng các số 1, 2, . . . , n sao
cho tại mỗi đỉnh mà ở đó có ít nhất hai cạnh của đồ thị, thì ước số chung lớn
45
nhất của các số nguyên viết trên các cạnh thuộc đỉnh này bằng 1.
Giải.
Từ một đỉnh x bất kỳ, đi dọc theo các cạnh phân biệt của đồ thị, ta đánh
số các cạnh bằng 1, 2,. . . theo thứ tự ta gặp chúng, cho tới khi không thể đi
xa hơn được nữa (vì nếu muốn đi thêm phải dùng lại một cạnh đã đi qua).
Nếu còn cạnh chưa được đánh số, do G liên thông, nên trong các cạnh này
phải có cạnh mà đỉnh thuộc nó đã nằm trên đường đi vừa đánh số. Lại xuất
phát từ đỉnh đó, lấy số vừa dừng lại, tiếp tục đi dọc theo các cạnh chưa đánh
số để đánh số tiếp (theo cách đã làm trên) cho đến khi gặp lại tình huống cũ.
Lặp lại quá trình này cho đến khi tất cả các cạnh đều được đánh số.
Giả sử y là đỉnh nối với k cạnh (k (cid:62) 2). Nếu y trùng x thì y là đỉnh đầu
cạnh ghi số 1, nên bài toán đã chứng minh xong.
Nếu y khác x, giả sử lần đầu tiên gặp y tại đỉnh cuối của cạnh đánh số r. Lúc này có k − 1 (k − 1 (cid:62) 1) cạnh chưa được đánh số nối với y. Do vậy, từ y
ra theo một trong các cạnh còn lại này phải đánh số r + 1. Do (r, r + 1) = 1,
nên ước số chung lớn nhất của các số ghi trên các cạnh y cũng bằng 1.
Bài toán 2.3.6. (Vô địch Hungari 1933 ) Cho một bảng ô vuông kích thước
8x8. Chọn 16 ô trong 64 ô vuông của bảng sao cho trên mỗi hàng ta chọn đúng
2 ô vuông và trên mỗi cột cùng chọn đúng 2 ô vuông. Chứng minh rằng có thể
tô 16 ô vuông này bằng hai màu xanh và đỏ sao cho trên mỗi hàng có đúng
một ô màu xanh và một ô màu đỏ, trên mỗi cột cũng vậy.
Giải.
Bắt đầu từ một ô bất kỳ trong 16 ô được chọn ta gọi ô này là ô thứ nhất.
Ta tô màu đỏ cho ô này. Với ô thứ hai, nằm cùng hàng ngang với ô thứ nhất ta
tô màu xanh. Với ô thứ ba, nằm cùng cột (hàng dọc) với ô thứ hai ta tô màu
đỏ. Để thấy cả ba ô thứ nhất, thứ hai và thứ ba là khác nhau. Xét ô thứ tư
nằm cùng hàng ngang với ô thứ ba: ô này hoặc nằm cùng cột với ô thứ nhất
và khác ô thứ nhất, hoặc không nằm cùng cột với ô thứ nhất và vì thế cũng
khác ô thứ nhất, ta tô ô thứ tư này màu xanh.
Xét trường hợp ô thứ tư cùng cột với ô thứ nhất: Như vậy bốn ô đều nằm
46
trên hai hàng và hai cột. Vậy 12 ô được chọn còn lại nằm trên 6 hàng và 6 cột,
mỗi hàng cũng như mỗi cột có đúng hai ô. Ta lặp lại quá trình trên.
Xét trường hợp ô thứ tư khác cột với ô thứ nhất: Ta tô ô thứ năm cùng
cột với ô thứ tư, tô ô này màu đỏ. Tô ô thứ sáu cùng hàng với ô thứ năm màu
xanh, ô thứ sáu này khác ô thứ nhất (nếu không trên hàng chứa ô thứ nhất sẽ
có 4 ô: ô thứ nhất, ô thứ hai, ô thứ năm, ô thứ sáu); tương tự ô thứ sáu cũng
khác ô thứ ba, thứ tư. Bây giờ ô thứ sáu có thể cùng cột với ô thứ nhất, và
nếu vậy tô 6 ô đầu tiên này nằm trên ba hàng và ba cột, 10 ô còn lại nằm trên
5 hàng và 5 cột còn lại; có thể ô thứ sáu không cùng cột với ô thứ nhất. Lại
lặp lại một trong hai quá trình trên cho đến khi hết cả 16 ô được chọn.
Rõ ràng hai ô cùng hàng hay cùng cột được tô khác màu nhau.
Bài toán 2.3.7. Hai mươi học sinh vào thư viện mượn sách mới. Biết rằng
thư viện mới có 20 cuốn sách mới thuộc về các loại khác nhau. Mỗi học sinh
muốn mượn hai cuốn, mỗi cuốn có đúng hai học sinh muốn mượn và người
phụ trách thư viện thấy rằng số sách mà các em học sinh muốn mượn đúng là
20 cuốn sách kia. Chứng tỏ rằng người phụ trách thư viện có thể cho mỗi em
mượn đúng một trong hai cuốn sách mình muốn mượn.
Giải.
Ký hiệu các học sinh là A1, A2, ..., A20 và các cuốn sách là a1, a2, ..., a20. Giả
sử A1 muốn mượn hai cuốn sách a1 và a2.
Cho A1 mượn cuốn a1. Cuốn a2 ngoài A1 ra còn một học sinh khác, chẳng
hạn A2, muốn mượn. Cho A2 mượn cuốn a2. Học sinh A2 ngoài cuốn a2 ra còn
muốn muộn một cuốn khác. Có hai khả năng.
a) Nếu cuốn thứ hai mà A2 muốn mượn là cuốn a1: Lúc này còn lại 18 học
sinh A3, A4, . . . , A20 mỗi em muốn mượn hai trong 18 cuốn a3, a4, . . . , a20. Ta
tiếp tục quá trình trên.
b) Nếu cuốn thứ hai mà A2 muốn mượn không phải là cuốn a1; không mất
tính tổng quát có thể giả sử đó là cuốn a3.
Học sinh A1 không muốn mượn cuốn a3 (vì rằng A1 muốn mượn hai cuốn
a1, a2). Do vậy còn một học sinh khác, khác A1, A2; muốn mượn cuốn a3. Giả
47
sử học sinh này là A3.
Cuốn thứ hai mà A3 muốn mượn không thể là a2 (vì nếu vậy a2 sẽ có ba
học sinh A1, A2, A3 muốn mượn). Nếu cuốn thứ hai mà A3 muốn mượn lại là
cuốn a1, thì ba học sinh A1, A2, A3 đã mượn ba cuốn. 17 cuốn còn lại có 17 em
muốn mượn mà mỗi em muốn mượn 2 trong 17 cuốn đó; mỗi cuốn còn lại lại
có đúng 2 trong 17 em đó mượn. Ta lặp lại quá trình ban đầu.
Còn khi cuốn thứ hai mà A3 muốn mượn không phải là cuốn a1 (dĩ nhiên
đó cũng không phải cuốn a2 và a3) thì có thể coi đó là cuốn a4. A1, A2 không
muốn mượn cuốn a4, nên người thứ hai muốn mượn cuốn a4 phải là học sinh
nào đó khác A1, A2, A3. Giả sử (mà không mất tính tổng quát) đó là học sinh
A4.
Lại xét cuốn thứ hai mà A4 muốn mượn (đó không thể là a2 và a3. Chỉ có
2 khả năng cuốn đó là cuốn a1 hoặc không phải là cuốn a1).
Quá trình trên tất sẽ kết thúc ở một bước nào đó. Lúc đó đúng là mỗi em
được mượn một trong hai cuốn mình muốn mượn.
Hai bài toán 2.3.6 và 2.3.7. Một bài cho với số n = 8, một bài cho với số n
= 20, ở đây n là số tự nhiên tùy ý lớn hơn 2.
Đồ thị tương ứng với hai bài toán này có thể biểu diễn dưới dạng sau đây:
Tất cả các đỉnh của đồ thị chia làm hai nhóm. Một đỉnh của nhóm này được
nối với hai đỉnh của nhóm kia bằng các cạnh, còn hai đỉnh ở một nhóm không
được nối với nhau bằng một cạnh nào cả.
Một đồ thị mà các đỉnh của nó có thể chia làm hai nhóm sao cho hai đỉnh
của một cạnh nào đó nằm trên hai nhóm khác nhau gọi là đồ thị chẵn (Hình
Hình 2.7
2.7).
Đồ thị chẵn có thể liên thông cũng có thể không liên thông. Nếu số đỉnh
48
của đồ thị chẵn là lớn hơn 2 thì đồ thị này không phải là đồ thị đầy đủ. Thật
vậy, vì đồ thị có nhiều hơn hai đỉnh nên một nhóm đỉnh nào đó phải có ít nhất
là hai đỉnh. Hai đỉnh này không thể nối với nhau bằng một cạnh nên đồ thị
không phải là đồ thị đầy đủ.
Bài toán 2.3.8. (xem [4]) Chứng minh rằng với mỗi đồ thị G thì hoặc G liên
thông, hoặc G liên thông.
Giải.
Giả sử G không liên thông. Lấy A là đỉnh bất kỳ của G. Xét tất cả các đỉnh
của G mà kề với A (nghĩa là được nối với A bằng một cạnh). Lại xét tất cả các
đỉnh kề với các đỉnh này,. . . Do số đỉnh của G là hữu hạn nên quá trình trên
kết thúc ở bước nào đó. Nếu khi kết thúc quá trình, trong G không còn đỉnh
nào khác thì G phải liên thông. Điều đó trái với giả thiết G không liên thông.
Do vậy có những đỉnh của G không được xét tới trong quá trình trên. Vậy
các đỉnh của G được chia thành hai nhóm mà không có cạnh nào nối hai đỉnh
Hình 2.8
của hai nhóm cả (hình 2.8).
Bây giờ xét hai đỉnh bất kỳ của G.
Nếu hai đỉnh thuộc hai nhóm khác nhau được chia ở trên thì rõ ràng trong
G tồn tại một cạnh nối chúng, có nghĩa là hai đỉnh này liên thông trong G .
Nếu hai đỉnh thuộc cùng một nhóm được chia ở trên thì lấy thêm một đỉnh
thứ 3 ở nhóm đỉnh khác. Cả hai đỉnh đều nối với đỉnh thứ 3 này bằng các cạnh
trong G , có nghĩa là hai đỉnh này liên thông trong G .
49
Vậy nếu G không liên thông thì G liên thông.
cạnh thì đồ thị G liên thông. Bài toán 2.3.9. Chứng minh rằng nếu đồ thị G có n đỉnh và có nhiều hơn: (n − 1)(n − 2) 2
Giải.
Giả sử G không liên thông, khi đó có thể chia các đỉnh của G làm hai nhóm,
số cạnh của G có hai đỉnh thuộc nhóm thứ nhất không thể quá sao cho không có một cạnh nào của G nối hai đỉnh thuộc hai nhóm khác nhau. Một nhóm có m đỉnh (1 (cid:54) m < n) còn nhóm kia có (n − m) đỉnh. Do vậy m(m − 1) 2
cạnh. cạnh. Tương tự, số cạnh của G có hai đỉnh thuộc nhóm thứ hai không thể quá (n − m)(n − m − 1) 2
Vì vậy, số cạnh của G không vượt quá
+ . m(m + 1) 2 (n − m)(n − m − 1) 2
. Ta chứng tỏ rằng, số này không vượt quá (n − 1)(n − 2) 2 Thật vậy
+ m(m − 1) 2 (n − m)(n − m − 1) 2 (cid:54) (n − 1)(n − 2) 2
⇔ m2 − mn (cid:54) 1 − n ⇔ (m − 1)(m + 1 − n) (cid:54) 0 (luôn đúng).
Vậy nếu G không liên thông thì số cạnh của G phải nhỏ hơn hay bằng
. (n − 1)(n − 2) 2
thì G liên thông. Suy ra nếu số cạnh của G lớn hơn (n − 1)(n − 2) 2
2.4 Đồ thị Euler - Đồ thị Hamilton
Định nghĩa
2.4.1 Đường đi Euler và đồ thị Euler
Xích α trong đồ thị vô hướng G(X, E) được gọi là xích Euler nếu nó đi qua
tất cả các cạnh của G và qua mỗi cạnh đúng một lần. Nói cách khác, xích Euler
50
của đồ thị G là một xích đơn và đi qua tất cả các cạnh của G.
Chu trình α của đồ thị G được gọi là chu trình Euler nếu nó đi qua tất cả
các cạnh của G và qua mỗi cạnh đúng một lần. Nói cách khác, chu trình Euler
của đồ thị G là một chu trình đơn và đi qua tất cả các cạnh của G.
Đồ thị vô hướng G được gọi là đồ thị Euler nếu nó có chu trình Euler.
Đường β của đồ thị có hướng G được gọi là đường Euler nếu nó đi qua tất
cả các cung của đồ thị G và qua mỗi cung đúng một lần. Nói cách khác, đường
Euler của đồ thị có hướng G là một đường đơn và đi qua tất cả các cung của
G.
Vòng (mạch) β của đồ thị có hướng G được gọi là vòng (mạch) Euler nếu
nó đi qua tất cả các cung của đồ thị G và qua mỗi cung đúng một lần. Nói
cách khác, vòng (mạch) Euler của đồ thị có hướng G là một vòng (mạch) đơn
và đi qua tất cả các cung của G.
Hình 2.9
Đồ thị có hướng G được gọi là đồ thị Euler nếu nó có vòng Euler.
Điều kiện cần và đủ để một đa đồ thị vô hướng là đồ thị Euler
Một số kết quả nhận được từ [5] như sau:
Bổ đề 2.4.1. Nếu tất cả các đỉnh của đa đồ thị vô hướng G đều có bậc chẵn
thì xuất phát từ đỉnh A tùy ý của G ta đều vạch ra được một chu trình đơn đi
qua A.
Chứng minh.
1) Nếu A là đỉnh biệt lập thì chu trình đi qua A có độ dài 0.
2) Nếu A có bậc dương thì xuất phát từ A phải có ít nhất 2 cạnh. Giả sử
51
hai trong các cạnh của đỉnh A là (A, B) và (A, C).
Theo (A, B), (A, C) đi theo hướng độc lập nhau, mỗi khi đi qua một đỉnh,
thì đi vào bằng một cạnh và đi ra theo một cạnh khác và không bao giờ lặp lại.
Vì đồ thị G hữu hạn nên sau một số bước hai xích phải gặp nhau và ta được
chu trình đơn đi qua A.
(cid:3)
Bổ đề 2.4.2. Nếu đa đồ thị vô hướng G là đồ thị Euler, thì G phải chứa không
quá một thành phần liên thông có cạnh và các đỉnh đều bậc chẵn.
Chứng minh.
Giả sử đồ thị G có chu trình Euler, nhưng hoặc chứa không ít hơn hai thành
phần liên thông có cạnh, hoặc có đỉnh bậc lẻ.
1) Giả sử G chứa không ít hơn 2 thành phần liên thông có cạnh và hai trong
các thành phần liên thông chứa cạnh của G là G1, G2 và α là một trong những
chu trình Euler của G. Khi đó, nếu α xuất phát từ G1 và qua cạnh a thuộc G1
thì nó không thể sang G2 để đi qua cạnh b thuộc G2. Ngược lại, nếu α xuất
phát từ G2 và qua cạnh b thuộc G2 thì nó không thể sang G1 để đi qua cạnh
a thuộc G1. Điều này mâu thuẫn với giả thiết cho G là một đồ thị Euler. Vậy
đồ thị G phải có không quá một thành phần liên thông chứa cạnh.
2) Giả sử G có đỉnh bậc lẻ và A là một trong các đỉnh bậc lẻ của G đồng
thời A có bậc bằng 3. Giả sử 3 cạnh thuộc A là (A, B), (A, C) và (A, D).
Khi đó nếu chu trình Euler α muốn đi qua cả 3 cạnh thuộc A thì nó phải đi
2 lần, trường hợp qua mỗi cạnh không quá một lần thì α không đi được qua cả
3 cạnh thuộc đỉnh A. Điều này mâu thuẫn với tính chất của chu trình Euler.
Do đó, G không chứa đỉnh bậc lẻ.
Bổ đề được chứng minh.
(cid:3)
Bổ đề 2.4.3. Nếu đa đồ thị vô hướng G = (X, E) chứa không quá một thành
phần liên thông có cạnh và các đỉnh đều bậc chẵn thì G có chu trình Euler.
52
Chứng minh.
1) Nếu tất cả các đỉnh của G đều biệt lập thì chu trình Euler trong trường
hợp này có độ dài 0.
2) Giả sử G1 là thành phần liên thông duy nhất trong G có chứa cạnh. Khi
đó xuất phát từ đỉnh A ∈ G1, theo bổ đề 2.4.2 vạch ra trong G1 một chu trình
đơn, ký hiệu p11, dùng số 1 để ghi trên các cạnh thuộc p11.
“Xóa” p11 khỏi đồ thị G1, đồ thị con nhận được ký hiệu bằng G2. Vì G1 liên
thông nên p11 và G2 phải có ít nhất một đỉnh chung. Do p11 là chu trình đơn,
nên mỗi khi đi qua một đỉnh thì nó đi vào bằng một cạnh, đi ra bằng một cạnh
khác và không bao giờ lặp lại. Vì vậy, tại mỗi đỉnh mà p11 đi qua bị “xóa” đi
một số chẵn cạnh. Do đó G2 cũng là một đồ thị với các đỉnh đều bậc chẵn.
Giả sử B là một trong những đỉnh chung của p11 và G2. Qua B, theo bổ đề
2.4.2, lại vạch ra trong G2 một chu trình đơn, ký hiệu bằng p12 và dùng số 2
để ghi trên các cạnh thuộc p12.
Thống nhất hai chu trình p11 và p12 thành một chu trình đơn mới p1 bằng
cách đi từ đỉnh A theo p11 tới đỉnh B, sau đó đi theo tiếp p12 để trở về B, rồi
tiếp tục đi theo p11 để trở về A.
Tiếp tục áp dụng bổ đề 2.4.2 và thực hiện quá trình tương tự như trên cho
tới khi nhận được chu trình đơn đi qua tất cả các cạnh của G1. Khi đó ta được
chu trình Euler trong G.
Bổ đề được chứng minh.
(cid:3)
Từ các bổ đề đã nêu ta có các hệ quả:
Hệ quả 2.4.1. Đồ thị vô hướng G = (X; E) là đa đồ thị Euler khi và chỉ khi nó
chứa không quá một thành phần liên thông có cạnh và các đỉnh đều bậc chẵn.
Hệ quả 2.4.2. Đồ thị vô hướng G = (X; E) có xích Euler khi và chỉ khi nó
chứa không quá một thành phần liên thông có cạnh và số đỉnh bậc lẻ là 0 hoặc
2.
Chứng minh.
53
1) Điều kiện cần:
Vì nếu trong G có xích Euler α thì nó phải đi qua tất cả các cạnh của đồ
thị, nên G không thể chứa quá một thành phần liên thông có cạnh. Ngoài ra,
chỉ có thể là đỉnh đầu và đỉnh cuối của α (nếu chúng khác nhau) là có bậc lẻ
và α qua mỗi đỉnh đều đi vào bằng một cạnh và đi ra bằng cạnh khác và không
lặp lại, nên chỉ có hai đỉnh đầu của α có bậc lẻ. Do đó số đỉnh bậc lẻ của G chỉ
có thể là 0 hoặc 2.
2) Điều kiện đủ:
a) Nếu đồ thị G không chứa đỉnh bậc lẻ, theo bổ đề 2.4.3, nó có chu trình
Euler – Xích Euler khép kín.
b) Nếu trong đồ thị G có đúng hai đỉnh bậc lẻ, chẳng hạn A, B là hai đỉnh
bậc lẻ của G. Nếu thêm vào cạnh mới (A, m, B), thì đồ thị nhận được G1 thỏa
mãn điều kiện bổ đề 2.4.3, nên nó có chu trình Euler α. Chu trình α đi qua
mỗi cạnh của đồ thị G đúng một lần và qua cạnh (A, m, B) cũng đúng một
lần, nên khi loại cạnh mới ra khỏi α thì phần còn lại chính là xích Euler của
đồ thị G.
Hệ quả được chứng minh.
Thuật toán để tìm trực tiếp chu trình Euler
(cid:3)
Để tìm chu trình Euler của đa đồ thị G ta thực hiện thuật toán sau:
Xuất phát từ một đỉnh tùy ý của G, mỗi khi đi qua một cạnh ta “xóa” cạnh
đó đi và ghi lại theo thứ tự từ trái sang phải.
Khi thực hiện thuật toán này cần lưu ý: Mỗi khi gặp cạnh bắc cầu cần “xóa”
hết một trong hai thành phần liên thông rồi mới “xóa” cạnh bắc cầu.
Chú ý : Nếu đa đồ thị có hai đỉnh bậc lẻ, thì khi tìm xích Euler cần xuất phát
54
từ một trong hai đỉnh bậc lẻ và sẽ kết thúc tại đỉnh bậc lẻ kia.
Định nghĩa
2.4.2 Đường đi Hamilton và đồ thị Hamilton
Xích α trong đồ thị vô hướng G(X, E) được gọi là xích Hamilton nếu nó đi
qua tất cả các đỉnh của G và qua mỗi đỉnh đúng một lần. Nói cách khác, xích
Hamilton của đồ thị G là một xích sơ cấp và đi qua tất cả các đỉnh của G.
Chu trình α của đồ thị G được gọi là chu trình Hamilton nếu nó đi qua tất
cả các đỉnh của G và qua mỗi đỉnh đúng một lần. Nói cách khác, chu trình
Hamilton của đồ thị G là một chu trình sơ cấp và đi qua tất cả các đỉnh của
G.
Đồ thị vô hướng G được gọi là đồ thị Hamilton nếu nó có chu trình Hamilton.
Đường β của đồ thị có hướng G được gọi là đường Hamilton nếu nó đi qua
tất cả các đỉnh của đồ thị G và qua mỗi đỉnh đúng một lần. Nói cách khác,
đường Hamilton của đồ thị có hướng G là một đường sơ cấp và đi qua tất cả
các đỉnh của G.
Vòng Hamilton trong đồ thị vô hướng G được gọi là vòng Hamilton nếu nó
đi qua tất cả các đỉnh của đồ thị G và qua mỗi đỉnh đúng một lần. Nói cách
khác, vòng Hamilton là một vòng sơ cấp và đi qua tất cả các đỉnh của G.
Đồ thị vô hướng G được gọi là đồ thị Hamilton nếu nó có vòng Hamilton.
Đồ thị vô hướng G được gọi là đồ thị thuần nhất bậc k nếu mỗi đỉnh của
đồ thị G đều có bậc bằng k.
Đồ thị có hướng G được gọi là đồ thị tựa đối xứng cấp k nếu mỗi đỉnh của
đồ thị G có đúng k cung đi vào và k cung đi ra.
Đồ thị liên thông và không có điểm khớp được gọi là đồ thị không khớp.
Năm 1857, nhà toán học người Ailen là Hamilton (1805 - 1865) đưa ra trò
chơi “đi vòng quanh thế giới” như sau:
Chọn trước trên Trái Đất 20 thành phố A, B, C, D, E, F, G, H, I, J, K, L, M,
N, O, P, Q, R, S, T . Để đơn giản ta giả sử rằng các thành phố này là đỉnh của
55
một hình 12 mặt đều (đó là đa diện có 12 mặt ngũ giác đều và 20 đỉnh) thay
cho Trái Đất, còn các cạnh của đa diện biểu hiện cho đường đi giữa các thành
phố.
Một khách du lịch xuất phát từ một thành phố, hãy tìm đường đi thăm tất
cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chỗ cũ. Hỏi có
bao nhiêu cách đi ?
Hamilton đã giải quyết bài toán trên bằng cách chỉ ra nguyên tắc đi như
sau: khách du lịch khi tới đầu mút một cạnh, nếu anh ta chọn cạnh bên trái
mình thì phép chọn được ký hiệu bằng T , chọn cạnh phía phải ký hiệu bằng
P , và ở nguyên tại chỗ ký hiệu bằng 1. Tích của phép chọn được xác định theo
nguyên tắc: P T là phép chọn đi theo cạnh phải rồi tiếp tục đi theo cạnh trái, T T P hay T 2P là phép chọn đi theo cạnh trái 2 lần sau đó đi theo cạnh phải 1
lần... Hai phép chọn là bằng nhau nếu xuất phát từ cùng một điểm và cùng đi
tới một điểm khác. Tích không có tính chất giao hoán (T P (cid:54)= P T ) nhưng có
Hình 2.10
tính kết hợp, chẳng hạn (T T )P = T (T P ).
Ta có các công thức:
P 5 = T 5 = 1; P T 2P = T P T ; T P 2T = P T P ; T P 3T = P 2; P T 3P = T 2.
Nên
1 = P 5 = P 2P 3 = (T P 3T )P 3 = (T P 3)2 = [T (T P 3T )P ]2 = . . .
= T T T P P P T P T P T T T P P P T P T P
Khi đó ta có một cách đi như sau A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P,
56
Q, R, S, T, A.
Điều kiện tồn tại chu trình Hamilton
Một số kết quả nhận được từ [5] như sau:
Bổ đề 2.4.4. Nếu đồ thị vô hướng G(X, E) có chu trình Hamilton thì G là đồ
thị không khớp và mỗi đỉnh của nó đều có bậc không nhỏ hơn 2.
Chứng minh.
Thật vậy, nếu đồ thị G(X, E) có chu trình Hamilton α. Chu trình α qua tất
cả các đỉnh, không có điểm khớp và mỗi đỉnh đều bậc 2 nên đồ thị G không
thể có điểm khớp và bậc của mỗi đỉnh phải có bậc không nhỏ hơn 2.
(cid:3)
Bổ đề 2.4.5. Đồ thị vô hướng G(X, E) có n (n (cid:62) 3) đỉnh liên thông, thuần
nhất bậc hai có chu trình Hamilton.
Chứng minh.
Giả sử đồ thị vô hướng G(X, E) (|X| = n (cid:62) 3), liên thông thuần nhất bậc
hai.
Đồ thị G hữu hạn nên số xích sơ cấp trong G cũng hữu hạn.
Giả sử α = (x1, x2, . . . , xk−1, xk) là một trong những xích sơ cấp có độ dài
dài nhất (|α|max).
y ∈ G . Do G liên thông nên phải có ít nhất Nếu k < n thì tồn tại đỉnh y /∈ α
một đỉnh thuộc α kề với đỉnh y, chẳng hạn xi.
Nếu i = 2, 3, 4, . . . , k − 1 thì m(xi) > 2, vô lý.
Nếu i = 1 hoặc i = k thì xích (y, x2, . . . , xk−1, xk) hoặc xích (x1, x2, . . . , xk−1,
xk, y) có độ dài bằng |α| + 1 (cid:62) |α|max nên cũng dẫn đến mâu thuẫn.
Do đó k = n, tức là ta được xích Hamilton.
57
Vì m(x1) = m(xn) = 2 nên x1 phải kề với xn (không thể kề với đỉnh xi, 3 (cid:54) i (cid:54) n−1, vì bậc của mỗi đỉnh này đã bằng 2). Ta được chu trình Hamilton. (cid:3)
Bổ đề 2.4.6. Đồ thị vô hướng G(X, E)có chu trình Hamilton khi và chỉ khi
nó có một đồ thị bộ phận liên thông và thuần nhất bậc hai.
Chứng minh.
1) Điều kiện cần là hiển nhiên. Bởi vì nếu đồ thị G có chu trình Hamilton
thì mỗi chu trình Hamilton của G là một đồ thị bộ phận liên thông thuần nhất
bậc hai.
2) Điều kiện đủ
Giả sử đồ thị G(X, E) có đồ thị bộ phận G1(X; E1) liên thông và thuần
nhất bậc hai. Theo bổ đề 2.4.5 đồ thị G1 có chu trình Hamilton α. Khi đó, chu
trình α cũng chính là chu trình Hamilton trong đồ thị G. Định lý được chứng
minh.
(cid:3)
Bổ đề 2.4.7. Nếu α = [x1, x2, x3, ..., xk−1, xk] là xích sơ cấp có độ dài cực đại trong đồ thị G và m(x1) + m(xk) (cid:62) k thì đồ thị con G1 gồm các đỉnh x1, x2, ..., xk−1, xk sẽ lập thành một đồ thị Hamilton gồm k đỉnh.
Chứng minh.
1) Nếu x1, xk kề nhau thì α là một chu trình sơ cấp đi qua tất cả các đỉnh
của đồ thị con G1.
2) Nếu x1, xk không kề nhau.
Do α là xích cực đại nên x1 cũng như xk không thể kề với một đỉnh nào
ngoài α. Xét các cặp đỉnh có khả năng là cạnh của đồ thị, một đầu là x1 hoặc
58
xk.
(1) (x1, x2)
(∗) (2) (xk, x3) (x1, x3)
(3) (xk, x3) (x1, x4)
. . . . . . . . . . . . . . .
(i) (xk, xi) (x1, xi+1)
(i+1) (xk, xi+1) (x1, xi+2)
. . . . . . . . . . . . . . .
(k - 2) (xk, xk−2) (x1, xk−1)
(k-1) (xk, xk−1)
m(xk) + m(x1).
Nếu từ hàng 2 đến hàng k − 2 mỗi hàng có không quá 1 cạnh thì số cạnh của
đồ thị G trong quan hệ (*) sẽ không vượt quá k − 1.
Do đó m(xk) + m(x1) (cid:54) k − 1 < k. Ta đi tới mâu thuẫn với giả thiết nên trong quan hệ (*) từ hàng 2 đến hàng
k − 2 phải có ít nhất một hàng mà cả hai cặp đỉnh đều là cạnh của đồ thị G. Chẳng hạn (xk, xi), (x1, xi+1), (2 (cid:54) i (cid:54) k − 2) đều là cạnh của đồ thị G. Ta sắp xếp lại xích α để được xích α(cid:48)
α(cid:48) = [xi+1, x1, x2, x3, . . . , xi−1, xi, xk, xk−1, ..., xi+3, xi+2].
Ta có xi+1, xi+2 kề nhau nên α(cid:48) là chu trình sơ cấp đi qua tất cả các đỉnh của G1. Vậy G1 là đồ thị Hamilton gồm k đỉnh.
(cid:3)
Bổ đề 2.4.8. Giả sử đồ thị vô hướng G(X, E) có n đỉnh và l = n − 1 hoặc l = n. Nếu ∀x, y ∈ X : m(x) + m(y) (cid:62) l thì trong G có xích sơ cấp có độ dài
cực đại chứa không ít hơn l đỉnh.
Chứng minh.
Với điều kiện đã cho thì G là đồ thị liên thông.
Giả sử α = [x1, x2, . . . , xk−1, xk] là một xích sơ cấp có độ dài cực đại nào đó
59
của đồ thị G. Khi đó k (cid:62) l.
Chứng minh bằng phản chứng: Thật vậy, giả sử k < l khi đó, từ điều kiện đã cho ta có m(xk) + m(xl) (cid:62) k và theo bổ đề 2.4.7, đồ thị con G1 gồm các đỉnh x1, x2, . . . , xk có chu trình
Hamilton. Giả sử β = [y1, y2, . . . , yk] là một trong những chu trình Hamlton
của G1 thì trong G, chu trình β là một chu trình sơ cấp. Do k < l nên có ít
nhất một đỉnh y của G nằm ngoài β. Vì G liên thông nên y phải nối với một
đỉnh nào đó của β, chẳng hạn y nối với yj bằng một xích có độ dài dương. Ta được xích sơ cấp mới β(cid:48) = [y, . . . , yj, yj−1, . . . , y1, yk, yk+1, ..., yj+2, yj+1] có độ dài lớn hơn α. Ta đi đến mâu thuẫn với tính độ dài cực đại của α.
Do đó k (cid:62) 1.
(cid:3)
(1) thì G có xích Hamilton.
Định lý 2.4.1. Giả sử đồ thị vô hướng G(X; E) có n đỉnh. a) Nếu ∀x, y ∈ X : m(x) + m(y) (cid:62) n − 1 b) Nếu ∀x, y ∈ X : m(x) + m(y) (cid:62) n (2) thì G có chu trình Hamilton.
Chứng minh.
1) Do điều kiện (1) theo bổ đề 2.4.8 trong đồ thị G có xích sơ cấp có độ
dài cực đại chứa không ít hơn n − 1 đỉnh. Giả sử α = [x1, x2, . . . , xl−1, xl] với l (cid:62) n − 1 là một trong những xích có độ dài cực đại.
a) Nếu l = n thì α là xích Hamilton của đồ thị G.
b) Nếu l = n − 1, theo bổ đề 2.4.7 đồ thị con G1 của G gồm các đỉnh
x1, x2, . . . , xn−1 có chu trình Hamilton. Giả sử một trong những chu trình
Hamilton của G1 là: β = [y1, y2, . . . , yn−2, yn−1].
Trong đồ thị G còn một đỉnh, chẳng hạn x không nằm trên β. Với điều kiện
(1), theo định lý 2.3.1 đồ thị G liên thông, nên x phải kề với một đỉnh nào đó thuộc β, chẳng hạn yi (1 (cid:54) i (cid:54) n − 1). Khi đó xích
γ = [x, yi, yi−1, . . . , y1, yn−1, yn−2, . . . , yi+1]
đi qua tất cả các đỉnh của đồ thị G, nên γ là một xích Hamilton của đồ thị G.
60
2) Với điều kiện (2) theo bổ đề 2.4.8 trong đồ thị G có xích sơ cấp có độ dài
cực đại chứa n đỉnh. Giả sử ω = [z1, z2, . . . , xn−1, zn] là một trong những xích
có độ dài cực đại.
Khi đó, theo bổ đề 2.4.7 đồ thị con G2 của G gồm các đỉnh z1, z2, . . . , zn−1, zn
có chu trình Hamilton. Giả sử ε = [p1, p2, ..., pn−1, pn] là một chu trình Hamilton
của G1. Chu trình ε là chu trình sơ cấp và đi qua tất cả n đỉnh của G nên trong
G, ε là một chu trình Hamilton. Định lý được chứng minh.
(cid:3)
Từ định lý trên ta có các hệ quả sau (theo [9]):
Hệ quả 2.4.3.
1) Mọi đồ thị đầy đủ vô hướng với ít nhất 2 đỉnh đều có xích Hamilton.
2) Mọi đồ thị đầy đủ vô hướng với ít nhất 3 đỉnh đều có chu trình Hamilton.
Hệ quả 2.4.4. (Định lý Dirac) Nếu bậc của mỗi đỉnh trong đồ thị vô hướng
G không nhỏ hơn một nửa số đỉnh thì nó có chu trình Hamilton.
Hệ quả 2.4.5. (Định lý Ore) Nếu G là một đơn đồ thị có n đỉnh và bất kỳ
hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một
đồ thị Hamilton.
Hình 2.11
Hệ quả 2.4.6. Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n (cid:62) 2) và bậc của mỗi đỉnh lớn hơn thì G là một đồ thị n 2 Hamilton (theo [9]).
61
- Đồ thị G có 8 đỉnh, đỉnh nào cũng có bậc 4, nên G là đồ thị Hamilton.
- Đồ thị G(cid:48) có 5 đỉnh bậc 4 và 2 đỉnh bậc 2 kề nhau nên tổng số bậc của
Điều kiện tồn tại đường Hamilton
hai đỉnh không kề nhau bất kỳ bằng 7 hoặc 8, nên G(cid:48) là đồ thị Hamilton.
Định lý 2.4.2. (Rédei) Trong đồ thị có hướng đầy đủ luôn luôn tồn tại đường
Hamilton.
Chứng minh.
(Thuật toán tìm đường Hamilton trong đồ thị đầy đủ có hướng)
Giả sử G(X, E) là đồ thị có hướng đầy đủ và α = [x1, x2, . . . , xi, xi+1, . . . , xk−1, xk]
là đường đi sơ cấp bất kỳ trong đồ thị G.
1) Nếu α đã đi qua tất cả các đỉnh của G thì nó là một đường đi Hamilton của
G.
2) Nếu trong G còn có đỉnh nằm ngoài α, thì ta có thể bổ sung dần các đỉnh
này vào α và các đường sơ cấp nhận được tiếp theo để cuối cùng nhận được
đường đi Hamilton.
Thật vậy, giả sử x là đỉnh tuỳ ý không nằm trên α.
a) Nếu có cung nối x với x1 thì bổ sung x vào đầu của đường đi α để được α1
mà |α1| = |α| + 1, nghĩa là α1 = [x, x1, x2, . . . , xi, xi+1, . . . , xk−1, xk]. b) Nếu tồn tại chỉ số i (1 (cid:54) i (cid:54) k − 1) mà từ xi có cung đi tới x và từ x có cung đi tới xi+1 thì ta chen x vào giữa xi và xi+1 để được đường đi sơ cấp α2
mà |α2| = |α| + 1, nghĩa là α2 = [x1, x2, . . . , xi, x, xi+1, . . . , xk−1, xk]. c) Nếu cả hai khả năng trên đều không xảy ra nghĩa là với mọi i (1 (cid:54) i (cid:54) k)
, xi đều có cung đi tới x. Khi đó bổ sung x vào cuối của đường đi α và được
đường đi α2 = [x1, x2, . . . , xi, xi+1, . . . , xk−1, xk, x].
Nếu đồ thị G có n đỉnh thì sau n − k bổ sung ta sẽ nhận được đường đi
Hamilton.
Định lý được chứng minh.
62
(cid:3)
2.4.3 Ứng dụng
Bài toán 2.4.1. (xem [7]) Chứng minh rằng: ta có thể tô màu các cạnh của
một đồ thị liên thông G bởi hai màu xanh - đỏ sao cho số cạnh đỏ và số cạnh
xanh xuất phát tại một đỉnh của đồ thị luôn bằng nhau khi và chỉ khi đồ thị
G có một số chẵn cạnh và bậc của mỗi đỉnh của G là một số chẵn.
Giải.
Nếu ta có thể tô màu các cạnh của một đồ thị liên thông G bằng hai màu
xanh - đỏ sao cho số cạnh đỏ và số cạnh xanh xuất phát tại mỗi đỉnh của đồ
thị luôn luôn bằng nhau thì bậc của đồ thị tại mỗi đỉnh phải là chẵn (số cạnh
xanh và số cạnh đỏ tại mỗi đỉnh bằng nhau); và đồ thị có một số chẵn cạnh
(do số cạnh xanh và số cạnh đỏ của đồ thị bằng nhau).
Ngược lại, giả sử đồ thị liên thông G có chẵn cạnh và bậc của các đỉnh là số
chẵn thì đồ thị G có đường một nét Euler khép kín H nào đó. Do G có số chẵn
cạnh nên H có chẵn cạnh. Như thế ta có thể tô màu các cạnh của H bằng hai
màu xanh - đỏ sao cho hai cạnh liên tiếp nhau trên H khác màu nhau. Khi đó
cạnh đi ra và cạnh đi vào dọc theo H tại mỗi đỉnh khác màu nhau. Do đó, số
cạnh màu xanh và màu đỏ tại mỗi đỉnh của G bằng nhau.
Bài toán 2.4.2. (xem [9]) Bài toán người phát thư Trung Hoa:
Một nhân viên đi từ Sở Bưu Điện, qua một số đường phố để phát thư, rồi
quay về Sở. Người ấy phải đi qua các đường theo trình tự nào để đường đi là
ngắn nhất?
Bài toán được nhà toán học Trung Hoa Guan nêu lên đầu tiên (1960), vì
vậy thường được gọi là “bài toán người phát thư Trung Hoa”. Ta xét bài toán
ở một dạng đơn giản như sau.
Cho đồ thị liên thông G. Một chu trình qua mọi cạnh của G gọi là một hành
trình trong G. Trong các hành trình đó, hãy tìm hành trình ngắn nhất, tức là
qua ít cạnh nhất.
Rõ ràng rằng nếu G là đồ thị Euler (mọi đỉnh đều có bậc chẵn) thì chu
63
trình Euler trong G (qua mỗi cạnh của G đúng một lần) là hành trình ngắn
nhất cần tìm.
Chỉ còn phải xét trường hợp G có một số đỉnh bậc lẻ (số đỉnh bậc lẻ là một
số chẵn). Khi đó, mọi hành trình trong G phải đi qua ít nhất hai lần một số
cạnh nào đó.
Dễ thấy rằng một hành trình qua một cạnh (u, v) nào đó quá hai lần thì
không phải là hành trình ngắn nhất trong G. Vì vậy, ta chỉ cần xét những hành
trình T đi qua hai lần một số cạnh nào đó của G.
Ta quy ước xem mỗi hành trình T trong G là một hành trình trong đồ thị
Euler GT , có được từ G bằng cách vẽ thêm một cạnh song song đối với những
cạnh mà T đi qua hai lần. Bài toán đặt ra được đưa về bài toán sau:
Trong các đồ thị Euler GT , tìm đồ thị có số cạnh ít nhất (khi đó chu trình
Euler trong đồ thị này là hành trình ngắn nhất).
Định lý (Gooodman và Hedetniemi, 1973). (Theo [9]) Nếu G là một đồ thị
liên thông có q cạnh thì hành trình ngắn nhất trong G có chiều dài q + m(G),
trong đó m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như
sau:
Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k phần tử
của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V0(G).
Ta gọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u, v). Đối với
mọi phân hoạch cặp Pi, ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi
tính tổng d(Pi). Số m(G) bằng cực tiểu của các d(Pi):
m(G) = min d(Pi)
Giải bài toán người phát thư Trung Hoa cho trong đồ thị sau:
Tập hợp các đỉnh bậc lẻ V0(G) = {B, G, H, K} và tập hợp các phân hoạch
cặp là P = {P1, P2, P3}, trong đó
P1 = {(B, G), (H, K)} → d(P1) = d(B, G) + d(H, K) = 4 + 1 = 5,
P2 = {(B, H), (G, K)} → d(P2) = d(B, H) + d(G, K) = 2 + 1 = 3,
64
P3 = {(B, K), (G, H)} → d(P3) = d(B, K) + d(G, H) = 3 + 2 = 5,
Hình 2.12
m(G) = min{d(P1), d(P2), d(P3)} = 3.
Do đó GT có được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K)
vào nên GT là đồ thị Euler. Vậy hành trình ngắn nhất cần tìm là đi theo chu
trình Euler trong GT :
A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A.
Bài toán 2.4.3. Trong một giải thi đấu cầu lông có n (n (cid:62) 2) vận động viên
tham gia. Mỗi vận động viên gặp từng vận động viên khác đúng một lần. Trong
thi đấu cầu lông chỉ có khả năng thắng hoặc thua (trong thi đấu cầu lông chỉ
có khả năng thắng hoặc thua). Chứng minh rằng sau giải đấu có thể xếp tất cả
các vận động viên đứng thành một hàng dọc, để người đứng sau thắng người
đứng ngay trước vận động viên đó.
Giải.
Xây dựng đồ thị có hướng G như sau:
Đỉnh của đồ thị G: Lấy n điểm trên mặt phẳng, không có ba điểm nào
thẳng hàng và tương ứng với các vận động viên. Dùng ngay số áo của các vận
động viên để ghi tên các điểm tương ứng.
Cạnh của đồ thị G: có một cung nối từ đỉnh x đến đỉnh y nếu vận động
viên x thắng vận động viên y.
Như vậy, đồ thị có hướng G có tính chất là với hai đỉnh phân biệt bất kỳ x
và y, có một và chỉ một trong hai cung (x, y) hoặc (y, x), đồ thị như thế được
gọi là đồ thị có hướng đầy đủ. Theo định lý 2.4.2, G có một đường Hamilton.
65
Giả sử β là một trong những đường Hamilton của G. Khi đó theo thứ tự của
các đỉnh xuất hiện trong β mà sắp xếp các vận động viên tương ứng đứng theo
một hàng dọc thì vận động viên đứng sau sẽ thắng vận động viên đứng trước.
Bài toán 2.4.4. (xem [9]) Hành trình của con Mã trên bàn cờ (Euler). Liệu
con Mã có thể di chuyển qua tất cả các ô của bàn cờ 8 x 8 và qua mỗi ô đúng
một lần (rồi trở về được ô xuất phát).
Giải.
Xây dựng đồ thị G gồm 64 đỉnh, trong đó mỗi đỉnh ứng với một ô của bàn
cờ vua 8 x 8. Khi đó, con Mã có thể di chuyển được qua tất cả các ô của bàn
cờ và qua mỗi ô đúng một lần (và trở về được ô xuất phát) khi và chỉ khi trên
Hình 2.13
đồ thị G có xích Hamilton (chu trình Hamilton). Một lời giải của bài toán:
Bài toán 2.4.5. (xem [9]) Bài toán sắp xếp chỗ ngồi:
Có n đại biểu từ n nước đến dự một Hội nghị quốc tế. Mỗi ngày họp một
lần ngồi quanh một bàn tròn. Hỏi phải bố trí bao nhiêu ngày và bố trí như thế
nào sao cho trong mỗi ngày, mỗi người có hai người kế bên là bạn mới. Lưu ý
rằng n người đều muốn làm quen với nhau.
Giải.
Xét đồ thị G gồm n đỉnh, mỗi đỉnh ứng với một người dự hội nghị. Ta lấy
66
mã thẻ dự hội nghị để ghi tên các đỉnh tương ứng.
Hai đỉnh kề nhau khi hai đại biểu tương ứng muốn làm quen với nhau. Như
vậy, ta có đồ thị đầy đủ Kn. Đồ thị này là đồ thị Hamilton và rõ ràng mỗi chu
trình Hamilton là một cách sắp xếp như yêu cầu của bài toán.
Bài toán trở thành tìm các chu trình Hamilton phân biệt của đồ thị đầy đủ
chu trình Hamilton n − 1 2 Kn (hai chu trình Hamilton gọi là phân biệt nếu chúng không có cạnh chung). Bổ đề : Đồ thị đầy đủ Kn với n lẻ và n (cid:62) 3 có đúng phân biệt. Chứng minh.
cạnh và mỗi chu trình Hamilton có n cạnh, nên số chu trình Kn có n(n − 1) 2
Hình 2.14
Hamilton phân biệt nhiều nhất là . n − 1 2
Giả sử các đỉnh của Kn là 1, 2, ..., n. Đặt đỉnh 1 tại tâm của một đường tròn
và các đỉnh 2, ..., n đặt cách đều nhau trên đường tròn (mỗi cung là sao 3600 n − 1 cho đỉnh lẻ nằm ở nửa đường tròn trên và đỉnh chẵn nằm ở nửa đường tròn
dưới. Ta có ngay chu trình Hamilton đầu tiên là 1, 2, ..., n, 1. Các đỉnh được giữ
cố định, xoay khung theo chiều kim đồng hồ với các góc quay:
, 2. , 3. . . . , . 3600 n − 1 3600 n − 1 3600 n − 1 n − 3 2 3600 n − 1
khung phân biệt với khung đầu tiên. ta nhận được
chu trình Hamilton phân biệt. (cid:3) Giải bài toán sắp xếp chỗ Do đó ta có
n − 3 2 n − 1 2 ngồi với n = 11.
67
Có = 5 cách sắp xếp chỗ ngồi phân biệt như sau: 11 − 1 2
1
2
3
4
5
6
7
8
9
10
11
1
1
3
5
2
7
4
9
6
11
8
10
1
1
5
7
3
9
2
11
4
10
6
8
1
1
7
9
5
11
3
10
2
8
4
6
1
1
9
11
7
10
5
8
3
6
2
4
1
Hình 2.15
Bài toán 2.4.6. (Đường đi của con Mã) Hai người chơi một trò chơi trên bàn
cờ như sau. A đặt quân mã lên ô bất kì của bàn cờ. Sau đó B dẫn con mã đi
một bước trên bàn cờ theo qui tắc bước nhảy thông thường của con mã. Mỗi
ô trên bàn cờ chỉ được đến một lần. Hỏi ai sẽ thắng và thắng bằng cách nào?
Giải.
Xây dựng một đồ thị với các đỉnh là 64 ô trên bàn cờ, còn hai ô được nối
với nhau bởi một cạnh nếu con mã có thể nhảy từ ô này tới ô kia. Do số đỉnh
(bằng 32) là chẵn, nên ta có thể tìm được một bộ 32 cạnh đôi một không liền
kề. Rõ ràng B có thể thắng A nếu bằng cách luôn dẫn con mã theo các cạnh
của tập hợp 32 cạnh được đánh dấu này.
Đồ thị này có một chu trình Hamilton. Người cuối cùng không có bước đi
là A. Vậy B đi trước thắng.
Bài toán 2.4.7. (xem [5]) Hình 2.16 cho sơ đồ nhà ở của 8 học sinh A, B, C, D, E, G, H, K.
68
Hãy tìm một đường đi từ nhà học sinh A qua nhà mỗi học sinh khác đúng
1 lần để cùng đến sân vận động S (Khi A đến nhà bạn nào thì bạn đó cùng A
đến sân vận động).
Giải.
Trước hết ta thấy các đỉnh A, E, C đều có đỉnh bậc 2, bởi vậy đường Hamil-
ton xuất phát từ A phải đi qua cạnh BC, CD, DE, EG. Khi đó ta xóa đi các
cạnh BD, DK, DH (đánh dấu x), đồng thời cạnh AG cũng được xóa (đánh
Hình 2.16
dấu xx)
Tiếp theo học sinh A đi tiếp từ G sang H rồi sang K và cuối cùng từ đỉnh
K sang đỉnh S. Đường Hamilton được tạo thành. ABCDEGHKS mô tả toàn
bộ hành trình của học sinh xuất phát từ A và đi tới sân vận động S, theo đúng
yêu cầu của bài toán đặt ra.
Bài toán 2.4.8. Vị trí nhà ở và đường nối giữa các nhà của 9 học sinh
A, B, C, E, F, G, H, K được mô tả trên hình 2.17. Chứng minh rằng:
a. Bạn A không thể đi đến nhà bạn K với điều kiện: Trên đường đi A phải
ghé qua nhà từng bạn khác đúng 1 lần;
b. Mỗi bạn đều có thể qua thăm từng bạn khách đúng một lần rồi lại trở
về được nhà mình.
Giải.
a). Thực chất bài toán yêu cầu chứng minh đồ thị trên Hình 2.17 không có
xích Hamilton nối giữa đỉnh A và đỉnh K.
Thật vậy, nếu trong đồ thị có xích Hamilton (α) nối giữa đỉnh A và đỉnh
69
K, thì phải đi qua tất cả các đỉnh còn lại, trong đó có các đỉnh bậc bằng 2:
E, F, G; nghĩa là phải đi qua các cạnh AE, ED, DF, F K, CG, GH. Có hai khả
năng xảy ra:
- Nếu α không đi qua đỉnh nào 2 lần, thì nó không thể đồng thời qua được
3 đỉnh E, F, G;
- Ngược lại, nếu α đi qua được cả 3 đỉnh E, F, G thì nó phải đi qua một
đỉnh nào đó từ 2 lần trở lên.
Như vậy đã đi tới mẫu thuẫn với tính chất của xích Hamilton nên không
Hình 2.17
tồn tại xích Hamilton nối giữa đỉnh A và đỉnh K. Bài toán được chứng minh.
b) Đồ thị trong hình 2.17 có chu trình Hamilton, chẳng hạn,
β = A, E, D, F, K, H, G, C, B, A
nên mỗi em đều xuất phát từ vị trí của mình, đi theo chu trình β, thì sẽ thăm
được từng bạn đúng một lần rồi lại trở về được nhà mình.
2.5 Bài toán liên quan đến đồ thị tô màu
2.5.1 Định nghĩa
Cho trước một số nguyên dương p. Ta nói rằng đồ thị G là p sắc nếu bằng p
màu khác nhau có thể tô trên các đỉnh (mỗi đỉnh một màu), sao cho hai đỉnh
kề nhau tùy ý đều có màu khác nhau.
Số p nhỏ nhất, mà đối với số đó đồ thị G là p sắc, được gọi là sắc số của đồ
70
thị G và ký hiệu bằng γ(G).
Nói cách khác, sắc số của một đồ thị là số màu ít nhất cần dùng để tô trên
các đỉnh của đồ thị (mỗi đỉnh một màu), sao cho hai đỉnh kề nhau tùy ý được
tô bằng hai màu khác nhau.
Sắc lớp là số màu ít nhất cần dùng để tô trên các cạnh của đồ thị (mỗi cạnh
một màu), sao cho hai cạnh kề nhau tùy ý đều có màu khác nhau.
Người ta có thể chuyển bài toán sắc lớp về bài toán sắc số bằng cách: Đối với mỗi đồ thị G = (X, U ) xây dựng đồ thị G(cid:48)(U, E), trong đó U là tập cạnh
của đồ thị G, còn tập cạnh E của nó được xác định như sau:
E = {(u, u(cid:48)) | u, u(cid:48) ∈ U và là hai cạnh kề nhau}.
Dễ dàng thấy rằng, sắc số của đồ thị G(cid:48) bằng số sắc lớp của đồ thị G.
2.5.2 Tính chất
Một số kết quả nhận được từ [5] như sau:
Định lý 2.5.1. Một chu trình có độ dài lẻ luôn có sắc số bằng 3.
Chứng minh.
Giả sử α là một chu trình có độ dài lẻ tùy ý. Khi đó tồn tại số tự nhiên n để
|α| = 2n+1. Ký hiệu các đỉnh của α một cách liên tiếp bằng x1, x2, ..., x2n, x2n+1.
Ta sẽ chứng minh khẳng định trên bằng quy nạp theo n.
a) Cơ sở quy nạp:
Với n = 1. Chu trình α gồm 3 đỉnh x1, x2, x3. Do mỗi đỉnh xi (1 (cid:54) i (cid:54) 3) đều kề với hai đỉnh còn lại nên ta phải dùng đúng 3 màu khác nhau thì mới
đủ tô trên mỗi đỉnh một màu, để cho hai đỉnh kề nhau tùy ý đều có màu khác
nhau.
b) Quy nạp:
Giả sử khẳng định đã đúng với n (cid:54) k, nghĩa là đối với chu trình α1 tùy ý
với độ dài 2n + 1 (1 (cid:54) n (cid:54) k) đều có sắc số bằng 3.
Cần chỉ ra rằng với n = k + 1 khẳng định vẫn đúng, nghĩa là chu trình α
71
tùy ý với độ dài 2(k + 1) + 1 cũng có sắc số bằng 3.
Giả sử α là chu trình có độ dài lẻ tùy ý có độ dài 2(k + 1) + 1 và có tập
đỉnh được đánh số liên tiếp {x1, x2, . . . , x2k+3}.
Nối đỉnh x1 với đỉnh x2k+1 ta thu được chu trình α1 với độ dài lẻ 2k + 1.
Theo giả thiết qui nạp sắc số của α1 bằng 3 đồng thời x1 và x2k+1 có màu khác
nhau. Chẳng hạn x1 được tô bằng màu M1 và x2k+1 được tô bằng M2. Khi đó
để tô đỉnh x2k+2 ta có thể dùng lại màu M1 và tô đỉnh x2k+3 ta dùng lại màu
M2. Nghĩa là không phải thêm màu mới. Vậy sắc số của α bằng 3 và khẳng
định được chứng minh.
(cid:3)
Định lý 2.5.2. (Định lý Konig) Đồ thị G = (X, U ) với ít nhất một cạnh là
đồ thị hai sắc khi và chỉ khi nó không có chu trình độ dài lẻ.
Chứng minh.
1) Điều kiện đủ : Giả sử đồ thị G = (X, U ) không có chu trình độ dài lẻ.
Cần chỉ ra G là đồ thị 2 - sắc. Có thể giả thiết G là đồ thị liên thông (nếu G
không liên thông ta xét riêng từng thành phần liên thông).
Ta tô màu dần dần các đỉnh của đồ thị G theo quy tắc sau đây:
a) Tô màu xanh cho đỉnh z tùy ý.
b) Nếu đỉnh x nào đó đã được tô màu xanh, ta dùng màu đỏ để tô cho tất
cả các đỉnh kề với x; nếu đỉnh y được tô màu đỏ, thì ta dùng màu xanh tô cho
tất cả các đỉnh kề với y.
Vì đồ thị G liên thông, nên sớm hay muộn mọi đỉnh của nó đều được tô
màu và mỗi đỉnh của G không thể cùng một lúc được tô màu xanh và màu đỏ.
Thậy vậy, giả sử trong G tồn tại đỉnh v mà theo nguyên tắc nó vừa phải tô
màu xanh, đồng thời lại phải được tô màu đỏ. Khi đó v đồng thời kề với đỉnh s
đã có màu xanh và đỉnh t đã có màu đỏ, nên các đỉnh s, v, t nằm trên một chu
trình độ dài lẻ. Như vậy, mâu thuẫn với giả thiết nên đỉnh v như trên không
tồn tại.
Mặt khác, do đồ thị có ít nhất một cạnh, nên cần phải dùng hai màu để tô
72
trên hai đỉnh của cạnh này.
Vậy G là một đồ thị 2 – sắc.
2) Điều kiện cần: Giả sử G là đồ thị 2 - sắc, nhưng trong G lại có chu trình
độ dài lẻ và α là một trong nhưng chu trình độ dài lẻ của G. Khi đó, theo
định lý 2.5.1, sắc số của α bằng 3. Mặt khác, sắc số của độ thị không nhỏ hơn
sắc số của bất kỳ đồ thị con nào, nên sắc số của G ít nhất bằng 3. Ta đi tới
mâu thuẫn với giả thiết, nên G không có chu trình độ dài lẻ. Khẳng định được (cid:3) chứng minh.
Từ định lý trên suy ra hệ quả sau:
Hệ quả 2.5.1. Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.
Định lý 2.5.3. Đồ thị đầy đủ với n đỉnh luôn luôn có sắc số bằng n.
Chứng minh.
Khẳng định được chứng minh bằng qui nạp theo số đỉnh của đồ thị. Dùng
Gn để ký hiệu đồ thị đầy đủ gồm n đỉnh.
1) Cơ sở quy nạp: Với n = 1: G1 gồm 1 đỉnh, nên phải dùng 1 màu.
2) Quy nạp: Giả sử khẳng định đúng với n = k, nghĩa là Gk tùy ý đã có
sắc số bằng k. Ta cần khẳng định tính đúng đắn của định lý đối với n = k + 1,
nghĩa là Gk+1 có sắc số bằng k + 1.
Giả sử Gk+1 là một đồ thì đầy đủ tùy ý với tập định:
x = {x1, x2, . . . , xk, xk+1}
Ta loại khỏi Gk+1 một đỉnh tùy ý, chẳng hạn đỉnh xk+1 cùng với các cạnh
thuộc nó. Đồ thị con nhận được cũng là một đồ thị đầy đủ Gk gồm k là đỉnh.
Nên theo giả thuyết qui nạp γ(Gk) = k.
“Khôi phục” lại đỉnh xk+1 cùng với các cạnh thuộc nó, tức là “trở lại” đồ thị
Gk+1. Vì xk+1 kề với từng đỉnh thuộc Gk, nên để tô màu cho xk+1 ta phải dùng
một màu chưa sử dụng trên Gk. Do đó:
γ(Gk+1) = γ(Gk) + 1 = k + 1.
Khẳng định đã được chứng minh.
73
(cid:3)
2.5.3 Thuật toán tìm sắc số
Nhờ các kết quả trên dễ dàng phát hiện được những đồ thị 2 - sắc, song đối
với các đồ thị loại khác, ta chưa có một phương pháp tổng quát để xác định
sắc số của chúng. Tuy vậy, đã có một số phương pháp đặc thù, cho phép xác
Phương pháp thực nghiệm
định sắc số của những lớp đồ thị nhất định.
Thoạt đầu dùng p màu tùy ý: 1, 2, . . . , p để tô trên các đỉnh. Sau đó tìm
cách loại dần từng màu một trong các màu đã tô (mà người ta gọi chúng là
các “màu tới hạn”), cho tới khi không có khẳ năng loại trừ, ta sẽ được sắc số
của đồ thị.
Muốn vậy, ta xét đỉnh x có “màu tới hạn” nào đó và các thành phần liên
1 = (X1, E1), C i,k
2 = (X2, E2), . . . , C i,k
t = (Xt, Et) của đồ thị con sinh bởi hai màu i và k. Dùng T (x) để ký hiệu tập đỉnh hoặc có cạnh hoặc có cung nối với x. Xét các giao Xs ∩ T (x) (1 (cid:54) s (cid:54) t). Có bốn khả năng xảy ra:
thông: C i,k
1) Nếu tất cả các tập đỉnh Xs ∩ T (x) (1 (cid:54) s (cid:54) t) đều cùng một màu. Chẳng hạn màu i thì ta dùng màu i để tô lên các đỉnh có màu k và dùng màu k tô lên các đỉnh có màu i trong mỗi tập Xs (1 (cid:54) s (cid:54) t) đồng thời dùng màu i tô lên đỉnh x.
2) Nếu như trong các tập Xs ∩ T (x) (1 (cid:54) s (cid:54) t) có một số tập màu i và các tập màu còn lại màu k, chẳng hạn các tập X1 ∩ T (x), X2 ∩ T (x), . . . , Xp ∩ T (x) màu i, còn các tập Xp+1 ∩ T (x), . . . , Xt ∩ T (x) màu k. Khi đó các tập Xs (1 (cid:54) s (cid:54) p) giữ nguyên màu ở các đỉnh, trong các tập Xs (p + 1 (cid:54) s (cid:54) t) ta đổi các đỉnh màu i sang màu k và màu k sang màu i và dùng màu k để tô lên đỉnh x.
3) Nếu Xs ∩ T (x) = ∅ (1 (cid:54) s (cid:54) t) ta dùng một màu trong hai màu i hoặc
k để tô lên đỉnh x.
Trong cả ba trường hợp trên ta đều thay được “màu tới hạn” ở đỉnh x bằng
một màu khác đã dùng để tô trên đỉnh của đồ thị, nên số màu đã giảm đi một.
4) Nếu có một trong những tập Xs ∩ T (x) (1 (cid:54) s (cid:54) t) mà hai màu, thì
74
không có khả năng áp dụng thuật toán này.
Phương pháp chứng minh cận trên và cận dưới.
Phương pháp này thích hợp với những đồ thị chứa ít đỉnh. Thuật toán gồm
hai bước:
1. Chứng minh cận dưới. Nhờ các định lí 2.5.1, 2.5.2, 2.5.3, hệ quả 2.5.1
hoặc bằng lí luận trực tiếp chỉ ra rằng:
(2.6) γ(G) (cid:62) p.
2. Chứng minh cận trên. Bằng cách tô trực tiếp chỉ ra rằng với p màu đủ để
tô trên các đỉnh, sao cho hai đỉnh kề nhau tùy ý đều có màu khác nhau, nghĩa
là:
(2.7) γ(G) (cid:54) p.
Khi đó suy ra rằng sắc số γ(G) của đồ thị G bằng p.
2.5.4 Lớp đồ thị có chu trình tam giác cùng màu
Để phục vụ cho việc giải quyết một lớp bài toán nào đó cần xét những dãy
số đặc biệt và đưa ra các khẳng định thích hợp, chẳng hạn, để xây dựng một
lớp đồ thị có chu trình tam giác cùng màu người ta đưa ra các dãy số nguyên
dương:
a1 = 2, a2 = 5, ..., an+1 = (n + 1)an + 1
u2 = 3, u3 = 6, ..., un+1 = (un − 1)n + 2
Định lý 2.5.4.
a) Một đồ thị đầy đủ vô hướng với an + 1 đỉnh, các cạnh được tô bằng n màu
luôn có chu trình tam giác cùng màu.
b) Một đồ thị đầy đủ vô hướng với un + 1 đỉnh, các cạnh được tô bằng n màu
luôn có chu trình tam giác cùng màu.
Chứng minh.
75
Chứng minh phần a) (Bằng quy nạp theo chỉ số n)
1) Cơ sở quy nạp: n = 1. Đồ thị đầy đủ tương ứng gồm a2 + 1 = 2 + 1 = 3
đỉnh lập thành một chu trình tam giác. Các cạnh của đồ thị này được tô bằng
một màu, nên chu trình tam giác lập nên G1 cùng màu.
2) Quy nạp: Giả sử khẳng định đã đúng với n = k, nghĩa là, đồ thị đầy đủ
bất kỳ Gk gồm ak + 1 đỉnh với các cạnh được tô bằng k màu đã có chu trình
tam giác cùng màu. Cần chứng tỏ khẳng định đúng với n = k + 1.
Xem xét đồ thị đầy đủ tùy ý Gk+1 với ak+1 + 1 đỉnh và các cạnh tô bằng
k + 1 màu.
Giả sử P là một đỉnh tùy ý của Gk+1. Khi đó P được nối với ak+1 =
(k + 1)ak + 1 đỉnh bằng các cạnh được tô bằng không quá k + 1 màu, nên xuất
phát từ P phải có ít nhất ak + 1 cạnh được tô bằng cùng một màu. Giả sử màu này là màu đỏ và các cạnh P A1, P A2, . . . , P Aak, P Aak+1 được tô màu đỏ. Có hai khả năng xảy ra:
1) Nếu một trong các cạnh nối giữa các đỉnh Ai, Aj (1 (cid:54) i, j (cid:54) ak + 1) được tô màu đỏ, chẳng hạn cạnh (A1, A2) màu đỏ. Khi đó chu trình tam giác A1P A2
màu đỏ nên đồ thị Gk+1 có chu trình tam giác màu đỏ.
2) Trong trường hợp ngược lại, không có cạnh nào trong các cạnh (Ai, Aj) (1 (cid:54) i, j (cid:54) ak + 1) được tô màu đỏ. Khi đó đồ thị con đầy đủ Gk với tập đỉnh {A1, A2, ..., Aak, Aak+1} có các cạnh được tô bằng không quá k màu nên theo giả thiết qui nạp Gk đã có chu trình tam giác cùng màu. Bởi vậy Gk+1 có chu
trình tam giác cùng màu. Khẳng định được chứng minh.
Phần b) chứng minh tương tự.
(cid:3)
Định lý 2.5.5. ( Định lý bốn màu của Appel - Haken) Mọi đồ thị phẳng
đều có thể tô đúng bằng 4 màu.
Định lý bốn màu đầu tiên được đưa ra như một phỏng đoán vào năm 1850
bởi một sinh viên người Anh tên là F.Guthrie. Đến năm 1976, nhờ công cụ
máy tính điện tử, hai nhà toán học Mỹ là Kenneth Appel và Wolfgang Haken
76
đã tìm ra lời giải của “bài toán bốn màu” (theo [7]).
2.5.5 Ứng dụng
Bài toán 2.5.1. (xem [9]) Bài toán lập lịch thi: Hãy lập lịch thi trong trường
đại học sao cho không có sinh viên nào có hai môn thi cùng một lúc.
Giải.
Có thể giải bài toán lập lịch thi bằng mô hình đồ thị, với các đỉnh là các
môn thi, có một cạnh nối hai đỉnh nếu có sinh viên phải thi cả hai môn được
biểu diễn bằng hai đỉnh này. Thời gian thi của mỗi môn được biểu thị bằng
các màu khác nhau. Như vậy việc lập lịch thi sẽ tương ứng với việc tô màu đồ
Hình 2.18
thị này.
Chẳng hạn, có 7 môn thi cần xếp lịch. Giả sử các môn học đuợc đánh số từ
1 tới 7 và các cặp môn thi sau có chung sinh viên: 1 và 2, 1 và 3, 1 và 4, 1 và
7, 2 và 3, 2 và 4, 2 và 5, 2 và 7, 3 và 4, 3 và 6, 3 và 7, 4 và 5, 4 và 6, 5 và 6, 5
và 7, 6 và 7. Hình dưới đây biểu diễn đồ thị tương ứng. Việc lập lịch thi chính
là việc tô màu đồ thị này. Vì số màu của đồ thị này là 4 nên cần có 4 đợt thi.
Bài toán 2.5.2. Trên mặt phẳng lấy 6 điểm, không có ba điểm nào thẳng
hàng, khoảng cách giữa các cặp điểm khác nhau từng đôi một. Chứng minh
rằng tồn tại ít nhất một cặp điểm, mà đoạn thẳng nối giữa chúng là cạnh ngắn
nhất thuộc một tam giác nào đó, đồng thời cạnh dài nhất của một tam giác
khác trong các tam giác có đỉnh là các điểm đã cho?
77
Giải.
Để giải bài toán trên trước hết dùng màu xanh để tô mỗi đoạn thẳng là
cạnh ngắn nhất của một tam giác nào đó trong các tam giác có đỉnh là các
điểm đã cho. Phần cạnh còn lại được tô màu đỏ. Khi đó được đồ thị G2 gồm
6 đỉnh, các cạnh được tô bằng hai màu.
Theo định lý 2.5.4, đồ thị G2 có chu trình tam giác cùng màu. Do khoảng
cách giữa các cặp điểm đã cho khác nhau từng đôi một, nên tam giác bất kỳ
với đỉnh là các điểm đã cho đều có cạnh ngắn nhất, mà cạnh này được dùng
màu xanh để tô trước. Bởi vậy chu trình tam giác cùng màu phải là tam giác
xanh. Khi đó cạnh dài nhất trong tam giác này chính là đoạn thẳng cần tìm.
Bài toán 2.5.3. Mười bảy nhà khoa học đã đến dự hội nghị quốc tế: Mỗi
người trong số họ chỉ biết một trong ba ngoại ngữ: Anh, Nga, Pháp. Chứng
minh rằng có ít nhất ba nhà khoa học cùng biết một trong ba ngoại ngữ nói
trên.
Giải.
Lấy 17 điểm, không có 3 điểm nào thẳng hàng và tương ứng với 17 nhà khoa
học đến dự họp. Đoạn thẳng nối giữa hai điểm tương ứng với hai nhà khoa
học:
- Cùng biết tiếng Anh được tô màu xanh.
- Cùng biết tiếng Nga được tô màu đỏ.
- Cùng biết tiếng Pháp được tô màu vàng.
Khi đó được đồ thị đầy đủ gồm G3 gồm 17 đỉnh, các cạnh được tô bằng 3
màu, nên theo định lý 2.5.4, tương ứng với n = 3, đồ thị G3 có chu trình tam
giác cùng màu. Do đó ba nhà khoa học tương ứng với ba đỉnh thuộc chu trình
này biết cùng một ngoại ngữ.
Bài toán 2.5.4. Chứng minh rằng trong không gian có 6 đường thẳng, trong
đó không có 3 đường thẳng nào đồng qui tại một điểm, không có 3 đường thẳng
nào đồng phẳng và không có 3 đường thẳng nào song song, thì nhất định có 3
đường thẳng đôi một chéo nhau.
78
Giải.
Ta chuyển bài toán về dạng đồ thị bằng cách lấy 6 điểm không có 3 điểm
nào thẳng hàng và tương ứng với 6 đường thẳng đã cho. Mỗi cặp điểm được nối
bằng một đoạn thẳng màu xanh khi và chỉ khi các đường thẳng tương ứng với
chúng chéo nhau. Các cặp điểm còn lại được nối bằng một đoạn thẳng tô màu
đỏ. Ta được một đồ thị G đầy đủ gồm 6 đỉnh và các cạnh được tô bằng hai
màu: xanh, đỏ; theo định lý 2.5.4, đồ thị G có tam giác cùng màu. Theo điều
kiện đầu bài ba đường thẳng bất kỳ đều có hai đường thẳng chéo nhau, nên
tam giác tùy ý có đỉnh là các điểm đã chọn đều có ít nhất một cạnh màu xanh
nên tam giác cùng màu phải là tam giác màu xanh. Ba đường thẳng tương ứng
với 3 đỉnh của tam giác xanh sẽ chéo nhau đôi một.
Bài toán 2.5.5. (xem [6]) Cho n điểm trên mặt phẳng sao cho không có ba
điểm nào thẳng hàng. Một số cặp điểm được nối bằng các đoạn thẳng tô màu
xanh hoặc đỏ, sao cho hai điểm bất kỳ đều được nối với nhau bằng một đường
gấp khúc duy nhất gồm các đoạn thẳng đã được tô màu.
Chứng minh rằng có thể tô nốt các đoạn thẳng còn lại (có hai đầu tại n
điểm đã cho) bằng màu xanh hoặc đỏ, để bất kỳ tam giác nào (có các đỉnh tại
n điểm đã cho) cũng có số cạnh tô đỏ là lẻ.
Giải.
Coi mỗi điểm đã cho là 1 đỉnh, còn các cạnh là các đoạn thẳng đã nối giữa
các cặp điểm của đồ thị G. Theo điều kiện đầu bài G liên thông nên giữa hai
đỉnh được nối bằng một xích duy nhất và các cạnh của đồ thị được tô bằng
hai màu.
Giả sử x, y là hai đỉnh không kề nhau. Ta bổ sung và đồ thị G cạnh nối x
với y và tô màu cho cạnh này như sau:
Ký hiệu D(x, y) là xích duy nhất nối giữa x và y. Khi đó:
- Cạnh (x, y) được tô màu xanh, nếu D(x, y) có một số lẻ cạnh xanh;
- Cạnh (x, y) được tô màu đỏ, nếu D(x, y) có một số chẵn cạnh xanh;
Rõ ràng cách tô màu này phù hợp với cả trường hợp D(x, y) trùng với (x, y),
79
(cạnh (x, y) đã được tô màu từ trước).
Xét chu trình tam giác bất kỳ (x, y, z, x). Ta sẽ chỉ ra rằng: có thể chọn thêm
một đỉnh a, sao cho các đường đã tô màu trước đó D(x, a), D(y, a), D(z, a)
không có đỉnh chung nào khác đỉnh a (a có thể trùng với x, y, z, chẳng hạn a
trùng với x. Khi đó D(x, a) là một đỉnh. Thật vậy, từ z đi theo xích D(z, x)
cho đến khi gặp được D(x, y) tại một đỉnh. Đó chính là đỉnh a (nếu không gặp
các đỉnh trên đường đi, thì sẽ gặp ở đầu mút x). Ký hiệu p, q, r là số cạnh tô
màu xanh của các xích D(x, a, y) D(y, a, z), D(z, a, x). Theo cách chọn màu,
số các cạnh tô màu xanh của chu trình (x, y, z, x) đúng bằng số các số lẻ bộ ba
p, q, r.
Do mỗi cạnh tô xanh của D(a, x), D(a, y), D(a, x) được tính hai lần, nên
p + q + r là một số chẵn. Bởi vậy các số lẻ trong bộ ba p, q, r là số chẵn. Do đó
số cạnh xanh của chu trình tam giác (x, y, z, x) chẵn. Từ đó suy ra số cạnh đỏ
của chu trình này phải lẻ.
Bài toán 2.5.6. Có 5 thành phố, từ mỗi thành phố có đường hàng không đến
một số thành phố khác. Biết rằng cứ 3 thành phố bất kỳ trong 5 thành phố
đó thì chỉ có 2 thành phố có đường hàng không với nhau. Chứng minh rằng:
a) Mỗi thành phố được nối bằng đường hàng không với đúng hai thành phố
khác.
b) Từ mỗi thành phố bất kỳ có thể theo các đường hàng không đi qua các
thành phố còn lại đúng một lần và quay về thành phố ban đầu.
Giải.
Biểu thị 5 thành phố là 5 đỉnh A, B, C, D, E của đồ thị 5 đỉnh G. Giữa hai
thành phố nào đó có đường hàng không thì cạnh nối hai đỉnh tương ứng được
tô màu đỏ, còn nếu không có đường hàng không thì tô màu xanh.
Vậy G là đồ thị đầy đủ 5 đỉnh có cạnh tô bằng 2 màu: đỏ - xanh.
Lấy ba thành phố bất kỳ, chẳng hạn A, B, C. Vì có 2 thành phố nối với
nhau bằng đường hàng không nên có một cạnh tô màu đỏ, và tương tự có 2
cạnh tô màu xanh. Do đó G không có tam giác cùng màu.
Như vậy, trong 4 cạnh có đầu mút tại mỗi đỉnh đã cho phải có 2 và chỉ 2
80
cạnh màu đỏ (vì nếu tại đỉnh A có 3 cạnh AB, AC, AD cùng màu đỏ thì do
một trong 3 cạnh BC, CD, DB có màu đỏ nên sẽ có một tam giác có 3 cạnh
Hình 2.19
màu đỏ, trái giả thiết. Suy ra ý a) được chứng minh.
Để chứng minh ý b), ta chứng minh rằng trong đồ thị G có một chu trình
sơ cấp (với cạnh màu đỏ) qua tất cả các đỉnh A, B, C, D, E.
1. Giả sử tại A, có AB và AE được tô màu đỏ, còn AC và AD được tô màu
xanh. Khi đó (hình 2.20a) CD phải là màu đỏ (tam giác ACD) và BE phải là
Hình 2.20
màu xanh (tam giác ABE).
- Nếu cạnh ED được tô màu đỏ thì cạnh EC được tô màu xanh (tam giác
CDE), suy ra BC được tô màu đỏ (tam giác BEC) và ABCDEA là chu trình
cần tìm (hình 2.20b).
- Nếu cạnh EC được tô màu xanh thì cạnh CE được tô màu đỏ (tam giác
CDE) và BD đỏ (tam giác BDE) và ABDCEA là chu trình cần tìm (hình
2.20c)
2. Nếu tại A có hai cạnh AB và AD được tô màu đỏ còn cạnh AC và AE
81
được tô màu xanh thì cạnh CE phải là màu đỏ và BD màu xanh (hình 2.21a).
Khi đó, nếu cạnh ED màu đỏ thì cạnh CD màu xanh và BC đỏ, ta có chu
trình ABCEDA; còn nếu ED màu xanh thì CD màu đỏ, suy ra BE màu đỏ
Hình 2.21
và ta có chu trình ABECDA (hình 2.21b).
Như vậy, trong mọi trường hợp ta đều có chu trình có cạnh màu đỏ cần tìm.
Ý b) được chứng minh.
Từ bài toán trên ta có kết quả: Cho đồ thị G đầy đủ có 5 đỉnh và các cạnh
được tô một trong hai màu (xanh, đỏ). Nếu trong G không có tam giác nào có
3 cạnh cùng màu thì G có thể biểu diễn đồ thị dưới dạng ngũ giác lồi có các
cạnh cùng màu đỏ (hoặc xanh) và các đường chéo cùng màu xanh (hoặc đỏ).
Bài toán 2.5.7. Chứng tỏ rằng trong một nhóm 9 người mà tất cả bộ 3 người
bất kì trong nhóm quen nhau từng đôi thì có thể chọn ra 4 người quen nhau
từng đôi.
Giải.
Mỗi một người có thể đặt tương ứng với một đỉnh của đồ thị. Nối các đỉnh
của đồ thị này tạo nên đồ thị 9 đỉnh đầy đủ. Tô màu xanh cho cạnh mà hai
người tương ứng quen nhau, màu đỏ cho cạnh mà hai người tương ứng không
quen nhau. Theo điều kiện bài ra thì trong đồ thị đã tô màu các cạnh như vậy,
sẽ không có một tam giác mà các cạnh toàn màu đỏ.
Yêu cầu đề bài cần chứng minh tỏ rằng có một tứ giác mà các cạnh và
đường chéo được tô màu xanh.
Giả sử trong đồ thị có đỉnh A mà qua A có lớn hơn 3 cạnh màu đỏ. Chọn
82
trong đó 4 cạnh màu đỏ: AB, AC, AD, AE. Khi đó 2 trong 4 người tương ứng
B, C, D, E phải quen nhau từng đôi (vì nếu có 2 người, chẳng hạn B, C không
quen nhau thì tam giác ABC có các cạnh màu đỏ). Khi đó tứ giác BCDE có
các cạnh và đường chéo tô màu xanh. Trường hợp này được giải.
Vì không thể qua mỗi đỉnh của đồ thị này có đúng 3 cạnh màu đỏ (bởi vì
nếu có như vậy thì xét đồ thị 9 đỉnh này với các cạnh tô màu đỏ ta được đồ
thị 9 đỉnh mà bậc mỗi đỉnh bằng 3 (là lẻ) trái định lý 2.1.2).
Vậy trường hợp còn lại phải xét là: trong các đỉnh của đồ thị, có đỉnh có (cid:54)
2 cạnh đỏ đi qua. Giả sử đỉnh đó là A. Bỏ đi đỉnh A ở đồ thị và các đỉnh nối với A bằng cạnh màu đỏ, cũng như bỏ các cạnh qua đỉnh này ta có đồ thị (cid:62) 6
đỉnh. Theo định lý 2.5.4, tìm được một tam giác, giả sử là tam giác BCD có
các cạnh cùng màu. Màu này không thể là màu đỏ (theo giả thiết), vậy đó là
màu xanh. Vì AB, AC, AD là các cạnh màu xanh nên ABCD là tứ giác cần
tìm.
Vậy bài toán được giải.
Bài toán 2.5.8. Trong hội nghị chuyên đề về ngôn ngữ của quốc tế có n người
tham dự. Biết rằng trong 4 người bất kỳ luôn có một người mà anh ta có thể
nói chuyện trực tiếp với mỗi một trong 3 người kia bằng một thứ tiếng nào đó.
Chứng tỏ rằng trong hội nghị luôn có một người có thể nói chuyện trực tiếp
với mỗi người còn lại.
Giải.
Thiết lập đồ thị tương ứng là đồ thị n đỉnh, có các cạnh được tô bởi một
trong hai màu (màu xanh cho hai người tương ứng có thể nói chuyện với nhau
trực tiếp và màu đỏ trong trường hợp ngược lại). Theo đề bài thì trong 4 đỉnh
bất kỳ luôn có ít nhất một đỉnh nối với ba đỉnh còn lại bằng 3 cạnh màu xanh.
Ta sẽ chứng tỏ rằng trong đồ thị có đỉnh mà mọi cạnh qua nó màu xanh.
Trường hợp mà mọi cạnh đồ thị đều có màu xanh, bài toán là tầm thường,
đỉnh cần tìm là bất kỳ đỉnh nào cũng được.
Giả sử có cạnh AB màu đỏ. Xét thêm hai đỉnh C và D khác. Trong 4 đỉnh
83
có 3 cạnh màu xanh đi qua chỉ là C hoặc D, có thể giả sử đó là C. Ta chứng
tỏ rằng C là đỉnh cần tìm. Thật vậy, lấy E là đỉnh bất kỳ khác A, B, D. Trong
4 đỉnh A, B, C, E đỉnh có 3 cạnh xanh đi qua phải là C hoặc E, và vì vậy bao
giờ cạnh CE cũng màu xanh.
Bài toán được giải.
Bài toán 2.5.9. (xem [7]) Trong thành phố có n người. Hai người bất kỳ hoặc
là bạn thân của nhau, hoặc là hai người không ưa nhau. Hơn nữa, trong 3 người
bất kỳ thì hoặc 3 người thân nhau từng đôi một hoặc chỉ có hai người thân
nhau. Chứng tỏ rằng nếu không phải tất cả mọi người của thành phố này thân
nhau từng đôi một thì có thể tìm ra một người dân có số bạn thân không ít
hơn số người không ưa anh ta.
Giải.
Mỗi người dân thành phố đã cho đặt tương ứng với một đỉnh đồ thị. Giả
sử cạnh đồ thị màu xanh biểu thị hai người tương ứng quen nhau và màu đỏ
trong trường hợp ngược lại. Khi đó ta có đồ thị đầy đủ n đỉnh, các cạnh được
tô bằng một trong hai màu. Theo điều kiện bài ra, trong đồ thị này, một tam
giác bất kỳ phải có 3 cạnh xanh hoặc một cạnh xanh và hai cạnh đỏ. Ngoài ra
đồ thị phải có cạnh đỏ.
Xét cạnh đỏ AB. Giả sử số cạnh xanh đi qua A bằng k.
thì người dân cần tìm chính là A.
: Xét đỉnh C mà cạnh AB tô màu xanh. Có k đỉnh C n Nếu k < 2 Ngược lại nếu k (cid:62) n 2 như vậy. Với mỗi đỉnh C như vậy thì CB màu đỏ. Vậy qua B có (k + 1) cạnh
màu đỏ (vì BA là cạnh màu đỏ).
nên người cần tìm là B. Bài toán được giải. Do k + 1 > k (cid:62) n 2
2.6 Bài toán về cây
Ta xét các đồ thị dạng đặc biệt: Đồ thị vô hướng liên thông và không có
84
chu trình; đồ thị có hướng liên thông mạnh và không có vòng.
2.6.1 Định nghĩa
Một đồ thị vô hướng liên thông, không có chu trình và có ít nhất hai đỉnh
được gọi là một cây (hình 2.22a). Khái niệm quan trọng này là do Cayley đề
ra.
Đồ thị hữu hạn có hướng G = (X; U ) là một bụi gốc x1 ∈ X, nếu nó có ít
nhất hai đỉnh và thỏa mãn ba điều kiện sau:
1) Mỗi đỉnh khác x1 là điểm cuối của một cung duy nhất.
2) Đỉnh x1 không là điểm cuối của bất kỳ một cung nào.
Hình 2.22
3) Đồ thị G = (X; U ) không có vòng (hình 2.22b).
2.6.2 Đặc điểm của cây và bụi
Một số kết quả nhận được từ [5] như sau:
Định lý 2.6.1. Giả sử H là một đồ thị vô hướng với n đỉnh (n > 1). Để đặc
trưng cho một cây thì sáu tính chất sau đây là tương đương:
(1) H liên thông và không có chu trình.
(2) H không có chu trình và có n − 1 cạnh.
(3) H liên thông và có n − 1 cạnh.
(4) H không có chu trình và nếu thêm một cạnh nối giữa hai đỉnh bất kì không kề nhau thì đồ thị nhận được H (cid:48) có một chu trình (và chỉ một mà thôi).
(5) H liên thông và khi bớt một cạnh bất kì thì đồ thị mất tính liên thông.
(6) Mọi cặp đỉnh của H đều được nói với nhau bằng một xích và chỉ một
85
mà thôi.
Chứng minh.
Định lý được chứng minh theo phương pháp vòng tròn.
Ký hiệu số cạnh của đồ thị H bằng m, số thành phần liên thông bằng p.
(1) ⇒ (2): Theo tính chất (1): p = 1, v(H) = m − n + 1, nên m = n − 1.
(1) ⇒ (3): Theo tính chất (2): m = n − 1, v(H) = 0 nên
v(H) = m − n + p = n − 1 + p = 0 ⇒ p = 1.
Bởi vậy H liên thông và có n − 1 cạnh.
(3) ⇒ (4): Theo tính chất (3): p = 1, m = n − 1 nên
v(H) = m − n + p = n − 1 − n + 1 = 0
tức là H không có chu trình; ngoài ra, nếu thêm vào một cạnh nối giữa hai đỉnh không kề nhau, thì đồ thị H (cid:48) nhận được sẽ có chu số:
v(H (cid:48)) = m + 1 − n + 1 = n − 1 + 1 − n + 1 = 1.
Nên đồ thị H (cid:48) có chu trình và chỉ một mà thôi.
(4) ⇒ (5): Lấy hai đỉnh bất kỳ x, y của đồ thị H. Theo tính chất (4): nếu thêm vào cạnh (x, y) thì đồ thị mới nhận được H (cid:48) có chu trình, điều đó chứng
tỏ giữa x, y đã có xích nối với nhau, tức H đã liên thông.
Giả sử bớt đi một cạnh nào đó, chẳng hạn (u, v) mà đồ thị nhận được vẫn
liên thông. Điều này chứng tỏ trong đồ thị H giữa các đỉnh u, v ngoài cạnh
(u, v) còn một xích nữa nối giữa chúng, tức là trong H có ít nhất một chu trình
đi qua u, v. Ta đi tới mẫu thuẫn với tính chất (4): đồ thị H không có chu trình.
Bởi vậy, nếu bớt đi một cạnh tùy ý thì đồ thị nhận được từ H sẽ không liên
thông.
(5) ⇒ (6): Giả sử trong H tồn tại cặp đỉnh nào đó, chẳng hạn x, y được nối
với nhau bằng từ hai xích trở lên. Khi đó, nếu ta bỏ đi một cạnh nào đó thuộc
một trong hai xích này, thì xích còn lại vẫn bảo đảm cho x, y liên thông. Như
vậy ta đã đi tới mâu thuẫn với tính chất (5). Do đó, mọi cặp đỉnh của H đều
86
được nối với nhau bằng một xích và chỉ một mà thôi.
(6) ⇒ (1): Giả sử H không liên thông. Khi đó có ít nhất một cặp đỉnh không
có xích nối với nhau, nên mâu thuẫn với tính chất (6).
Giả sử H có chu trình. Khi đó có ít nhất một cặp đỉnh nằm trên chu trình
này được nối với nhau bằng ít nhất hai xích. Như vậy ta cũng đi đến mâu
thuẫn với tính chất (6). Bởi vật đồ thị H có tính chất (1).
Định lý đã được chứng minh
(cid:3)
Định lý 2.6.2. Một cây có ít nhất hai đỉnh treo.
Chứng minh.
Giả sử cây H chỉ có không quá một đỉnh treo. Ta tưởng tượng có một khách
bộ hành đi theo đồ thị đó, xuất phát từ một đỉnh tùy ý (trong trường hợp đồ
thị không có đỉnh treo) hay từ đỉnh treo (trong trường hợp đồ thị có 1 đỉnh
treo): Nếu hành khách tự cấm mình không đi qua một cạnh hai lần, khi đó
không thể gặp một đỉnh hai lần (do đồ thị H không có chu trình). Mặt khác,
khi tới một đỉnh người đó luôn luôn có thể đi ra bằng một cạnh mới (vì mỗi
đỉnh khác đỉnh xuất phát đều có ít nhất hai cạnh). Như vậy khách bộ hành
sẽ đi mãi không bao giờ dừng lại. Đó là điều không thể xảy ra, vì đồ thị H có
hữu hạn đỉnh. Vậy đồ thị H không thể có ít hơn hai đỉnh treo. Định lý được
chứng minh.
(cid:3)
Định lý 2.6.3. Mọi bụi khi bỏ định hướng các cạnh đều trở thành cây
Chứng minh.
Giả sử bụi H = (X, U ) có gốc là x1 và đồ thị vô hướng G = (X, E) nhận
được từ bụi H sau khi bỏ định hướng các cung.
1) Đồ thị G liên thông: Do điều kiện 1) mỗi đỉnh x (cid:54)= x1 đều có đường từ
x1 đi tới. Thật vậy, giả sử x (cid:54)= x1 và từ x1 không có đường đi tới x.
Nếu x là đỉnh biệt lập, thì nó không thể là đỉnh cuối của một cung nào đó,
còn nếu x không phải đỉnh biệt lập, thì phải có đỉnh y là điểm xuất phát của
87
một đường đi tới x. Nhưng do từ x1 không có đường đi tới x nên y (cid:54)= x1; mà
nó cũng không là điểm cuối của bất kỳ cung nào. Như vậy, ta đã đi tới mẫu
thuẫn với điều kiện 1). Do đó mọi đỉnh x (cid:54)= x1, từ x1 đều có đường đi tới nó,
nên trong G mọi đỉnh x đều có xích nối với hai đỉnh x1. Bởi vậy G liên thông.
2) Đồ thị G không có chu trình. Thật vậy, giả sử G có chu trình, thì trong
H dãy cung tương ứng với các cạnh thuộc chu trình này sẽ hoặc lập thành một
vòng hoặc có ít nhất hai cung có chung điểm cuối. Như vậy ta đã đi tới mẫu
thuẫn với điều kiện 1) hoặc điều kiện 3). Nên đồ thị G không có chu trình và
liên thông. Do đó G là 1 cây. Định lý được chứng minh.
(cid:3)
2.6.3 Ứng dụng
Bài toán 2.6.1. (xem [5]) Trong một cuộc thi đấu bóng bàn, An và Bình quy
ước với nhau: người thắng cuộc là người đầu tiên thắng 3 ván hoặc thắng 2
ván liên tiếp. Hãy xác định số khả năng có thể xảy ra.
Giải.
Dùng A để ký hiệu An thắng, dùng B để ký hiệu Bình thắng.
Dùng cây để mô tả toàn bộ hiện trạng có khả năng xảy ra.
Xây dựng cây: Xuất phát từ điểm S.
Ván đầu tiên có hai khả năng: An thắng hoặc Bình thắng. Lấy hai điểm sao
cho hai điểm này với điểm S không thẳng hàng; một trong hai điểm này ghi A,
điểm kia ghi B. Nối S với A bằng một đoạn thẳng hoặc một đoạn cong để biểu
thị “A thắng”. Tương tự, để biểu thị “B thắng” ta nối S với Bbằng một đoạn
thẳng hoặc một đoạn cong.
Ván thứ hai lại có 2 khả năng: An thắng hoặc Bình thắng, nên xuất phát
từ A cũng lấy hai điểm mới và ghi các ký hiệu tương ứng A, B và từ A kẻ hai
đoạn thẳng hoặc hai đoạn cong tới hai điểm mới thêm. Đối với điểm B cũng
chọn thêm hai đỉnh mới ghi A và B, rồi từ B kẻ hai đoạn thẳng hay hai đoạn
cong đi tới hai điểm mới thêm.
Tiếp theo thực hiện kéo dài các đương một cách tương tự, nhưng do quy
88
ước của An và Bình, những đường mà trên đó xuất hiện hoặc 2 đỉnh liên tiếp
ghi cùng bằng một ký hiệu hoặc 3 đỉnh được ghi bằng cùng một ký hiệu đều
Hình 2.23
không được kéo dài.
Vì An và Bình đấu với nhau 5 ván, thì hoặc có người thắng 2 ván liên tiếp
hoặc có người thắng 3 ván. Do đó, những đường xuất phát từ S đều không có
quá 5 cạnh.
Vậy cây có 10 đỉnh ngọn, nên có 10 khả năng xảy ra.
Bài toán 2.6.2. (xem [5]) Có bốn đội bóng đá A, B, C, D lọt vào vòng bán
kết trong giải các đội mạnh khu vực. Có mấy dự đoán xếp hạng như sau:
a. Đội B vô địch, đội D nhì.
b. Đội B nhì, đội C ba.
c. Đội A nhì, đội C tư.
Biết rằng mỗi dự đoán trên đúng về một đội. Hãy cho biết kết quả xếp hạng
của các đội.
Giải.
Ta ký hiệu:
B1: Đội B nhất
B2: Đội B nhì
D2: Đội D nhì
A2: Đội A nhì
89
C3: Đội C ba
C4: Đội C bốn
Để biết kết quả xếp hạng của các đội ra vẽ cây như sau:
- Hai “nhánh” đầu tiên ứng với dự đoán thứ nhất.
- Từ mỗi nhánh trên lại rẽ thành hai nhánh ứng với dự đoán thứ hai.
Hình 2.24
- Tiếp tục rẽ nhánh đối với dự đoán thứ 3 theo cách trên ta có 1 cây:
Ta chọn một đường đi từ “gốc” O đến “ngọn” trên đó các cạnh không mang
chữ trùng nhau. Vì một đội không thể xếp hai hạng khác nhau và không có
chỉ số trùng nhau. (Vì hai đội không thể được xếp hàng cùng một hạng), đồng
thời thứ tự xếp hạng của các đội thỏa mãn điều kiện đầu bài. Đường tô đậm
nét với dãy ký hiệu B1, C3, A2, D4 cho ta xếp hạng cần tìm.
Bài toán 2.6.3. Cho n điểm trên mặt phẳng có khoảng cách giữa các điểm
đôi một khác nhau. Nối mỗi điểm với điểm gần nó nhất. Bằng cách đó chúng
ta thu được một đồ thị G. Chứng minh rằng G là một bụi mà bậc của mỗi
đỉnh không lớn hơn 5.
Giải.
Trước tiên, ta chứng tỏ rằng G không có chu trình.
Giả sử ngược lại, G có một chu trình K nào đó. Không mất tính tổng quát,
giả sử AB là cạnh có độ dài lớn nhất trong tất cả các cạnh của K. Gọi C và
90
D lần lượt là hai đỉnh kề với A và B trong số các đỉnh thuộc K.
Hình 2.25
Ta có AB > AC và AB > BD. Theo cách nối các đỉnh của yêu cầu bài
toán: mỗi đỉnh chỉ nối với đỉnh gần nó nhất thì cạnh AB không thể được nối.
Hình 2.26
Vậy, điều giả sử là sai. Nghĩa là trong G không có chu trình.
Bây giờ ta chứng minh rằng các đỉnh của đồ thị đều có bậc nhỏ hơn 6. Giả sử đỉnh P có bậc m(p) (cid:62) 6, và 6 đỉnh kề với P là A1, A2, A3, A4, A5, A6 được bố trí trên mặt phẳng theo chiều kim đồng hồ (hình 2.26), không mất tính tổng
quát, ta có thể giả sử A1 là điểm gần P nhất.
Như vậy, trong các tam giác AiP Ai+1 (i = 2, 3, 4, 5) ta có cạnh AiAi+1 là
cạnh lớn nhất, do P là điểm gần với Ai nhất. Trong tam giác A6P A1 và A1P A2
cạnh A6A1 và A1A2 cũng là cạnh dài nhất, do A6P < A6A1 và A1P < A6P
91
(A1 gần P nhất), và cũng tương tự như vậy là A2P < A2A1 và A1P < A2P . Do đó, ∠AiP Ai+1 > 600. Ta cũng có tổng các góc quanh P lớn hơn 3600, điều này không thể xảy ra. Bài toán được chứng minh.
Lời kết
Dưới sự hướng dẫn khoa học của NGND.GS.TS Đặng Huy Ruận cùng với
sự nỗ lực học tập và nghiêm túc nghiên cứu của bản thân, các kết quả chính
của luận văn “Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp” đã được trình
bày theo hệ thống sau đây:
1. Trình bày các lý thuyết cơ bản của Lý thuyết đồ thị ứng dụng để giải
toán sơ cấp.
2. Sưu tầm và hệ thống các bài toán nhằm khắc sâu kiến thức lý thuyết.
Mặc dù tác giả đã hết sức cố gắng nhưng do thời gian và khả năng có hạn
chắc chắn luận văn này còn nhiều thiếu sót. Tác giả rất mong nhận được ý
kiến đóng góp của quý thầy cô giáo và các bạn đồng nghiệp để luận văn được
hoàn thiện hơn.
92
Xin trân trọng cảm ơn!
Tài liệu tham khảo
[1] Hoàng Chúng: Graph và giải toán phổ thông. NXBGD 1992.
[2] Đỗ Đức Giáo: Hướng dẫn giải bài tập toán rời rạc. NXBGD 2009.
[3] Vũ Đình Hòa: Định lý và vấn đề về Đồ thị hữu hạn. NXBGD 2003.
[4] Vũ Đình Hòa: Một số kiến thức cơ sở về graph hữu hạn. NXBGD 2006.
[5] Đặng Huy Ruận: Lý thuyết đồ thị và ứng dụng. NXB Khoa học và kỹ
thuật 2004.
[6] Đặng Huy Ruận: Bảy phương pháp giải các bài toán logic. NXB Khoa
học và kỹ thuật 2002.
[7] Hoàng Chí Thành: Đồ thị và các thuật toán. NXBGD 2007.
[8] Nguyễn Văn Thông: Bồi dưỡng học sinh giỏi Toán Tổ hợp - rời rạc.
NXB ĐHQGHN 2012.
[9] Nguyễn Gia Định: Giáo trình Toán rời rạc. NXB Đại học Huế 2003.
93
[10] Diendantoanhoc.vn