Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp

ĐẠ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

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

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ị.

- 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

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

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é.

• 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

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

?”.

Đế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

đỉ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

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 đồ

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

• Đỉ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à

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

á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

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.

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.

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

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

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.

Đư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

đỉ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

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

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

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.

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.

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].

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

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.

(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.

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.

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

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

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ó

độ 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

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.

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

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.

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

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

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.

(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.

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ó

đị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.

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

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

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ả

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

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 .

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

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

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ử

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.

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

Chứng minh.

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

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

Đồ 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

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,

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.

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

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 đó

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.

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]).

- Đồ 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

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.

(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

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ư

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,

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.

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

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.

Có = 5 cách sắp xếp chỗ ngồi phân biệt như sau: 11 − 1 2

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.

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

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 đồ

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 α

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ô

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.

(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ì

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.

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

đã 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?

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.

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),

(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

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

đượ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

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

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ó

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

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

đượ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

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

ướ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ì

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à

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

(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.

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.

[10] Diendantoanhoc.vn

Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp

Chủ đề:

Luận văn cao học

Luận văn thạc sĩ mỹ thuật ứng dụng

LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP

LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP

Mục lục

Mở đầu

Chương 1

Các khái niệm và định lý cơ bản

1.1 Các ví dụ về đồ thị

1.2 Định nghĩa đồ thị

1.3 Biểu diễn đồ thị bằng hình học

1.4 Một số dạng đồ thị đặc biệt

1.5 Phương pháp đồ thị

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.2 Bài toán liên quan đến chu trình

2.3 Bài toán liên quan đến tính liên thông

2.4 Đồ thị Euler - Đồ thị Hamilton

2.5 Bài toán liên quan đến đồ thị tô màu

2.6 Bài toán về cây

Lời kết

Tài liệu tham khảo

Tài liệu liên quan

Tóm tắt Luận án Tiến sĩ: Nghiên cứu mô phỏng và dự đoán chuyển động của vệt dầu loang tại vùng biển Việt Nam dựa trên phương pháp mô phỏng 3D

Báo cáo thực tập: Nghiên cứu bài toán geocoding và phát triển ứng dụng minh họa

Luận văn Thạc sĩ Mỹ thuật: Tạo hình bàn tay trong một số tác phẩm của Michelangelo, Leonardo Da Vinci, Albrecht Durer

Luận văn Thạc sĩ Khoa học vật chất: Nghiên cứu chế tạo vật liệu compozit từ polylactic, dầu hạt đen và sợi gai xanh AP1

Luận án Tiến sĩ Kỹ thuật trắc địa - bản đồ: Nghiên cứu phương pháp xác định dòng chảy bề mặt trên vùng biển Việt Nam từ số liệu đo cao vệ tinh phục vụ cho một số hoạt động của Hải quân Việt Nam

Luận án Tiến sĩ Nghệ thuật: Nghệ thuật trang trí nội thất một số khách sạn tiêu biểu tại thành phố Hồ Chí Minh

Luận án Tiến sĩ Nghệ thuật: Nghệ thuật tạo hình đồ trang sức Champa

Luận án Tiến sĩ Nghệ thuật: Hội họa sơn mài tại Thành phố Hồ Chí Minh giai đoạn từ năm 1986 đến năm 2020

Luận văn Thạc sĩ Kiến trúc: Chất hài trong kiến trúc của Renzo Piano

Luận văn Thạc sĩ Mỹ thuật: Sự chuyển biến về tạo hình trong minh họa tranh truyện thiếu nhi ở Việt Nam từ 1995 đến 2015

Tài liêu mới

Luận án Tiến sĩ: Trích xuất mạch vành và phát hiện bất thường trên mạch vành hỗ trợ trong chẩn đoán

Tóm tắt Luận án Tiến sĩ: Trích xuất mạch vành và phát hiện bất thường trên mạch vành hỗ trợ trong chẩn đoán

Luận án Tiến sĩ: Tổng hợp, đặc trưng và ứng dụng của vật liệu khung cơ kim loại trên cơ sở Bismuth

Tóm tắt Luận án Tiến sĩ: Tổng hợp, đặc trưng và ứng dụng của vật liệu khung cơ kim loại trên cơ sở Bismuth

Luận án Tiến sĩ: Tác động của trách nhiệm xã hội đến tài sản thương hiệu, sự hài lòng và ý định quay lại của du khách - Trường hợp các điểm đến ở khu vực Đông Nam Bộ, Việt Nam

Tóm tắt Luận án Tiến sĩ: Tác động của trách nhiệm xã hội đến tài sản thương hiệu, sự hài lòng và ý định quay lại của du khách - Trường hợp các điểm đến ở khu vực Đông Nam Bộ, Việt Nam

Luận án Tiến sĩ: Nghiên cứu chế tạo vật liệu xúc tác quang trên nền TiO₂, ZnO biến tính bởi chấm lượng tử Graphene pha tạp nitơ và nano bạc

Tóm tắt Luận án Tiến sĩ: Nghiên cứu chế tạo vật liệu xúc tác quang trên nền TiO₂, ZnO biến tính bởi chấm lượng tử Graphene pha tạp nitơ và nano bạc

Luận án Tiến sĩ: Nghiên cứu phát triển các mô hình sinh kế bền vững dựa vào canh tác nông nghiệp của người dân ở vùng đệm Vườn quốc gia Tà Đùng

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phát triển các mô hình sinh kế bền vững dựa vào canh tác nông nghiệp của người dân ở vùng đệm Vườn quốc gia Tà Đùng

Luận án Tiến sĩ: Nghiên cứu tổng hợp dung dịch Ferrate (FeO₄²⁻) bằng phương pháp điện hoá và ứng dụng trong xử lý nước thải

Tóm tắt Luận án Tiến sĩ: Nghiên cứu tổng hợp dung dịch Ferrate (FeO₄²⁻) bằng phương pháp điện hoá và ứng dụng trong xử lý nước thải

Tóm tắt Đề án Thạc sĩ: Đào tạo nguồn nhân lực trong bối cảnh chuyển đổi số tại Học viện Công nghệ Bưu chính Viễn thông

Đề án Thạc sĩ: Đào tạo nguồn nhân lực trong bối cảnh chuyển đổi số tại Học viện Công nghệ Bưu chính Viễn thông

Luận án Tiến sĩ: Tác động của văn hoá doanh nghiệp đến năng lực sáng tạo của nhân viên các doanh nghiệp ICT Việt Nam - Nghiên cứu trường hợp Tập đoàn FPT

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok