LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
MỤC LỤC

Trang
MỤC LỤC 01
LỜI NÓI ĐẦU 02
BẢNG PHÂN CÔNG NGHIÊN CỨU
CHƯƠNG I : ĐẠI CƯƠNG VỀ ĐỒ THỊ 03
CHƯƠNG II : ĐỒ THỊ PHẲNG 11
CHƯƠNG III : ỨNG DỤNG 19
KẾT LUẬN 29
TÀI LIỆU THAM KHẢO 30
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 1
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
LỜI NÓI ĐẦU
Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu nhưng lại có
nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18
bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải
quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng.
Đồ thị cũng được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau.
Ví dụ, dùng đồ thị để xác định xem có thực hiện một mạch điện trên một bản
điện phẳng được không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có
cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta cũng
có thể xác định xem hai máy tính có được nối với nhau bằng một đường truyền
thông hay không nếu dùng mô hình đồ thị mạng máy tính. Đồ thị với các trọng
số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán
tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông. Chúng ta
cũng có thể dùng đồ thị để lập lịch thi và phân chia kênh cho các đài truyền
hình…
Như vậy đồ thị nói chung, đồ thị phẳng nói riêng có nhiều ứng dụng trong
nhiều lĩnh vực khác nhau. Qua quá trình học tập và nghiên cứu chuyên đề “Lý

Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải được bài toán đố hóc
búa nổi tiếng thời đó về những cái cầu ở Konigsberg. Bài toán như sau: Trong
thành phố Konigsberg có hai hòn đảo được nối với nhau và hai bờ sông bằng bảy
chiếc cầu. Bài toán đặt ra là tìm đường đi qua tất cả bảy cái cầu, mỗi cầu chỉ
được qua một lần, sau đó quay về nơi xuất phát. Euler đã chứng minh được rằng
bài toán không có lời giải bằng ngôn ngữ đồ thị.
1.2.2. Bài toán mạng điện
Năm 1847 Kirchoff xây dựng lý thuyết các vòng để giải các hệ phương trình
tuyến tính tương thích cho phép tìm giá trị cường độ dòng điện trên mỗi dây dẫn
và trong mỗi mạch vòng của mạch điện. Biểu diễn mạng điện bằng đồ thị ông đã
chỉ ra rằng để giải hệ phương trình không nhất thiết phải xét riêng rẽ từng vòng
của đồ thị mạng điện. Thay vào đó ông đề xuất thuật toán hữu hiệu (sau này trở
thành thuật toán chuẩn), mà theo đó chỉ cần giới hạn trong việc xét các vòng đơn
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 3
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
độc lập của đồ thị xác định bởi một trong số các cây khung của đồ thị.
1.2.3. Bài toán các đồng đẳng hóa học
Khi nghiên cứu những bài toán hóa hữu cơ năm 1857 Kelly đã phát minh
một lớp đồ thị quan trọng gọi là cây. Ông cố gắng tính số đồng đẳng no của
Hydro cacbon C
n
H
2n+2
với số nguyên tử cacbon cho trước là n. Viêc nghiên cứu
trên đã dẫn đến bài toán về cây: tìm số tất cả các cây với p đỉnh có các đỉnh là
bậc 1 và 4. Muộn hơn, vào năm 1869 Jordan độc lập với Kelly cũng đã nghiên
cứu các cây như là đối tượng toán học.
1.2.4. Bài toán người du lịch
Một người du lịch muốn tham quan n thành phố 1, 2,…, n. Xuất phát từ
thành phố nào đó người du lịch đi qua tất cả các thành phố, mỗi thành phố chỉ

n = 35.
Năm 1968 Ore và Stemple chứng minh giả thiết 4 màu với bản đồ có số
nước n = 39.
Năm 1977 Appel K. và W. Haken cùng J.Koch chứng minh giả thiết 4 màu
với sự trợ giúp của máy tính.
Gần đây, năm 1987 Roberston, Sanders, Seymour và Thomas đã đưa ra
chứng minh khác ngắn gọn hơn.
Các chứng minh trên đều sử dụng máy tính và đến nay vẫn chưa có chứng
minh bằng suy luận toán học thuần túy.
1.3. CÁC KHÁI NIỆM CƠ BẢN
1.3.1. Đồ thị vô hướng và đồ thị có hướng
• Đồ thị vô hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh.
Mỗi cạnh e∈E được liên kết với một cặp đỉnh v, w (không kể thứ tự) như hình
sau:
• Đồ thị có hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh có hướng
gọi là cung.
Mỗi cạnh e∈E được liên kết với một cặp đỉnh (v, w) có thứ tự như hình sau:
Cho đồ thị có hướng G = (V, E). Nếu ta thay mỗi cung của đồ thị G bằng một
cạnh, thì đồ thị vô hướng nhận được gọi là đồ thị lót của đồ thị có hướng G.
• Cho đồ thị (có hướng hoặc vô hướng) G = (V, E).
Nếu cạnh e ∈ E liên kết đỉnh v và w, ta nói e liên thuộc đỉnh v, w; đỉnh v và
w liên thuộc cạnh e, các đỉnh v, w là các đỉnh biên của cạnh e và đỉnh v gọi là kề
đỉnh w.
Nếu e là cung thì v gọi là đỉnh đầu, w gọi là đỉnh cuối của cung e.
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 5
v
e
w
v
e

(i) Tổng bậc các đỉnh của đồ thị là số chẵn và
∑
∈
=
Vv
Ecardv )(.2)deg(
(ii) Nếu G là đồ thị có hướng thì

)()(deg)(deg Ecardvv
Vv
I
Vv
o
==
∑∑
∈∈
trong đó card(E) ký hiệu số phần tử của tập E.
Hệ quả: Số đỉnh bậc lẻ của đồ thị vô hướng là số chẵn.
• Đồ thị K
n
là đồ thị đơn, đủ n đỉnh (mỗi cặp đỉnh đều có duy nhất một cạnh liên
kết).
Mọi đỉnh của đồ thị K
n
có bậc là n-1 và K
n
có n(n-1)/2 cạnh.
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 6
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
• Đồ thị lưỡng phân G = (V, E) là đồ thị mà tập các đỉnh được phân làm 2 tập

nhất.
1.4. BIỂU DIỄN ĐỒ THỊ
1.4.1. Ma trận kề
a. Đồ thị vô hướng
• Cho đồ thị vô hướng G = (V,E) có n đỉnh theo thứ tự v
1
,v
2
,…,v
n
. Ma trận kề
của đồ thị G là ma trận vuông A = (a
ij
)
n×n
, trong đó a
ij
là số cạnh (khuyên) nối v
i

với v
j
. Lưu ý rằng khi tính bậc của đỉnh mỗi khuyên được tính hai bậc. Từ định
nghĩa suy ra rằng ma trận kề của đồ thị vô hướng luôn đối xứng qua đường chéo
chính.
Mệnh đề. Cho đồ thị G = (V,E) với ma trận kề (a
ij
). Khi đó
Deg(v
i

là bậc của đỉnh v
i
.
Hệ quả. Cho đồ thị đơn G = (V,E) có n đỉnh, V = { v
1
,v
2
,…,v
n
} và ma trận kề
của đồ thị G là ma trận A = (a
ij
)
n×n
. Ký hiệu T = A + A
2
+…+A
n-1
. Khi đó đồ thị
G liên thông khi và chỉ khi các phần tử ngoài đường chéo chính của ma trận T
đều lớn hơn 0.
b. Đồ thị có hướng.
• Cho đồ thị có hướng G = (V,E) có n đỉnh theo thứ tự v
1
,v
2
,…,v
n
. Ma trận kề
của đồ thị G là ma trận vuông A = (a

,…,v
n
} và ma trận
kề của đồ thị G là ma trận A = (a
ij
)
n×n
. Giả sử A
k
= (c
ij
)
n×n
, k ≥ 1.Khi đó c
ij
, i ≠j, là
số dây có hướng chiều dài k từ đỉnh v
i
đến đỉnh v
j
.
Hệ quả. Cho đồ thị có hướng G = (V,E) có n đỉnh, V = {v
1
,v
2
,…,v
n
} và ma trận
kề của đồ thị G là ma trận A = (a
ij

ij
=1, nếu đỉnh v
i
liên thuộc cạnh e
j
.
a
ij
=0, nếu đỉnh v
i
không liên thuộc cạnh e
j
.
Mệnh đề. Cho đồ thị đơn G = (V,E) với ma trận liên thuộc (a
ij
). Khi đó
Deg(v
i
) = ,∀v
i
∈V
b. Đồ thị có hướng
• Cho đồ thị có hướng không khuyên G = (V,E) có n đỉnh, V = { v
1
,v
2
,…,v
n
} và
m cung E = {e

j
.
Mệnh đề. Cho đồ thị có hướng không khuyên G = (V,E) với ma trận liên thuộc
(a
ij
). Khi đó: Deg
o
(v
i
) = ,∀v
i
∈V
Deg
I
(v
i
) = ,∀v
i
∈V
1.4.3. Danh sách cạnh (cung)
Trong trường hợp đồ thị thưa (đồ thị có n đỉnh và m cạnh hoặc cung thỏa
mãn m < 6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách
cạnh (cung).
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 8
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng ta sẽ lưu trữ tất
cả danh sách các cạnh (cung) của đồ thị vô hướng (có hướng). Một cạnh (cung)
e=(x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. Như vậy để lưu trữ
đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này là
để xác định những đỉnh nào của đồ thị kề với một đỉnh cho trước chúng ta phải

và g : E
1
→ E
2
thỏa mãn:
∀e ∈ E
1
: e = (v,w) ⇔ g(e) = (f(v),f(w)).
Cặp ánh xạ (f,g) gọi là một đẳng cấu từ G
1
đến G
2
.
Mệnh đề. Hai đơn đồ thị G
1
= (V
1
,E
1
) và G
2
= (V
2
,E
2
) gọi là đẳng cấu với nhau
nếu tồn tại song ánh f : V
1
→ V
2

thỏa mãn G
1
có tính chất P khi và chỉ khi G
2
có tính chất P.
Do đó để chứng minh hai đồ thị không đẳng cấu ta phải tìm ra tính chất bất
biến nào đó mà một đồ thị có, còn đồ thị kia không có.
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 9
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
Định lý. Cho G
1
= (V
1
,E
1
) và G
2
= (V
2
,E
2
) là hai đồ thị đẳng cấu. Khi đó:
(i) G
1
và G
2
có số cạnh và số đỉnh bằng nhau.
(ii) Với mọi số k tự nhiên, số đỉnh bậc k của G
1
và G

NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 10
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
CHƯƠNG II
ĐỒ THỊ PHẲNG
2.1. ĐỒ THỊ PHẲNG
• Đồ thị hình học phẳng. Một đồ thị gọi là đồ thị hình học phẳng nếu nó được
biểu diễn trên mặt phẳng sao cho các cạnh không cắt nhau.
• Đồ thị phẳng. Một đồ thị gọi là phẳng nếu nó đẳng cấu với đồ thị hình học
phẳng.
Với một đồ thị hình học phẳng liên thông, mặt phẳng được chia làm các
miền con gọi là mặt. Mỗi mặt được giới hạn bởi chu trình gọi là biên của mặt. Số
cạnh trên biên của mặt f được gọi là bậc của mặt, ký hiệu deg(f). Bậc nhỏ nhất
gọi là đai của đồ thị.
• Mệnh đề. Mọi chu trình của đồ thị phẳng có độ dài chẵn khi và chỉ khi mọi
mặt của đồ thị đều có bậc chẵn.
• Đồ thị tuyến tính phẳng. Đồ thị G gọi là đồ thị tuyến tính phẳng nếu G là đồ
thị hình học phẳng có tất cả các cạnh là đoạn thẳng.
• Định lý. Mỗi đơn đồ thị phẳng đẳng cấu với đồ thị tuyến tính phẳng.
2.2. CÔNG THỨC EULER.
• Định lý 2.2.1 (công thức Euler). Cho G là đồ thị liên thông phẳng có e cạnh, v
đỉnh và f mặt. Khi đó ta có công thức Euler:
f = e – v + 2
• Định lý 2.2.2 (Bất đẳng thức cạnh-đỉnh). Cho G là đơn đồ thị phẳng liên thông
với e cạnh, v đỉnh và đai g (g≥3), không có đỉnh treo. Khi đó ta có:
)2v(
2g
g
e −
−
≤

gọn từ G.
• Đồ thị đồng phôi. Hai đồ thị G
1
và G
2-
gọi là đồng phôi nếu G
1
và G
2
có thể
rút gọn thành những đồ thị đẳng cấu qua một số phép rút gọn nối tiếp.
• Định lý (Kuratowski). Đồ thị G là đồ thị phẳng khi và chỉ khi G không chứa
đồ thị con đồng phôi với đồ thị K
5
hoặc K
3,3
.
2.4. NHÚNG ĐỒ THỊ
Trong nhiều trường hợp chúng ta muốn biểu diễn đồ thị trong không gian
nào đó, chẳng hạn như mặt phẳng, mặt cầu, không gian Euclide ba chiều,…,
trong đó các điểm của không gian biểu diễn đỉnh đồ thị và các đường cong không
cắt nhau (trừ các đỉnh đồ thị) biểu diễn các cạnh đồ thị.
• Đường cong Jordan. Một đường cong Jordan trong mặt phẳng là đường cong
liên tục không tự cắt. Đường cong Jordan với điểm đầu và cuối trùng nhau gọi là
đường cong Jordan khép kín.Tương tự định nghĩa đường cong Jordan trong các
mặt khác (mặt cầu, mặt xuyến, không gian Euclide ba chiều…).
• Định lý 2.4.1. Giả sử C là đường cong Jordan khép kín trong mặt phẳng và x
và y là 2 điểm khác nhau của C. Khi đó mọi đường cong Jordan nối x và y hoặc
nằm hoàn toàn bên trong C (trừ x và y), hoặc nằm hoàn toàn bên ngoài C (trừ x
và y), hoặc cắt C ở điểm khác x và y.

Ví dụ 2: Bản đồ trong hình bên có 8 miền, A B C
chỉ cần ít nhất 4 màu thì tô được.
D E F G

H

• Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng một đồ thị, trong đó mỗi
miền của bản đồ được biểu diễn bằng một đỉnh; có cạnh nối hai đỉnh, nếu các
miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách
này gọi là đồ thị đối ngẫu của bản đồ đang xét.
Chẳng hạn đồ thị đối ngẫu của các bản đồ ở trên lần lượt là:

Rõ ràng mọi bản đồ trên mặt phẳng đều có đồ thị đối ngẫu phẳng.
• Tô màu đỉnh một đơn đồ thị là sự gán màu cho các đỉnh của nó sao cho không
có hai đỉnh liền kề gán cùng một màu.
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 13
f
a
b
c
d
e
A
B
C
D
E

đường này có độ dài lẻ thì tô màu 1 cho v. Nếu có hai đường đi mang tính chẵn
lẻ khác nhau cùng nối u với v thì dễ thấy rằng G phải chứa ít nhất một chu trình
độ dài lẻ. Điều mâu thuẫn này cho biết hai màu 0 và 1 tô đúng đồ thị G.
Định lý 2.5.3. χ(G) ≤ ∆(G) + 1 với mọi đồ thị G, trong đó ∆(G) là bậc đỉnh lớn
nhất của G ( đẳng thức xảy ra khi G = K
n
hoặc G là chu trình độ dài lẻ).
Định lý 2.5.4 (Brooks). Cho G là đơn đồ thị n đỉnh liên thông khác K
n
và không
phải chu trình độ dài lẻ. Khi đó χ(G) ≤ ∆(G) .
2.5.2. Thuật toán tuần tự ưu tiên đỉnh bậc lớn nhất
Cho đồ thị G = (V,E). Thuật toán sau sẽ tô màu các đỉnh đồ thị với số màu k
gần với sắc số χ(G).
(i) Lập danh sách các đỉnh đồ thị E’ := [v
1
,v
2
, ,v
n
] theo thứ tự bậc giảm dần
deg(v
1
) ≥ deg(v
2
) ≥ ≥ deg(v
n
).
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 14
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG

2.5.4. Bài toán tô màu cạnh
• Tô màu cạnh một đơn đồ thị là sự gán màu cho các cạnh của nó sao cho không
có hai cạnh kề được gán cùng một màu.
Sắc số cạnh của đồ thị G , ký hiệu là χ’(G), là số màu tối thiểu cần thiết để tô
màu cạnh đồ thị.
Hiển nhiên với mọi đồ thị G ta có χ’(G) ≥ ∆(G).
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 15
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
Giả sử ta tô màu các cạnh của đồ thị G = (V,E). Công việc này có thể đưa về
việc tô màu các đỉnh của đồ thị đường L(G).Từ đó ta có kết quả sau:
χ’(G) = χ( L(G)).
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 16
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
2.6. Bài tập
Bài 1: Chứng minh các đồ thị sau là không phẳng: Đồ thị Peterson:
a

e j f g b

i h
d c
Bài giải:
Xác định đồ thị con bằng cách bỏ đi đỉnh b và ba cạnh liên thuộc với nó:
a

e j f g

i h
d c
Thực hiện phép rút gọn nối tiếp như sau:

a) Đồ thị được cho là phẳng. Nếu kẻ thêm cạnh (a, c’) thì đồ thị nhận được là
không phẳng vì có đồ thị con K
3,3
với tập đỉnh được chia thành hai tập con là {a,
b’, c} và {a’, b, c’}.
b) Đồ thị được cho là không phẳng vì chứa đồ thị con đồng phôi với K
5
có các
đỉnh b, g, e, d, h.
Bài 5. Cho G là một đơn đồ thị phẳng. Chứng minh rằng G có thể tô đúng bằng
hai màu khi và chỉ khi G là đồ thị phân đôi.
Bài giải:
(⇒) Giả sử G được tô đúng bằng hai màu xanh và đỏ. Khi đó G là đồ thị phân
đôi với hai tập đỉnh U gồm các đỉnh màu xanh và V gồm các đỉnh màu đỏ.
(⇐) Giả sử G là đồ thị phân đôi với hai tập đỉnh U và V. Khi đó mọi chu trình
trong G (nếu có) đều có độ dài chẵn. Lấy một đỉnh bất kỳ của G và tô bằng màu
xanh, sau đó mỗi đỉnh kề với đỉnh màu xanh được tô bằng màu đỏ và mỗi đỉnh
kề với đỉnh màu đỏ thì được tô bằng màu xanh. Do mọi chu trình trong G đều có
độ dài chẵn nên không thể có hai đỉnh kề của G được tô cùng một màu.
Bài 6. Chứng minh rằng một đơn đồ thị phẳng liên thông có thể tô đúng các miền
bằng hai màu khi và chỉ khi đó là một đồ thị Euler.
Bài giải:
(⇒) Nếu đồ thị G được tô đúng các miền bằng hai màu thì số miền bao quanh
mỗi đỉnh phải là số chẵn, do đó các đỉnh đều có bậc chẵn và G là đồ thị Euler.
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 18
a’
a b
b’
c
c’

. Khi đó có thể chơi như sau:
Bước 1: Gọi A là người được tô trước, anh ta tô mặt D
1
. Ta nhận thấy rằng: mặt
D
1
kề với không ít hơn 4 mặt; hai mặt kề với D
1
cùng qua một đỉnh của D
1
cũng
kề nhau (vì từ mỗi đỉnh chỉ có đúng 3 cạnh, trong đó đã có 2 cạnh thuộc mặt D
1
,
nên cạnh còn lại phải chung cho 2 mặt).
Bước 2: Sau khi người thứ hai tô, chắc chắn còn ít nhất 3 mặt kề với D
1
, đồng
thời kề nhau liên tiếp đôi một. Không giảm tổng quát, giả sử đó là D
2
, D
3
, D
4
.
Khi đó A tô D
3
.
Bước 3: Sau khi người thứ hai tô, chắc chắn còn lại một trong hai mặt D
2

ĐĐ
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
CHƯƠNG III
ỨNG DỤNG
3.1. Ứng dụng đồ thị trong giải toán logic:
3.1.1. Phương pháp:
Để giải bài toán T bằng cách thông qua đồ thị cần thực hiện lần lượt hai bước
sau:
Bước 1: Xây dựng đồ thị G mô tả các mối quan hệ:
+ 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 đã cho trong bài toán, dùng ngay các ký hiệu đối tượng để ghi tên điểm
tương ứng.
+ Cặp điểm x, y được nối với nhau bằng một cạnh với “đặc điểm t” khi và
chỉ khi các đối tượng x, y có mối quan hệ (t) với nhau. Khi đó bài toán T đã được
chuyển về bài toán D trên đồ thị.
Bước 2: Dựa vào các kết quả của lý thuyết đồ thị hoặc lý luận trực tiếp suy ra
đáp án của bài toán D.
Nếu đáp án của bài toán D còn dưới dạng “ngôn ngữ đồ thị”, thì căn cứ vào
phép đặt tương ứng khi xây dựng đồ thị mà diễn đạt thành đáp án bằng ngôn ngữ
thông thường (tức đáp án của bài toán T).
3.1.2. Áp dụng:
Bài 1. Trên một hòn đảo có một số cụm dân cư, mỗi cụm dân cư có hai đường
lớn và ba đường mòn đi ra. Mỗi đường lớn cũng như đường mòn đều dẫn tới
một cụm dân cư khác. Hai cụm dân cư khác nhau bất kỳ đều được nối liền bằng
đường lớn hoặc đường mòn. Hỏi trên đảo này có bao nhiêu đường mòn và bao
nhiêu đường lớn?
Bài giải:
Mỗi cụm dân cư có hai đường lớn và ba đường mòn đi ra, mỗi đường đều
dẫn tới một cụm dân cư khác nên phải có ít nhất 6 cụm dân cư. Mặc khác hai
cụm dân cư khác nhau đều có đường nối nhau nên mỗi cụm chỉ nối đến đúng 5

A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
B
X
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
Vì An và Bình đấu với nhau tối đa 5 ván thì chắc chắn sẽ có người thắng 2 ván
liên tiếp hoặc có người thắng 3 ván nên những đường xuất phát từ X đều không
có quá 5 cạnh. Cây có 10 đỉnh ngọn nên có 10 khả năng xảy ra.
Bài 3. Tại một giải bóng đá có 4 đội Anh, Đan Mạch, Hà Lan, Thụy Điển vào
bán kết. Có mấy dự đoán xếp hạng như sau:
1. Đan Mạch vô địch, Thụy Điển nhì.
2. Đan Mạch nhì, Hà Lan ba.
3. Anh nhì, Hà Lan tư.
Kết quả là mỗi dự đoán đúng được một đội.Hãy cho biết kết quả xếp hạng
của các đội?
Bài giải:

2
H
4
A
2
H
4
. . . .
Đ
2
H
3
Đ
2
H
3
. .

Đ
1
T
2
O
Đường tô đậm Đ
1
H
3
A
2
thỏa mãn điều kiện mỗi dự đoán đúng được một đội

được 2 bộ số mà trong mỗi bộ, từng đôi một đều là nguyên tố cùng nhau hoặc
không nguyên tố cùng nhau.
Bài giải:
Bước 1: Chuyển bài toán sang bài toán về đồ thị màu G(X,E).
- Đỉnh : Cho ứng mỗi số với một đỉnh X = {A, B, C, D, E, F}.
- Cạnh : Đoạn nối giữa 2 đỉnh tương ứng với 2 số :
+ Nguyên tố cùng nhau được tô màu xanh.
+ Không nguyên tố cùng nhau được tô màu đỏ.
Khi đó, ta được bài toán đồ thị màu: Trong đồ thị đầy đủ G (X,E) có 6 đỉnh
với 2 màu cạnh, thì ta luôn tìm được 2 “tam giác” với cạnh cùng màu.
Bước 2: Giải bài toán đồ thị.
Vì G là đồ thị đầy đủ có 6 đỉnh nên mỗi đỉnh của G là đầu mút của 5 cạnh,
và chúng được tô bởi chỉ 2 màu, nên mỗi đỉnh của G phải là mút của ít nhất 3
cạnh cùng màu.
Giả sử đỉnh A là mút của 3 cạnh AB, AC, AD cùng màu đỏ (đường liền nét).
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 23
v
1
3
2
1’
2’
3’
0 0
’
’
’
’
’
•

đỉnh A, cùng tất cả các cạnh thuộc nó. Ta được đồ thị con đầy đủ G
1
có 5 đỉnh.
NHÓM 10_PHƯƠNG PHÁP TOÁN SƠ CẤP Trang 24
LÝ THUYẾT ĐỒ THỊ ĐỒ THỊ PHẲNG
Nếu trong G1 có tam giác cùng màu thì bài toán đã được giải xong.
Ngược lại, trong G1 không có tam giác cùng màu, thì ta có thể biểu diễn G1
thành một hình 5 cạnh với màu đỏ và đường chéo màu xanh.
E
•
F• •D
C• •B
Bây giờ ta khôi phục lại đỉnh A thứ 6 và các cạnh màu thuộc nó. Xét 2 cạnh AD
và AF. Nếu chúng đều màu xanh thì ta có tam giác mới ADF có màu xanh. Nếu
AD hoặc AF màu đỏ thì ta có tam giác đỏ nữa được hình thành là ABD hoặc
ACF.
Vậy ngoài tam giác ABC, ta có thêm một tam giác nữa có các cạnh cùng
màu. Khẳng định đã được chứng minh.
•
F• •D
C• •B
Trong G luôn tồn tại hai tam giác có cạnh cùng màu đỏ hoặc xanh. Nếu cả hai
tam giác đều màu đỏ, thì ta có 2 bộ 3 số, mà trong mỗi bộ, chúng đôi một nguyên
tố cùng nhau. Nếu chỉ có một tam giác màu đỏ, thì ta được một bộ 3 số đôi một
nguyên tố cùng nhau, và một bộ 3 số đôi một không nguyên tố cùng nhau. Nếu
cả hai tam giác màu xanh, nghĩa là ta được hai bộ 3 số, mà trong mỗi bộ, chúng
đôi một không nguyên tố cùng nhau.
3.3. Những ứng dụng của bài toán tô màu đồ thị:
3.3.1. Điều khiển đèn hiệu nút giao thông:
Giả sử ta cần thiết lập một quy trình điều khiển đèn hiệu ở nút giao thông