Bài toán tô màu đồ thị và ứng dụng
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1016.48 KB, 35 trang )
Bạn đang đọc: Bài toán tô màu đồ thị và ứng dụng
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
VŨ
HOÀNG
LINH
BÀI
TOÁN
TÔ
MÀU
ĐỒ THỊ VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên – 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
VŨ
HOÀNG
LINH
BÀI
TOÁN
TÔ
MÀU
ĐỒ THỊ VÀ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TS. Trần Vũ Thiệu
Thái nguyên – 2015
1
MỞ
ĐẦU
Đồ thị là một cấu trúc toán học rời rạc, bao gồm hai yếu tố đỉnh và cạnh, và là
mô hình toán học cho nhiều vấn đề lý thuyết và thực tiễn đa dạng. Bài toán tô màu
cho các đỉnh (hay các cạnh) của một đồ thị là một chủ đề quan trọng và hấp dẫn của
lý thuyết đồ thị. Bài toán này có những ứng dụng thiết thực trong kinh tế, kỹ thuật
và đời sống. Chẳng hạn, ta thường gặp bài toán tô màu bản đồ, tô màu cho dây dẫn
điện. Một số vấn đề không liên quan đến tô màu cũng có thể được xử lý nhờ bài
toán tô màu: bố trí kho chứa hóa chất, thiết kế các bảng vi mạch điện tử, sắp xếp
lịch hỏi thi, bố trí các trạm truyền tin, xác lập các tuyến xe buýt thành phố, v.v
Lý thuyết đồ thị ra đời và phát triển gắn liền với tên tuổi của nhiều nhà toán
học nổi tiếng: Euler (Thụy sĩ), với bài toán về 7 cầu ở thành phố Königsberg,
König và Egeváry (Hungari), với phương pháp Hungari giải bài toán phân việc.
Về vấn đề tô màu đồ thị có nhiều kết quả lý thuyết đáng chú ý: Định lý Brooks,
Minty về tô màu đỉnh; Định lý König, Vizing, Shannon về tô màu cạnh, định lý 5
màu của Heawood (1890) và Định lý 4 màu của Appel và Haken (1976), đã giải
quyết được giả thuyết 4 màu nổi tiếng do Guthrie nêu ra lần đầu năm 1852.
“Bài toán tô màu đồ thị và ứng dụng”.
Luận văn này có mục đích tìm hiểu và trình bày các khái niệm cơ bản về đồ
thị và các dạng đồ thị thường gặp, về bài toán tô màu trên đồ thị (tô đỉnh, tô cạnh
và tô diện – tô màu bản đồ) và một số ứng dụng của các bài toán này. Trình bày các
kết quả lý thuyết, các định lý về tô màu trên các loại đồ thị khác nhau và các thuật
toán tô màu đỉnh và cạnh, dựa trên các kết quả lý thuyết đã có.
Nội dung luận văn được viết trong hai chương.
2
Chương 1 “Khái niệm cơ bản về đồ thị” nhắc lại các khái niệm cơ bản về đồ
thị: đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chu
trình, đồ thị liên thông, không liên thông, các phép toán trên đồ thị. Miêu tả nhiều
dạng đồ thị đặc biệt: rừng và cây, đồ thị hình sao, đồ thị vòng, đồ thị đường, đồ thị
bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy đủ, đồ thị đều (chính
qui), đồ thị Petersen, đồ thị Platon, đồ thị phẳng,
Chương 2 “Bài toán tô màu đồ thị” đề cập tới vấn đề tô màu các đỉnh, cạnh và
diện của một đồ thị. Trình bày các kết quả về tô màu đỉnh: định lý Brooks (1941),
định lý Minty (1962), các định lý tô màu đồ thị phảng, đặc biệt định lý bốn màu
(Appel và Haken, 1976). Về tô màu bản đồ (tô diện của đồ thị phẳng) có các định
lý về bản đồ 2 màu, bản đồ lập phương 3 màu và định lý bốn màu cho bản đồ. Về
tô màu cạnh của đồ thị: trình bày định lý Vizing (1964) về số màu tối thiểu cần tô,
định lý tô cạnh đồ thị đầy đủ, tô cạnh đồ thị hai phần (Định lý König, 1916) và
quan hệ với định lý bốn màu. Cuối chương đề cập tới đa thức màu, cho biết có thể
tô đỉnh của đò thị bằng k màu được không, nếu được thì có mấy cách tô.
Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS
–
TS Trần
Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành
cảm ơn các thầy giáo, cô giáo Trường Đại học Khoa học – Đại học Thái Nguyên,
Viện Toán hoc – Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và
tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.
Thái Nguyên 20 tháng 04 năm 2015
Tác giả
Vũ Hoàng Linh
3
Chương 1
KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ
Chương này trình bày các kiến thức cơ sở về lý thuyết đồ thị. Mục 1.1 nêu các
định nghĩa, khái niệm dùng trong lý thuyết đồ thị và các phép toán trên đồ thị. Mục
1.2 mô tả các dạng đồ thị thường gặp. Trong chương dẫn ra nhiều ví dụ minh họa.
Nội dung của chương được tham khảo chủ yếu từ các tài liệu [2], [3], [4] và [5].
1.1. ĐỊNH NGHĨA VÀ KÝ HIỆU
1.1.1. Khái niệm đồ thị
Trong thực tế ta thường gặp các sơ đồ giao thông (Hình 1.1) hay sơ đồ mạch
điện (Hình 1.2). Các sơ đồ này được khái quát thành sơ đồ vẽ ở Hình 1.3. Từ đó ta
đi tới định nghĩa sau.
Hình 1.1. Sơ đồ khu phố Hình 1.2. Sơ đồ mạch điện Hình 1.3. Đồ thị đại diện
Đồ thị (graph) là một tập hợp hữu hạn và khác rỗng các điểm, gọi là các đỉnh
(vertex) hay nút (node), và một tập hợp các đường (thẳng hay cong) nối liền một số
cặp điểm này, gọi là các cạnh (edge) của đồ thị (Số cạnh có thể bằng 0).
Mỗi đỉnh của đồ thị thường được ký hiệu bằng một chữ cái (a, b, c, hay A,
B, C, ) hoặc chữ số (1, 2, 3, ). Cạnh nối liền đỉnh v với đỉnh w được ký hiệu là
(v, w) hay đơn giản là vw (v và w có thể là các chữ số). Một cạnh có dạng (a, a),
nối đỉnh a với chính nó, gọi là một khuyên (loop).
Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ V
×
V thì để cho gọn, ta viết
G = (V, E). Ta cũng dùng ký hiệu V(G) để chỉ tập đỉnh và E(G) để chỉ tập cạnh của
đồ thị G. Ký hiệu n = |V(G)| là số đỉnh và m = |E(G)| là số cạnh của đồ thị G.
4
Để dễ hình dung, mỗi đồ thị thường được biểu diễn bởi một hình vẽ trên mặt
phẳng. Chẳng hạn, Hình 1.3 biểu diễn một đồ thị có 5 đỉnh: P, Q, R, S, T và 8 cạnh
(mỗi cạnh là một đoạn thẳng nối hai đỉnh). Chú ý rằng điểm cắt nhau của hai cạnh
PS và QT trong hình vẽ không phải là một đỉnh của đồ thị.
Đỉnh v gọi là kề (adjacent) đỉnh w nếu có một cạnh của đồ thị nối v với w.
Nếu ký hiệu cạnh này là e thì ta viết e = (v,
w) và nói cạnh e liên thuộc (incident) v,
w hay v, w là hai đầu mút của e. Cạnh e và e’ gọi là kề nhau nếu e, e’ có chung đỉnh.
Hai cạnh e và e’ cùng nối một cặp đỉnh gọi là cạnh kép (multiple edge). Đồ thị
không có cạnh kép gọi là một đơn đồ thị (simple graph). Trái lại, gọi là một đa đồ
thị. Hình 1.4 và 1.5 minh họa cạnh kép và khuyên trong đa đồ thị.
Hình 1.4. Cạnh kép và đa đồ thị Hình 1.5. Khuyên trong đa đồ thị
Một cạnh của đồ thị gọi là cạnh có hướng (directed edge) nếu có qui định rõ
một đầu mút của cạnh là đỉnh đầu, mút kia là đỉnh cuối. Cạnh có hướng còn được
gọi là một cung.
Một đồ thị gồm toàn các cạnh gọi là đồ thị vô hướng (undirected graph), đồ thị
gồm toàn các cung gọi là đồ thị có hướng (digraph). Một đồ thị vừa có cạnh vừa có
cung gọi là đồ thị hỗn hợp (mixed graph). Bằng cách thay một cạnh bởi hai cung có
hướng ngược chiều nhau, ta có thể qui mọi đồ thị về đồ thị có hướng. Hình 1.6 mô
tả một đồ thị có hướng.
Hình 1.6. Đồ thị có hướng Hình 1.7. Đồ thị không liên thông
5
Bậc (degree) của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc nó, ký
hiệu là (v). Đỉnh có bậc 0 gọi là đỉnh cô lập (isolated vertex), đỉnh có bậc 1 gọi là
đỉnh treo (end-vertex), Tương tự, trong đồ thị có hướng ta gọi bậc ra (bậc vào) của
đỉnh v là số cung đi khỏi v (số cung đi tới v), ký hiệu tương ứng là
+
(v) và
–
(v).
Qui ước: khuyên tại một đỉnh được tính 2 lần. Ví dụ trong đồ thị vẽ ở Hình 1.7 ta
có (P) = (S) = (U) = (V) = 2; (Q) = (R) = 3 và (T) = 4 (có khuyên ở T).
Dễ dàng chứng minh các tính chất sau đây về bậc của đỉnh trong đồ thị:
a) Trong một đồ thị vô hướng, tổng số bậc của mọi đỉnh bằng hai lần số cạnh
của đồ thị và số đỉnh có bậc lẻ bao giờ cũng là một số chẵn.
b) Trong một đồ thị có hướng, tổng các bậc vào của mọi đỉnh bằng tổng các
bậc ra của mọi đỉnh và bằng tổng số cung trong đồ thị.
Nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng các cung
trong đồ thị. Vì thế, khi bỏ qua hướng trên các cung (đổi cung thành cạnh) ta sẽ
nhận được một đồ thị vô hướng, gọi là đồ thị nền của đồ thị có hướng đã cho.
1.1.2. Phép toán trên đồ thị
Sau đây ta tập trung chủ yếu xét các đồ thị vô hướng và một số phép toán.
• Đồ thị con (subgraph) của một đồ thị G là đồ thị nhận được từ G bằng cách
bỏ đi một số đỉnh và một số cạnh của nó. Nói chính xác, H = (V(H), E(H)) là một
đồ thị con của G nếu V(H) V(G) và E(H) E(G). Ta cũng nói G chứa H. H gọi
là đồ thị con cảm sinh (induced subgraph) của G nếu H là một đồ thị con của G và
E(H) = {(x, y) ∈ E(G) : x, y ∈ V(H)}. Ở đây H là đồ thị con của G sinh bởi V(H).
Vì thế ta còn viết H = G[V(H)]. Đồ thị con H của G gọi là đồ thị con bao trùm nếu
V(H) = V(G), tức tập đỉnh của H và của G trùng nhau.
• Với v ∈ V(G), ký hiệu G – v là đồ thị con của G cảm sinh bởi V(G) \ {v},
tức đồ thị nhận được từ G bằng cách bỏ đỉnh v và các cạnh liên thuộc v.
• Với e ∈ E(G), ta định nghĩa G – e := (V(G), E(G) \ {e}), tức đồ thị nhận
được từ G bằng cách xóa cạnh e (không xóa hai đầu mút của e). Ta cũng định nghĩa
6
G \ e là đồ thị nhận được bằng cách co cạnh e thành một điểm duy nhất. Hình 1.8
minh họa các đồ thị G, G – e và G \ e.
Hình 1.8. Đồ thị G, cạnh e và các đồ thị G e và G \ e tương ứng
1.1.3. Đồ thị đẳng cấu
Hai đồ thị G
1
và G
2
gọi là đẳng cấu (isomorphic) nếu chúng có số đỉnh và số
cạnh như nhau và có phép tương ứng một
–
một giữa tập đỉnh của G
1
và G
2
sao cho
hai đỉnh được nối với nhau bởi một cạnh trong đồ thị này khi và chỉ khi hai đỉnh
tương ứng trong đồ thị kia cũng được nối với nhau bởi một cạnh và ngược lại. Hình
1.9 vẽ các đồ thị đẳng cấu với đồ thị vẽ ở Hình 1.3. Các cạnh của hai đồ thị ở Hình
1.9 chỉ gặp nhau ơ đinh. Các đồ thị đẳng cấu được xem là tương đương (là một).
Hình 1.9. Các đồ thị đẳng cấu với đồ thị ở Hình 1.3
1.1.4. Đồ thị liên thông
Có thể ghép hai đồ thị để lập lên một đồ thị lớn hơn. Cho G
1
= (V(G
1
), E(G
1
)),
G
2
= (V(G
2
), E(G
2
)) với V(G
1
)
∩V(G
2
) = ∅. Khi đó, hợp (union) G
1
∪ G
2
là đồ thị
có tập đỉnh là V(G
1
) ∪ V(G
2
) và tập cạnh là E(G
1
) ∪ E(G
2
) (Hình 1.10).
Hình 1.10. Đồ thị G
1
, G
2
và hợp G
1
∪ G
2
Hình 1.11. Đồ thị không liên thông
Hầu hết các đồ thị thường gặp là đồ thị ghép. Một đồ thị được gọi là liên thông
(connected graph) nếu nó không biểu diễn được dưới dạng hợp của hai hay nhiều
7
đồ thị. Trái lại, đồ thị gọi là không liên thông (disconnected graph). Rõ ràng là bất
cứ một đồ thị không liên thông G nào cũng biểu diễn được dưới dạng hợp của các
đồ thị liên thông, mỗi đồ thị liên thông gọi là một thành phần liên thông của G.
Chẳng hạn, một đồ thị gồm ba thành phần liên thông được vẽ ở Hình 1.11.
Hình 1.12. Các kiểu đồ thị liên thông không quá 5 đỉnh
8
Khi cần chứng minh một kết luận nào đó cho các đồ thị nói chung, ta thường
chứng minh kết quả tương ứng cho các đồ thị liên thông, sau đó áp dụng kết quả
thu được cho từng thành phần liên thông riêng lẻ của đồ thị. Một bảng gồm tất cả
các đồ thị liên thông (không ghi tên đỉnh) có tối đa 5 đỉnh được vẽ ở Hình 1.12.
1.1.5. Đường và chu trình trong đồ thị vô hướng
Đường (path) P từ đỉnh v tới đỉnh w là một dãy liên tiếp các cạnh có dạng:
(a
0
, a
1
), (a
1
, a
2
),, (a
k-1
, a
k
) với (a
i-1
, a
i
) E(G), a
0
= v, a
k
= w và k 1,
trong đó các đỉnh a
0
, a
1
,, a
k
đều khác nhau. Để đơn giản, đôi khi ta viết P = {a
0
,
a
1
,, a
k
} và nói đó là đường nối đỉnh v và đỉnh w. Đỉnh v gọi là đỉnh đầu, đỉnh w
gọi là đỉnh cuối của đường P. Một đường nối một đỉnh với chính nó (đỉnh đầu trùng
với đỉnh cuối) gọi là một chu trình (cycle). Độ dài (length) của đường (chu trình) là
số cạnh của đường (chu trình) đó.
Ví dụ với đồ thị vẽ ở Hình 1.9 một đường nối đỉnh P và đỉnh R là (P,
T), (T,
Q), (Q, R) hay đơn giản là P, T, Q, R. Hai đường khác từ P tới R là P, T, S, R và P,
Q, R hay P, S, R. Đồ thị này có các chu trình sau:
(P, Q), (Q, R), (R, S), (S, T), (T, P); (Q, S), (S, T), (T, Q), v.v
1.1.6. Biểu diễn đồ thị bằng ma trận
Mặc dù cách biểu diễn đồ thị bằng hình vẽ gồm các điểm được nối với nhau
bởi các cạnh khá thuận tiện, song cách này không còn phù hợp nếu ta muốn lưu giữ
một đồ thị cỡ lớn trên máy tính. Có cách lưu giữ một đơn đồ thị là liệt kê các đỉnh
kề với mỗi đỉnh của đồ thị. Ví dụ cho cách biểu diễn này được chỉ ra ở Hình 1.13.
Hình 1.13. Liệt kê các đỉnh kề Hình 1.14. Đồ thị rỗng N
4
Một cách biểu diễn hữu ích khác là dùng các ma trận.
y
u
v
w
x
u : v, y
v : u, w, y
w: v, x, y
x w, y
y : u, v, w, x
∙
∙
∙
∙
9
• Ma trận kề: Nếu G là một đồ thị với các đỉnh được đánh số 1, 2, …, n, thì
ma trận kề (adjacency matrrix) cuả G là ma trận vuông A cấp n, phần tử ở hàng i
cột j của A bằng số cạnh nối đỉnh i và đỉnh j của đồ thị.
• Ma trận liên thuộc: Nếu các cạnh của đồ thị cũng được đánh số 1, 2, …, m,
thì ma trận liên thuộc (incidence matrrix) của G là ma trận chữ nhật M cấp n×m,
phần tử ở hàng i cột j của M bằng 1 nếu đỉnh i kề cạnh j và bằng 0 nếu trái lại.
Hình 1.15 vẽ đồ thị G cùng với ma trận kề và ma trận liên thuộc của nó.
Hình 1.15. Ma trận kề và ma trận liên thuộc
1.2. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Mục này trình bày một số dạng đồ thị đặc biệt, đáng chú ý và hay được dùng
trong lý thuyết đồ thị và trong các ứng dụng.
1.2.1 Đồ thị rỗng (Đồ thị không)
Một đồ thị có đỉnh, nhưng không có cạnh nào (tập cạnh rỗng) gọi là một đồ thị
rồng (empty graph) hay đồ thị không (null graph). Ký hiệu đồ thị rỗng n đỉnh là N
n
.
Mỗi đỉnh của một đồ thị rỗng là một đỉnh cô lập (đỉnh bậc 0) và các đồ thị rỗng rất
ít được chú ý. Một đồ thị rỗng N
4
được vẽ ở Hình 1.14.
1.2.2. Rừng và cây
Có thể hiểu đồ thị liên thông theo nghĩa tương đương như sau. Một đồ thị vô
hướng gọi là liên thông nếu có đường đi nối hai đỉnh bất kỳ của đồ thị. Trái lại, đồ
thị gọi là không liên thông. Đồ thị không liên thông sẽ bị tách thành một số đồ thị
con liên thông, đôi một không có đỉnh chung. Mỗi đồ thị con liên thông như thế là
một thành phần liên thông. Cạnh e gọi là một cầu (bridge) nếu xóa e (không xóa
10
đỉnh) thì đồ thị còn lại sẽ tăng thêm một thành phần liên thông, mỗi thành phần
gồm ít nhất một cạnh. Ví dụ, các đồ thị vẽ ở Hình 1.9 là liên thông, còn đồ thị vẽ ở
Hình 1.11 là không liên thông (gồm 3 thành phần liên thông).
Một đồ thị vô hướng không có chu trình gọi là một rừng (forest). Một rừng
liên thông gọi là một cây (tree), tức cây là một đồ thị liên thông và không có chu
trình. Ví dụ phả hệ của một họ tộc là một cây (cây phả hệ). Rừng có thể gồm nhiều
thành phần liên thông khác nhau, mỗi thành phần liên thông là một cây. Như vậy,
rừng gồm nhiều cây. Đỉnh có bậc 1 trong cây gọi là một lá (leaf). Đồ thị hình sao là
một cây có duy nhất một đỉnh không phải là lá.
Một đồ thị con, không chứa chu trình của đồ thị G gọi là một cây của G. Một
đồ thị con bao trùm của G mà là một cây được gọi là một cây bao chùm (spanning
tree) của G. Một số tính chất đặc trưng của cây: cây n đỉnh có đúng n
–
1 cạnh, trong
một cây, bao giờ cũng có một đường đi duy nhất nối một cặp đỉnh bất kỳ của cây.
Các ví dụ về rừng và cây được vẽ ở Hình 1.16.
Hình 1.16. Ví dụ về rừng và cây
1.2.3. Đồ thị đầy đủ
Một đơn đồ thị trong đó mọi cặp đỉnh (khác nhau) đều kề nhau, gọi là một đồ
thị đầy đủ (completed graph). Đồ thị đầy đủ n đỉnh ký hiệu là K
n
. Số cạnh của K
n
bằng n(n
–
1)/2. Đồ thị K
4
và K
5
được vẽ ở Hình 1.17.
Hình 1.17. Đồ thị đầy đủ K
4
và K
5
11
1.2.4. Đồ thị vòng, đồ thị đường và đồ thị bánh xe
Một đồ thị liên thông và mọi đỉnh bậc 2 gọi là một đồ thị vòng (cycle graph).
Ký hiệu đồ thị vòng n đỉnh là C
n
. Đồ thị nhận được từ C
n
bằng cách bỏ di một cạnh
bất kỳ gọi là một đồ thị đường (path graph) n đỉnh, ký hiệu là P
n
. Đồ thị nhận được
từ C
n – 1
bằng cách thêm vào một đỉnh v và nối mỗi đỉnh của C
n – 1
với v bởi một
cạnh, gọi là một đồ thị bánh xe (wheel) n đỉnh, ký hiệu là W
n
.
Các đồ thị C
6
, P
6
và W
6
được vẽ ở Hình 1.18.
Hình 1.18. Đồ thị vòng C
6
, đồ thị đường P
6
và đồ thị bánh xe W
6
1.2.5. Đồ thị đều (đồ thị chính qui)
Một đồ thị mà mọi đỉnh có bậc bằng nhau gọi là một đồ thị đều hay đồ thị
chính qui (regular graph). Nếu mọi đỉnh có bậc r thì đồ thị được gọi là đồ thị đều
(chính qui) bậc r hoặc r
–
chính qui. Có tầm quan trọng đặc biệt là các đồ thị bậc 3
(cubic graph), tức các đồ thị đều (chính qui) bậc 3. Một ví dụ điển hình về đồ thị
bậc 3 là đồ thị Petersen (Petersen graph), đồ thị này được vẽ ở Hình 1.19. Chú ý
rằng đồ thị rỗng N
n
là đồ thị chính qui bậc 0, đồ thị vòng C
n
là đồ thị chính qui bậc
2 và đồ thị đầy đủ K
n
là đồ thị chính qui bậc n
–
1.
Hình 1.19. Đồ thị Petersen (chính qui bậc 3)
1.2.6. Đồ thị Platon
Trong các đồ thị chính qui, đáng chú ý là các đồ thị Platon (Platonic graph).
Đồ thị Platon được hình thành từ các đỉnh và các cạnh của 5 khối đa diện đều: hình
12
tứ diện, hình tám mặt, hình lập phương, khối hai mươi mặt và khối mười hai mặt
(Hình 1.20).
Hình 1.20. Đồ thị Platon
1.2.7. Đồ thị hai phần
Nếu tập đỉnh của đồ thị G có thể chia tách ra thành hai tập rời nhau A và B sao
cho mỗi cạnh của G nối một đỉnh thuộc A với một đỉnh thuộc B, thì G được gọi là
một đồ thị hai phần (bipartite graph) (Hình 1.21). Nói một cách khác, đồ thị hai
phần là đồ thị mà có thể tô các đỉnh của nó bằng hai màu đen và trắng sao cho mỗi
cạnh nối một đỉnh đen (trong A) và một đỉnh trắng (trong B).
Có thể chứng minh rằng đơn đồ thị G là đồ thị hai phần khi và chỉ khi mọi chu
trình trong G đều có độ dài (số cạnh) chẵn.
Đồ thị hai phần đầy đủ (complete bipartite graph) là một đồ thị hai phần mà
mỗi đỉnh trong A được nối với mỗi đỉnh trong B bằng đúng một cạnh. Ta ký hiệu
đồ thị hai phần có r đỉnh đen và s đỉnh trắng là K
r,s
. Các đồ thị K
1,3
; K
2,3
, K
3,3
và K
4,3
được vẽ ở Hình 1.22. Dễ dàng kiểm tra lại rằng K
r, s
có (r
+
s) đỉnh và r×s cạnh.
Hình 1.21. Đồ thị hai phần Hình 1.22. Đồ thị hai phần đầy đủ: K
1,3
, K
2,3
, K
3,3
, K
4,3
Tứ diện Hình tám mặt Hình lập phương Khối 20 mặt Khối 12 mặt
13
1.2.8. Đồ thị lập phương
Trong các đồ thị hai phần đều (mọi đỉnh có cùng bậc), người ta đặc biệt quan
tâm tới các đồ thị lập phương (cubes). Ký hiệu Q
k
là k
–
lập phương (k
–
cube), đó là
một đồ thị đều, bậc k (k
–
chính qui) mà các đỉnh của nó có thể đặt tương ứng với
dãy số (a
1
, a
2
, …, a
k
), trong đó mọi a
i
= 0 hoặc 1, và các cạnh của đồ thị nối liền
hai đỉnh tương ứng với hai dãy số chỉ khác nhau ở một vị trí. Để ý rằng Q
3
là đồ thị
hai phần đều, bậc 3 (Hình 1.23). Có thể kiểm tra lại rằng Q
k
có 2
k
đỉnh và k×2
k – 1
cạnh, và là đồ thị k
–
chính qui (đồ thị đều, bậc k).
Hình 1.23. Đồ thị hai phần đều, bậc 3: Q
3
Hình 1.24. Phần bù của đơn đồ thị G
1.2.9. Phần bù của đơn đồ thị
Nếu G là một đơn đồ thị với tập đỉnh V(G), thì phần bù (complement)
G
của
G là một đơn đồ thị, với cùng tập đỉnh V(G) và hai đỉnh kề nhau trong
G
khi và
chỉ khi chúng không kề nhau trong G. Chẳng hạn, Hình 1.24 vẽ đồ thị G và phần bù
G
của nó. Có thể thấy rằng phần bù của một đồ thị đầy đủ là một đồ thị rỗng và
phần bù của một đồ thị hai phần đầy đủ là hợp của hai đồ thị đầy đủ.
1.2.10. Đồ thị phẳng
Một đồ thị (hay đa đồ thị) G gọi là đồ thị phẳng (planar graph) khi nào nó có
thể biểu diễn được trên một mặt phẳng sao cho ứng với mỗi đỉnh là một điểm và
ứng với mỗi cạnh là một đoạn thẳng hay cong và bất kỳ hai cạnh nào cũng không
có điểm chung khác với các đầu mút của chúng. Chẳng hạn, đồ thị vẽ ở Hình 1.4 và
Hịnh 1.5 là các (đa) đồ thị phẳng.
Khi đó, mỗi miền mặt phẳng hạn định bởi các cạnh và không chứa đỉnh hoặc
cạnh ở bên trong của nó, gọi là một diện (face) của đồ thị phẳng G. Biên (boundary)
của một diện là chu trình tạo nên bởi các cạnh hạn định nó. Hai diện gọi là kề nhau
G
G
14
(adjacent) khi nào biên của chúng có ít nhất một cạnh chung (hai diện chỉ có đỉnh
chung thì không xem là kề). Rõ ràng mỗi đồ thị phẳng liên thông đều có một diện
vô hạn duy nhất, còn mọi diện khác đều là diện hữu hạn.
Ví dụ. Một bản đồ địa lý không có đảo (không có khuyên) là một đồ thị phẳng:
mỗi đỉnh là điểm chung của ít nhất ba đường biên giới (bậc của đỉnh ≥ 3), mỗi cạnh
là một đoạn đường biên giới nối hai đỉnh và mỗi diện là một nước.
Đồ thị phẳng có các đặc điểm đáng chú ý sau:
• Trong một đồ thị phẳng liên thông, giữa số đỉnh n, số cạnh m và số diên d có
hệ thức: n – m + d = 2 (công thức Euler).
• Trong một đơn đồ thị phẳng phải có ít nhất một đỉnh với bậc ≤ 5.
• Đồ thị K
5
(Hình 1.17) và K
3,3
(Hình 1.22) là hai đồ thị không phẳng.
• Một đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con nào thuộc kiểu
K
5
hay K
3,3
(Định lý Kuratowski).
Ví dụ. Hình lập phương vẽ ở Hình 1.25a là một đồ thị phẳng. Biểu diễn phẳng
của đồ thị được vẽ ở Hình 1.25b. Đồ thị này có số đỉnh n = 8, số cạnh m = 12 và số
diện d = 6 (5 diện hữu hạn và 1 diện vô hạn). Công thức Ơle đương nhiên đúng đối
với đồ thị phẳng này (8 – 12 + 6 = 2).
Hình 1.25. a) Hình lập phương; b) Biểu diễn phẳng
Tóm lại, chương này đã đề cập tới các khái niệm cơ bản về đồ thị: đỉnh, cạnh,
bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chu trình, đồ thị liên
thông và không liên thông. Trình bày các phép toán thường dùng trên đồ thị (thêm,
bớt đỉnh hoặc cạnh). Miêu tả nhiều dạng đồ thị đặc biệt: rừng và cây, đồ thị hình
sao, đồ thị vòng, đồ thị bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy
đủ, đồ thị đều (chính qui), đồ thị Petersen, đồ thị Platon, đồ thị phẳng,
15
Chương 2
BÀI TOÁN TÔ MÀU ĐỒ THỊ
Chương này đề cập tới bài toán tô màu đồ thị và giới thiệu định lý bốn màu
nổi tiếng. Mục 2.1 xét bài toán tô màu các đỉnh của đồ thị. Mục 2.2 xét bài toán tô
màu bản đồ. Mục 2.3 xét bài toán tô màu các cạnh của đồ thị. Cuối chương, ở mục
2.4, đề cập tới đa thức màu và vấn đề có bao nhiêu cách tô màu có thể. Nội dung
của chương được tham khảo chủ yếu từ các tài liệu [2], [3], [5] và [6].
2.1. TÔ MẦU CÁC ĐỈNH CỦA ĐỒ THỊ
Nhiều vấn đề kỹ thuật hiện đại (chẳng hạn, tin học và tự động hóa) đưa tới
việc tô màu các đỉnh của một đồ thị G, sao cho hai đỉnh kề nhau có các màu khác
nhau. Để cho gọn, ta sẽ nói một cách tô như thế là một cách tô đúng. Đương nhiên
nếu G có n đỉnh thì chỉ việc dùng n màu khác nhau là có thể tô đúng được rồi.
Nhưng nhiều khi không cần tới n màu mà chỉ cần một số màu ít hơn cũng tô đúng
được. Chẳng hạn, nếu đồ thị G không có chu trình thì chỉ cần 2 màu là đủ tô đúng
trong mọi trường hợp. Do đó vấn đề đặt ra là: số màu tối thiểu cần thiết để tô đúng
các đỉnh của một đồ thị cho trước là bao nhiêu?
Ta nói một đồ thị là k
–
sắc tính (k
–
colourable) nếu nó có thể tô đúng bằng k
màu. Số k nhỏ nhất mà G còn là k
–
sắc tính, nghĩa là số màu tối thiểu cần thiết để
tô đúng được các đỉnh của G, gọi là số sắc tính hay sắc số (chromatic number) của
đồ thị G và viết (G) = k.
Hình 2.1. Sắc số của đồ thị: (G) = 4
16
Chẳng hạn, đồ thị G vẽ ở Hình 2.1 có (G) = 4. Các màu được biểu thị bằng
chữ cái Hy lạp (, , và ). Vì vậy, G là k
–
sắc tính với mọi k ≥ 4.
Vấn đề tìm số sắc tính của một đồ thị thường rất phức tạp (trừ khi G không có
chu trình), và cho tới nay nó vẫn chưa có một lời giải thỏa đáng. Trong mục này sẽ
trình bày một số kết quả đáng chú ý về các đồ thị k
–
sắc tính.
Sau đây ta giả thiết G là đơn đồ thị vô hướng, liên thông và không có khuyên.
Rõ ràng, sắc số của đồ thị đầy đủ n đỉnh bằng n: χ(K
n
) = n. Vì vậy có các đồ
thị với sắc số lớn tùy ý. Theo chiều ngược lại, χ(G) = 1 khi và chỉ khi G là đồ thị
không (null graph), tức là đồ thị G có đỉnh nhưng không có cạnh, và χ(G) = 2 khi
và chỉ khi G là một đồ thị hai phần khác không (non-null bipartite graph). Chú ý
rằng một cây bất kỳ, cũng như mọi chu trình độ dài chẵn bất kỳ là 2
–
sắc tính.
Ta có thể dễ dàng lấy ví dụ về đồ thị là 3 – sắc tính. Chẳng hạn, các chu trình
độ dài lẻ hay các đồ thị bánh xe với một số lẻ đỉnh và đồ thị Petersen là 3
–
sắc tính.
Các đồ thị bánh xe với một số chẵn đỉnh là 4
–
sắc tính. Trong [1] đưa ra một lớp đồ
thị phẳng 3
–
sắc tính đáng chú ý, đó là các đồ thị với n ≥ 6 đỉnh và mọi đỉnh có bậc
3 (Hình 2.2).
Hình 2.2. Đồ thị phẳng đẳng cấp bậc 3 là 3
–
sắc tính
Ta có thể nói đôi điều về số sắc tính (sắc số) của một đồ thị tuỳ ý: Nếu đồ thị
có n đỉnh thì sắc số của nó không vượt quá n, và nếu đồ thị chứa K
r
(đồ thị đầy đủ r
đỉnh) như một đồ thị con thì sắc số của nó không ít hơn r. Nhìn chung, các kết quả
này không giúp ta biết chính xác sắc số của một đồ thị. Tuy nhiên, nếu biết bậc của
các đỉnh trong đồ thị thì ta có thể biết nhiều hơn.
Định lý 2.1. Nếu đơn đồ thị G có bậc lớn nhất của đỉnh bằng Δ thì G là (Δ
+
1)
–
sắc tính.
17
Chứng minh. Dùng phương pháp quy nạp toán học theo số đỉnh của G. Giả
sử G là một đơn đồ thị n đỉnh. Nếu ta xoá một đỉnh bất kỳ v, cùng với các cạnh liên
thuộc nó, thì đồ thị còn lại là một đơn đồ thị (n
–
1) đỉnh và bậc lớn nhất của đỉnh
cùng lắm bằng Δ (xem Hình 2.3). Theo giả thuyết quy nạp, đồ thị này là (Δ
+
1)
–
sắc tính. Giữ nguyên màu của các đỉnh trong đồ thị này, ta sẽ tô cho đỉnh v một
màu, khác với những màu đã tô cho các đỉnh kề v (số này nhiều nhất bằng ). Kết
quả là G được tô bằng ( +
1) màu, tức G là ( +
1)
–
sắc tính.
∎
Hình 2.3. Minh họa chứng minh Định lý 2.1
Bằng xử lý tinh tế hơn, có thể làm mạnh thêm Định lý 2.1 và đi tới kết quả sau
đây, với tên gọi Định lý Brooks. Chứng minh xem [5], tr. 86 – 88.
Định lý 2.2. (Brooks, 1941) Nếu G là một đơn đồ thị liên thông mà không
phải là một đồ thị đầy đủ và nếu bậc lớn nhất của đỉnh là ≥ 3 thì G là
–
sắc tính.
Cả hai định lý trên đều rất hữu ích, đặc biệt khi bậc của các đỉnh xấp xỉ như
nhau. Chẳng hạn theo Định lý 2.1, mỗi đồ thị lập phương (cubic graph) là 4
–
sắc
tính, và theo Định lý 2.2, mỗi đồ thị lập phương liên thông, khác đồ thị đầy đủ K
4
,
là 3
–
sắc tính. Mặt khác, nếu đồ thị có vài đỉnh với bậc lớn thì các định lý này cho
ta rất ít thông tin. Điều này được minh hoạ rõ bởi đồ thị hai phần đầy đủ K
1,s
. Định
lý Brooks cho thấy đồ thị này là s
–
sắc tính, nhưng thực tế chỉ cần dùng 2 màu là có
thể tô đúng các đỉnh của đồ thị loại này, nghĩa là K
1,s
là 2
–
sắc tính với mọi s.
Không có cách nào hiệu quả để thoát khỏi tình trạng này.
Tình trạng tồi tệ này sẽ không xảy ra, nếu ta giới hạn chỉ xét các đồ thị phẳng.
Trên thực tế, có thể dễ dàng chứng minh kết quả khá mạnh nói rằng mọi đơn đồ thị
phẳng là 6
–
sắc tính.
Định lý 2.3. Mọi đơn đồ thị phẳng là 6
–
sắc tính.
18
Chứng minh. (Tương tự như Định lý 2.1, tức là dùng phương pháp quy nạp
theo số đỉnh của đồ thị) Hiển nhiên định lý đúng đối với các đơn đồ thị phẳng
không quá 6 đỉnh. Giả sử G là một đơn đồ thị phẳng n đỉnh, và mọi đơn đồ thị
phẳng (n
–
1) đỉnh là 6
–
sắc tính. Do đồ thị G phẳng nên G chứa một đỉnh v có bậc
nhiều nhất là 5. Nếu xoá v và các cạnh liên thuộc v thì đồ thị còn lại có n
–
1 đỉnh,
và vì vậy nó là 6
-sắc tính (xem Hình 2.4). Giữ nguyên màu của các đỉnh trong đồ
thị này, ta tô cho đỉnh v bằng màu, khác với những màu đã tô cho các đỉnh kề v (số
này không quá 5). Kết quả là G được tô bằng 6 màu, tức G là 6
–
sắc tính. ∎
Hình 2.4. Minh họa chứng minh Định lý 2.3
Cũng như Định lý 2.1, có thể làm mạnh thêm Định lý 2.3 này bằng cách xử lý
tinh tế hơn. Kết quả nhận được gọi là Định lý 5
màu (Five Colour Theorem).
Định lý 2.4. Một đơn đồ thị phẳng bao giờ cũng là 5
–
sắc tính.
Chứng minh. Tương tự như định lý 2.3, tuy nhiên các chi tiết sẽ phức tạp hơn.
Ta chứng minh định lý bằng phương pháp quy nạp theo số đỉnh. Hiển nhiên định lý
đúng đối với đơn đồ thị phẳng ít hơn 6 đỉnh. Giả sử G là một đơn đồ thị phẳng n
đỉnh, và mọi đơn đồ thị phẳng n
–
1 đỉnh là 5
–
sắc tính. Do đồ thị G phẳng nên G
chứa một đỉnh v với bậc không quá 5. Cũng như trong chứng minh định lý trước,
sau khi xoá đỉnh v và các cạnh liên thuộc v, ta được một đơn đồ thị n
–
1 đỉnh và đồ
thị này là 5
–
sắc tính. Mục đích của ta bây giờ là tô đỉnh v bằng một trong 5 màu
này, và như vậy sẽ hoàn thành việc tô các đỉnh của G bằng 5 màu.
Nếu bậc của đỉnh v nhỏ hơn 5 thì v có thể được tô bằng màu bất kỳ, chưa
dùng để tô cho các (tối đa là 4) đỉnh kề v, và như vậy hoàn thành chứng minh định
lý trong trường hợp này. Giả sử bậc của v bằng 5 và 5 đỉnh kề v là v
1
,, v
5
, được
19
sắp xếp quanh v theo chiều kim đồng hồ như vẽ ở Hình 2.5. Nếu các đỉnh v
1
,, v
5
đôi một kề nhau thì G chứa đồ thị không phẳng K
5
như một đồ thị con, vô lý! Vậy
phải có ít nhất 2 trong số các đỉnh v
i
(chẳng hạn, v
1
và v
3
) không kề nhau.
Bây giờ ta co hai cạnh vv
1
và vv
3
về đỉnh v, và nhận được một đồ thị phẳng có
n – 2 đỉnh. Theo giả thiết qui nạp, ta có thể tô đúng nó bằng 5 màu. Sau khi tô đồ thị
này, ta khôi phục trở lại hai cạnh ban đầu và tô cho v
1
và v
3
. bằng màu đã tô cho v,
còn v thì tô bằng màu thứ 5 còn lại (ngoài những màu đã tô cho các đỉnh kề v). Kết
quả là bao giờ ta cũng có thể tô cho các đỉnh của G bằng 5 màu, nghĩa là G là 5
–
sắc tính.
∎
Một câu hỏi tự nhiên đặt ra là liệu có thể làm mạnh hơn nữa định lý này được
không. Điều này dẫn đến một trong những bài toán nổi tiếng nhất trong toán học,
tồn tại hơn một thế kỷ, đó là bài toán bốn màu (Four-Colour Problem). Theo một
cách diễn đạt khác, bài toán này đã được đặt ra lần đầu tiên vào năm 1852, và cuối
cùng được K. Appel và W. Haken giải quyết năm 1976.
Hình 2.5. Minh họa Định lý 2.4
Hình 2.6. Tìm nơi để hóa chất a – e
Định lý 2.5. (Appel và Haken, 1976) Mọi đơn đồ thị phẳng là 4
–
sắc tính.
Chúng minh định lý này được thực hiện trong một số năm và tiêu tốn nhiều
thời gian chạy máy tính, suy cho cùng nó dựa trên việc mở rộng phức tạp các ý
tưởng trong chứng minh định lý 5
–
màu.
Ứng dụng thực tế. Ta nêu một ứng dụng đơn giản của việc tô màu đỉnh. Giả
sử một nhà hóa học muốn cất giữ 5 loại hóa chất a, b, c, d và e trong kho. Một số
hóa chất có tương tác mạnh khi tiếp xúc, vì thể chúng cần được để cách xa nhau
20
trong kho. Dấu * trong bảng sau cho biết những cặp hóa chất không được để gần
nhau. Cần bao nhiêu nơi trong kho để cất giữ hóa chất?
Để trả lời câu hỏi này, ta vẽ một đồ thị 5 đỉnh, mỗi đỉnh đại diện cho một loại
hóa chất, hai đỉnh là kề nhau khi các hóa chất tương ứng cần để xa nhau (xem Hình
2.6). Tô màu cho các đỉnh bằng các chữ cái Hy Lạp (, ,, ). Khi đó số màu sẽ
tương ứng với số nơi cần để hóa chất. Với ví dụ này do cần ít nhất 4 màu để tô, nên
cần 4 nơi khác nhau để hóa chất trong kho. Chẳng hạn, hóa chất a và e có thể để ở
nơi có màu α, các hóa chất b, c và d để ở nơi có màu tương ứng là β, γ và δ.
Ta kết thúc vấn đề tô màu các đỉnh bằng Định lý Minty nêu một tính chất đặc
trưng của đồ thị k
–
sắc tính. Trong đồ thị G cho trước, ta chọn một hướng tùy ý trên
mỗi cạnh. Nếu là một chu trình thì ta gọi t
1
( ) là số cạnh hướng theo cùng một
chiều của, t
2
( ) là số cạnh hướng theo chiều ngược lại, và giả thiêt t
1
( ) ≥ t
2
( ).
Định lý 2.6. (G. J. Minty, 1962) Một đồ thị là k
–
sắc tính khi và chỉ khi có thể
chọn hướng trên mỗi cạnh của nó sao cho trên mọi chu trình sơ cấp (chu trình
không đi qua đỉnh nào hai lần trở lên) đều có t
1
( ) ≤ (k
–
1)×t
2
( ).
Chứng minh. Xem [2], tr. 44 – 46. ∎
2.2. TÔ MẦU BẢN ĐỒ
Về lịch sử, bài toán bốn màu liên quan tới vấn đề tô màu các bản đồ. Cho
trước một bản đồ địa lý gồm một số nước, câu hỏi đặt ra là: cần dùng ít nhất bao
nhiêu màu để có thể tô cho mỗi nước một màu, sao cho hai nước có đường biên
giới chung phải có màu khác nhau. Dạng gần gũi nhất với định lý bốn màu là mệnh
đề nói rằng có thể tô mọi bản đồ địa lý chỉ bằng bốn màu. Chẳng hạn, Hình 2.7 vẽ
một bản đồ được tô bằng bốn màu.
21
Hình 2.7. Bản đồ tô bằng 4 màu
Hình 2.8. Cầu trong bản đồ Hình 2.9. Đỉnh bậc 2
Để chính xác hóa mệnh đề này, ta cần giải thích rõ thế nào là một bản đồ. Do
hai màu ở mỗi phía của một cạnh phải khác nhau, nên ta cần loại trừ những bản đồ
có chứa cầu nối (xem Hình 2.8). Ta cũng cần loại trừ các đỉnh bậc 2, vì chúng có
thể dễ dàng bị loại bỏ (xem Hình 2.9). Để bao quát được các trường hợp này và các
trường hợp tương tự, ta quan niệm bản đồ là một đồ thị phẳng 3
–
liên thông, nghĩa
là phải bỏ đi ít nhất 3 đỉnh mới có thể làm đồ thị mất liên thông. Như vậy bản đồ
không có “tập cắt” (tập cạnh bó đi thì đồ thị sẽ mất liên thông) gồm 1 hoặc 2 cạnh,
và nói riêng không có đỉnh bậc 1 hoặc 2. Vì vậy như ta sẽ thấy, việc loại bỏ cầu nối
ở đây tương ứng với việc loại bỏ các khuyên (cạnh nối một đỉnh với chính nó).
Ta nói một bản đồ là k
–
sắc tính diện nếu có thể tô các nước (diện) bằng k
màu sao cho hai nước có đường biên giới (cạnh) chung được tô bằng hai màu khác
nhau. Để tránh nhầm lẫn, ta dùng k
–
sắc tính đỉnh để chỉ k
–
sắc tính theo nghĩa tô
các đỉnh. Chẳng hạn, bản đồ ở Hình 2.10 là 3
–
sắc tính diện và 4
–
sắc tính đỉnh.
Hình 2.10. Tô đỉnh và tô diện
Hình 2.11. Minh họa Định lý 2.7
Định lý bốn màu đối với bản đồ nói rằng mọi bản đồ là 4
–
sắc tính diện. Hệ
quả 2.1 sẽ cho thấy hai dạng của định lý bốn màu là tương đương. Trước hết, ta hãy
tìm điều kiện để có thể tô bản đồ bằng 2 màu. Các điều kiện này khá đơn giản.
Định lý 2.7. Bản đồ G là 2
–
sắc tính diện khi và chỉ khi mọi đỉnh của G có bậc
chẵn.
22
Chứng minh. ⇒ Với mỗi đỉnh v của G, số diện xung quanh v phải là số chẵn,
bởi vì chúng được tô bằng 2 màu. Từ đó suy ra mọi đỉnh của G có bậc chẵn.
⇐ Nếu mọi đỉnh của G có bậc chẵn thì ta sẽ tô các diện của G bằng 2 màu như
sau: Chọn diện bất kỳ F và tô nó bằng màu đỏ. Vẽ một đường cong từ điểm x trong
F tới điểm y trong diện khác F’ và không đi qua đỉnh nào của G. Nếu đường cong
đó đi qua một số chẵn cạnh thì tô màu đỏ cho diện chứa y. Nếu trái lại, tô màu xanh.
(xem Hình 2.11). Việc tô màu này được hoàn toàn xác định, vì có thể lấy một chu
trình gồm hai đường như thế và chứng minh rằng chu trình đi qua một số chẵn cạnh
của G, nhờ dựa trên sự kiện là mỗi đỉnh có một số chẵn cạnh liên thuộc nó. ∎
Một chứng minh đơn giản hơn của Định lý 2.7 dựa trên việc chuyển về bài
toán tô màu các đỉnh của đồ thị đối ngẫu. Cho đồ thị phẳng G, đồ thị đối ngẫu (dual
graph) G* của G được xây dựng như sau: trong mỗi diện f của G, chọn một điểm
v*, các điểm này là các đỉnh của G*; với mỗi cạnh e của G, ta vẽ một cạnh e*, cắt e
(không cắt các cạnh khác của G) và nối hai đỉnh thuộc hai diện có chung cạnh e,
các cạnh như thế tạo nên tập cạnh của G* (xem Hình 2.12),
Định lý 2.8. Cho G là một đồ thị phẳng, không có khuyên và G* là đồ thị đối
ngẫu của G. Khi đó, G là k
–
sắc tính đỉnh khi và chỉ khi G* là k
–
sắc tính diện.
Chứng minh. ⇒ Ta có thể giả thiết G là một đơn đồ thị liên thông, do đó G*
là một bản đồ. Nếu G là k
–
sắc tính đỉnh thì ta có thể dùng k màu để tô các diện của
G* sao cho mỗi diện thừa hưởng màu của đỉnh duy nhất nằm trong diện đó (xem
Hình 2.12). Hai diện kề nhau trong G* có màu khác nhau, bởi vì các đỉnh của G
nằm trong hai diện này là kề nhau trong G, nên chúng có màu khác nhau. Vì vậy
G* là k-
sắc tính diện.
Hình 2.12. Đồ thị đối ngẫu G*: tô đỉnh của G tương đương tô diện của G*
23
⇐ Bây giờ giả sử rằng G* là k
–
sắc tính diện. Khi đó dùng k màu ta có thể tô
các đỉnh của G sao cho mỗi đỉnh thừa hưởng màu của diện chứa nó. Bằng lập luận
tương tự như trên có thể thấy rằng không có hai đỉnh kề nhau nào trong G lại có
màu như nhau. Vì vậy G là k
–
sắc tính đỉnh.
∎
Từ đó suy ra có thể phát biểu dạng đối ngẫu cho định lý bất kỳ về tô đỉnh của
một đồ thị phẳng để đưa ra định lý về tô diện của bản đồ và ngược lại. Để làm ví dụ,
ta trở lại Định lý 2.7 và xét cách chứng minh khác của định lý này. Ta nhắc lại
Định lý 2.7. Bản đồ G là 2
–
sắc tính khi và chỉ khi mọi đỉnh của G có bậc
chẵn.
Chứng minh thứ hai. Có thể chỉ ra rằng đối ngẫu của đồ thị phẳng mà mọi
đỉnh có bậc chẵn là một đồ thị phẳng hai phần và ngược lại. Vì vậy ta chỉ cần để ý
rằng một đồ thị phẳng, liên thông và không có khuyên là 2
–
sắc tính đỉnh khi và chỉ
khi nó là một đồ thị hai phần. ∎
Tương tự, ta có thể chứng minh hai dạng của định lý bốn màu là tương đương.
Hệ quả 2.1. Định lý bốn màu đối với các bản đồ tương đương với định lý bốn
màu đối với các đồ thị phẳng.
Chứng minh. ⇒ Ta có thể giả thiêt G là một đơn đồ thị phẳng liên thông. Khi
đó, đồ thị đối ngẫu G* là một bản đồ. Theo Định lý 2.8, nếu G* là 4-sắc tính diện
thì G là 4
–
sắc tính đỉnh.
⇐ Ngược lại, giả sử G là một bản đồ và G* là đồ thị đối ngẫu của G. Khi đó,
G* là một đơn đồ thị phẳng và vì vậy theo định lý 2.8, nếu G* là 4
–
sắc tính đỉnh
thì G là 4
–
sắc tính diện. ∎
Cũng có thể sử dụng tính đối ngẫu để chứng minh định lý sau đây.
Định lý 2.9. Giả sử G là một bản đồ lập phương. Khi đó, G là 3
–
sắc tính diện
khi và chỉ khi mỗi diện được giới hạn bởi một số chẵn cạnh.
Chứng minh. ⇒ Cho một diện bất kỳ F của G, các diện của G xung quanh F
phải luân phiên đổi màu. Như vậy phải có một số chẵn diện quanh F, và vì vậy mỗi
diện được giới hạn bởi một số chẵn cạnh (xem Hình 2.13).
LUẬN VĂN THẠC SĨ TOÁN HỌCThái Nguyên – năm ngoái ĐẠI HỌC THÁI NGUYÊNTRƯỜNG ĐẠI HỌC KHOA HỌCVŨHOÀNGLINHBÀITOÁNTÔMÀUĐỒ THỊ VÀ ỨNG DỤNGChuyên ngành : Toán ứng dụngMã số : 60 46 01 12LU ẬN VĂN THẠC SĨ TOÁN HỌCNGƯỜI HƯỚNG DẪN KHOA HỌCGS.TS. Trần Vũ ThiệuThái nguyên – 2015M ỞĐẦUĐồ thị là một cấu trúc toán học rời rạc, gồm có hai yếu tố đỉnh và cạnh, và làmô hình toán học cho nhiều yếu tố kim chỉ nan và thực tiễn phong phú. Bài toán tô màucho những đỉnh ( hay những cạnh ) của một đồ thị là một chủ đề quan trọng và mê hoặc củalý thuyết đồ thị. Bài toán này có những ứng dụng thiết thực trong kinh tế tài chính, kỹ thuậtvà đời sống. Chẳng hạn, ta thường gặp bài toán tô màu map, tô màu cho dây dẫnđiện. Một số yếu tố không tương quan đến tô màu cũng hoàn toàn có thể được giải quyết và xử lý nhờ bàitoán tô màu : sắp xếp kho chứa hóa chất, phong cách thiết kế những bảng vi mạch điện tử, sắp xếplịch hỏi thi, sắp xếp những trạm truyền tin, xác lập những tuyến xe buýt thành phố, v.v Lý thuyết đồ thị sinh ra và tăng trưởng gắn liền với tên tuổi của nhiều nhà toánhọc nổi tiếng : Euler ( Thụy sĩ ), với bài toán về 7 cầu ở thành phố Königsberg, König và Egeváry ( Hungari ), với giải pháp Hungari giải bài toán phân việc. Về yếu tố tô màu đồ thị có nhiều tác dụng triết lý đáng chú ý quan tâm : Định lý Brooks, Minty về tô màu đỉnh ; Định lý König, Vizing, Shannon về tô màu cạnh, định lý 5 màu của Heawood ( 1890 ) và Định lý 4 màu của Appel và Haken ( 1976 ), đã giảiquyết được giả thuyết 4 màu nổi tiếng do Guthrie nêu ra lần đầu năm 1852. ” Bài toán tô màu đồ thị và ứng dụng “. Luận văn này có mục tiêu khám phá và trình diễn những khái niệm cơ bản về đồthị và những dạng đồ thị thường gặp, về bài toán tô màu trên đồ thị ( tô đỉnh, tô cạnhvà tô diện – tô màu map ) và một số ít ứng dụng của những bài toán này. Trình bày cáckết quả kim chỉ nan, những định lý về tô màu trên những loại đồ thị khác nhau và những thuậttoán tô màu đỉnh và cạnh, dựa trên những tác dụng kim chỉ nan đã có. Nội dung luận văn được viết trong hai chương. Chương 1 ” Khái niệm cơ bản về đồ thị ” nhắc lại những khái niệm cơ bản về đồthị : đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chutrình, đồ thị liên thông, không liên thông, những phép toán trên đồ thị. Miêu tả nhiềudạng đồ thị đặc biệt quan trọng : rừng và cây, đồ thị hình sao, đồ thị vòng, đồ thị đường, đồ thịbánh xe, đồ thị vừa đủ, đồ thị hai phần, đồ thị hai phần rất đầy đủ, đồ thị đều ( chínhqui ), đồ thị Petersen, đồ thị Platon, đồ thị phẳng, Chương 2 ” Bài toán tô màu đồ thị ” đề cập tới yếu tố tô màu những đỉnh, cạnh vàdiện của một đồ thị. Trình bày những tác dụng về tô màu đỉnh : định lý Brooks ( 1941 ), định lý Minty ( 1962 ), những định lý tô màu đồ thị phảng, đặc biệt quan trọng định lý bốn màu ( Appel và Haken, 1976 ). Về tô màu map ( tô diện của đồ thị phẳng ) có những địnhlý về map 2 màu, map lập phương 3 màu và định lý bốn màu cho map. Vềtô màu cạnh của đồ thị : trình diễn định lý Vizing ( 1964 ) về số màu tối thiểu cần tô, định lý tô cạnh đồ thị khá đầy đủ, tô cạnh đồ thị hai phần ( Định lý König, 1916 ) vàquan hệ với định lý bốn màu. Cuối chương đề cập tới đa thức màu, cho biết có thểtô đỉnh của đò thị bằng k màu được không, nếu được thì có mấy cách tô. Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn thâm thúy tới GSTS TrầnVũ Thiệu, đã tận tình giúp sức trong suốt quy trình làm luận văn. Tác giả chân thànhcảm ơn những thầy giáo, cô giáo Trường Đại học Khoa học – Đại học Thái Nguyên, Viện Toán hoc – Viện Hàn lâm Khoa học và Công nghệ Nước Ta đã giảng dạy vàtạo mọi điều kiện kèm theo thuận tiện trong quy trình tác giả học tập và điều tra và nghiên cứu. Thái Nguyên 20 tháng 04 năm 2015T ác giảVũ Hoàng LinhChương 1KH ÁI NIỆM CƠ BẢN VỀ ĐỒ THỊChương này trình diễn những kỹ năng và kiến thức cơ sở về kim chỉ nan đồ thị. Mục 1.1 nêu cácđịnh nghĩa, khái niệm dùng trong triết lý đồ thị và những phép toán trên đồ thị. Mục1. 2 diễn đạt những dạng đồ thị thường gặp. Trong chương dẫn ra nhiều ví dụ minh họa. Nội dung của chương được tìm hiểu thêm hầu hết từ những tài liệu [ 2 ], [ 3 ], [ 4 ] và [ 5 ]. 1.1. ĐỊNH NGHĨA VÀ KÝ HIỆU1. 1.1. Khái niệm đồ thịTrong thực tiễn ta thường gặp những sơ đồ giao thông vận tải ( Hình 1.1 ) hay sơ đồ mạchđiện ( Hình 1.2 ). Các sơ đồ này được khái quát thành sơ đồ vẽ ở Hình 1.3. Từ đó tađi tới định nghĩa sau. Hình 1.1. Sơ đồ thành phố Hình 1.2. Sơ đồ mạch điện Hình 1.3. Đồ thị đại diệnĐồ thị ( graph ) là một tập hợp hữu hạn và khác rỗng những điểm, gọi là những đỉnh ( vertex ) hay nút ( node ), và một tập hợp những đường ( thẳng hay cong ) nối tiếp một sốcặp điểm này, gọi là những cạnh ( edge ) của đồ thị ( Số cạnh hoàn toàn có thể bằng 0 ). Mỗi đỉnh của đồ thị thường được ký hiệu bằng một vần âm ( a, b, c, hay A, B, C, ) hoặc chữ số ( 1, 2, 3, ). Cạnh tiếp nối đỉnh v với đỉnh w được ký hiệu là ( v, w ) hay đơn thuần là vw ( v và w hoàn toàn có thể là những chữ số ). Một cạnh có dạng ( a, a ), nối đỉnh a với chính nó, gọi là một khuyên ( loop ). Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ VV thì để cho gọn, ta viếtG = ( V, E ). Ta cũng dùng ký hiệu V ( G ) để chỉ tập đỉnh và E ( G ) để chỉ tập cạnh củađồ thị G. Ký hiệu n = | V ( G ) | là số đỉnh và m = | E ( G ) | là số cạnh của đồ thị G.Để dễ tưởng tượng, mỗi đồ thị thường được màn biểu diễn bởi một hình vẽ trên mặtphẳng. Chẳng hạn, Hình 1.3 trình diễn một đồ thị có 5 đỉnh : P., Q., R, S, T và 8 cạnh ( mỗi cạnh là một đoạn thẳng nối hai đỉnh ). Chú ý rằng điểm cắt nhau của hai cạnhPS và QT trong hình vẽ không phải là một đỉnh của đồ thị. Đỉnh v gọi là kề ( adjacent ) đỉnh w nếu có một cạnh của đồ thị nối v với w. Nếu ký hiệu cạnh này là e thì ta viết e = ( v, w ) và nói cạnh e liên thuộc ( incident ) v, w hay v, w là hai đầu mút của e. Cạnh e và e ‘ gọi là kề nhau nếu e, e ‘ có chung đỉnh. Hai cạnh e và e ‘ cùng nối một cặp đỉnh gọi là cạnh kép ( multiple edge ). Đồ thịkhông có cạnh kép gọi là một đơn đồ thị ( simple graph ). Trái lại, gọi là một đa đồthị. Hình 1.4 và 1.5 minh họa cạnh kép và khuyên trong đa đồ thị. Hình 1.4. Cạnh kép và đa đồ thị Hình 1.5. Khuyên trong đa đồ thịMột cạnh của đồ thị gọi là cạnh có hướng ( directed edge ) nếu có qui định rõmột đầu mút của cạnh là đỉnh đầu, mút kia là đỉnh cuối. Cạnh có hướng còn đượcgọi là một cung. Một đồ thị gồm toàn những cạnh gọi là đồ thị vô hướng ( undirected graph ), đồ thịgồm toàn những cung gọi là đồ thị có hướng ( digraph ). Một đồ thị vừa có cạnh vừa cócung gọi là đồ thị hỗn hợp ( mixed graph ). Bằng cách thay một cạnh bởi hai cung cóhướng ngược chiều nhau, ta hoàn toàn có thể qui mọi đồ thị về đồ thị có hướng. Hình 1.6 môtả một đồ thị có hướng. Hình 1.6. Đồ thị có hướng Hình 1.7. Đồ thị không liên thôngBậc ( degree ) của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc nó, kýhiệu là ( v ). Đỉnh có bậc 0 gọi là đỉnh cô lập ( isolated vertex ), đỉnh có bậc 1 gọi làđỉnh treo ( end-vertex ), Tương tự, trong đồ thị có hướng ta gọi bậc ra ( bậc vào ) củađỉnh v là số cung đi khỏi v ( số cung đi tới v ), ký hiệu tương ứng là ( v ) và ( v ). Qui ước : khuyên tại một đỉnh được tính 2 lần. Ví dụ trong đồ thị vẽ ở Hình 1.7 tacó ( P. ) = ( S ) = ( U ) = ( V ) = 2 ; ( Q. ) = ( R ) = 3 và ( T ) = 4 ( có khuyên ở T ). Dễ dàng chứng tỏ những đặc thù sau đây về bậc của đỉnh trong đồ thị : a ) Trong một đồ thị vô hướng, tổng số bậc của mọi đỉnh bằng hai lần số cạnhcủa đồ thị và số đỉnh có bậc lẻ khi nào cũng là một số chẵn. b ) Trong một đồ thị có hướng, tổng những bậc vào của mọi đỉnh bằng tổng cácbậc ra của mọi đỉnh và bằng tổng số cung trong đồ thị. Nhiều đặc thù của đồ thị có hướng không nhờ vào vào hướng những cungtrong đồ thị. Vì thế, khi bỏ lỡ hướng trên những cung ( đổi cung thành cạnh ) ta sẽnhận được một đồ thị vô hướng, gọi là đồ thị nền của đồ thị có hướng đã cho. 1.1.2. Phép toán trên đồ thịSau đây ta tập trung chuyên sâu hầu hết xét những đồ thị vô hướng và một số ít phép toán. • Đồ thị con ( subgraph ) của một đồ thị G là đồ thị nhận được từ G bằng cáchbỏ đi một số ít đỉnh và 1 số ít cạnh của nó. Nói đúng mực, H = ( V ( H ), E ( H ) ) là mộtđồ thị con của G nếu V ( H ) V ( G ) và E ( H ) E ( G ). Ta cũng nói G chứa H. H gọilà đồ thị con cảm sinh ( induced subgraph ) của G nếu H là một đồ thị con của G vàE ( H ) = { ( x, y ) ∈ E ( G ) : x, y ∈ V ( H ) }. Ở đây H là đồ thị con của G sinh bởi V ( H ). Vì thế ta còn viết H = G [ V ( H ) ]. Đồ thị con H của G gọi là đồ thị con bao trùm nếuV ( H ) = V ( G ), tức tập đỉnh của H và của G trùng nhau. • Với v ∈ V ( G ), ký hiệu G – v là đồ thị con của G cảm sinh bởi V ( G ) \ { v }, tức đồ thị nhận được từ G bằng cách bỏ đỉnh v và những cạnh liên thuộc v. • Với e ∈ E ( G ), ta định nghĩa G – e : = ( V ( G ), E ( G ) \ { e } ), tức đồ thị nhậnđược từ G bằng cách xóa cạnh e ( không xóa hai đầu mút của e ). Ta cũng định nghĩaG \ e là đồ thị nhận được bằng cách co cạnh e thành một điểm duy nhất. Hình 1.8 minh họa những đồ thị G, G – e và G \ e. Hình 1.8. Đồ thị G, cạnh e và những đồ thị G e và G \ e tương ứng1. 1.3. Đồ thị đẳng cấuHai đồ thị Gvà Ggọi là đẳng cấu ( isomorphic ) nếu chúng có số đỉnh và sốcạnh như nhau và có phép tương ứng mộtmột giữa tập đỉnh của Gvà Gsao chohai đỉnh được nối với nhau bởi một cạnh trong đồ thị này khi và chỉ khi hai đỉnhtương ứng trong đồ thị kia cũng được nối với nhau bởi một cạnh và ngược lại. Hình1. 9 vẽ những đồ thị đẳng cấu với đồ thị vẽ ở Hình 1.3. Các cạnh của hai đồ thị ở Hình1. 9 chỉ gặp nhau ơ đinh. Các đồ thị đẳng cấu được xem là tương tự ( là một ). Hình 1.9. Các đồ thị đẳng cấu với đồ thị ở Hình 1.31.1. 4. Đồ thị liên thôngCó thể ghép hai đồ thị để lập lên một đồ thị lớn hơn. Cho G = ( V ( G ), E ( G ) ), = ( V ( G ), E ( G ) ) với V ( G ∩ V ( G ) = ∅. Khi đó, hợp ( union ) G ∪ Glà đồ thịcó tập đỉnh là V ( G ) ∪ V ( G ) và tập cạnh là E ( G ) ∪ E ( G ) ( Hình 1.10 ). Hình 1.10. Đồ thị G, Gvà hợp G ∪ GHình 1.11. Đồ thị không liên thôngHầu hết những đồ thị thường gặp là đồ thị ghép. Một đồ thị được gọi là liên thông ( connected graph ) nếu nó không trình diễn được dưới dạng hợp của hai hay nhiềuđồ thị. Trái lại, đồ thị gọi là không liên thông ( disconnected graph ). Rõ ràng là bấtcứ một đồ thị không liên thông G nào cũng màn biểu diễn được dưới dạng hợp của cácđồ thị liên thông, mỗi đồ thị liên thông gọi là một thành phần liên thông của G.Chẳng hạn, một đồ thị gồm ba thành phần liên thông được vẽ ở Hình 1.11. Hình 1.12. Các kiểu đồ thị liên thông không quá 5 đỉnhKhi cần chứng tỏ một Kết luận nào đó cho những đồ thị nói chung, ta thườngchứng minh tác dụng tương ứng cho những đồ thị liên thông, sau đó vận dụng kết quảthu được cho từng thành phần liên thông riêng không liên quan gì đến nhau của đồ thị. Một bảng gồm tất cảcác đồ thị liên thông ( không ghi tên đỉnh ) có tối đa 5 đỉnh được vẽ ở Hình 1.12.1. 1.5. Đường và quy trình trong đồ thị vô hướngĐường ( path ) P. từ đỉnh v tới đỉnh w là một dãy liên tục những cạnh có dạng : ( a, a ), ( a, a ), , ( ak-1, a ) với ( ai-1, a ) E ( G ), a = v, a = w và k 1, trong đó những đỉnh a, a, , ađều khác nhau. Để đơn thuần, nhiều lúc ta viết P. = { a, , a } và nói đó là đường nối đỉnh v và đỉnh w. Đỉnh v gọi là đỉnh đầu, đỉnh wgọi là đỉnh cuối của đường P. Một đường nối một đỉnh với chính nó ( đỉnh đầu trùngvới đỉnh cuối ) gọi là một quy trình ( cycle ). Độ dài ( length ) của đường ( quy trình ) làsố cạnh của đường ( quy trình ) đó. Ví dụ với đồ thị vẽ ở Hình 1.9 một đường nối đỉnh P. và đỉnh R là ( P., T ), ( T, Q. ), ( Q., R ) hay đơn thuần là P., T, Q., R. Hai đường khác từ P. tới R là P., T, S, R và P., Q., R hay P., S, R. Đồ thị này có những quy trình sau : ( P., Q. ), ( Q., R ), ( R, S ), ( S, T ), ( T, P. ) ; ( Q., S ), ( S, T ), ( T, Q. ), v.v 1.1.6. Biểu diễn đồ thị bằng ma trậnMặc dù cách màn biểu diễn đồ thị bằng hình vẽ gồm những điểm được nối với nhaubởi những cạnh khá thuận tiện, tuy nhiên cách này không còn tương thích nếu ta muốn lưu giữmột đồ thị cỡ lớn trên máy tính. Có cách lưu giữ một đơn đồ thị là liệt kê những đỉnhkề với mỗi đỉnh của đồ thị. Ví dụ cho cách trình diễn này được chỉ ra ở Hình 1.13. Hình 1.13. Liệt kê những đỉnh kề Hình 1.14. Đồ thị rỗng NMột cách trình diễn có ích khác là dùng những ma trận. u : v, yv : u, w, yw : v, x, yx w, yy : u, v, w, x • Ma trận kề : Nếu G là một đồ thị với những đỉnh được đánh số 1, 2, …, n, thìma trận kề ( adjacency matrrix ) cuả G là ma trận vuông A cấp n, thành phần ở hàng icột j của A bằng số cạnh nối đỉnh i và đỉnh j của đồ thị. • Ma trận liên thuộc : Nếu những cạnh của đồ thị cũng được đánh số 1, 2, …, m, thì ma trận liên thuộc ( incidence matrrix ) của G là ma trận chữ nhật M cấp n × m, thành phần ở hàng i cột j của M bằng 1 nếu đỉnh i kề cạnh j và bằng 0 nếu trái lại. Hình 1.15 vẽ đồ thị G cùng với ma trận kề và ma trận liên thuộc của nó. Hình 1.15. Ma trận kề và ma trận liên thuộc1. 2. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTMục này trình diễn 1 số ít dạng đồ thị đặc biệt quan trọng, đáng chú ý quan tâm và hay được dùngtrong triết lý đồ thị và trong những ứng dụng. 1.2.1 Đồ thị rỗng ( Đồ thị không ) Một đồ thị có đỉnh, nhưng không có cạnh nào ( tập cạnh rỗng ) gọi là một đồ thịrồng ( empty graph ) hay đồ thị không ( null graph ). Ký hiệu đồ thị rỗng n đỉnh là NMỗi đỉnh của một đồ thị rỗng là một đỉnh cô lập ( đỉnh bậc 0 ) và những đồ thị rỗng rấtít được quan tâm. Một đồ thị rỗng Nđược vẽ ở Hình 1.14.1. 2.2. Rừng và câyCó thể hiểu đồ thị liên thông theo nghĩa tương tự như sau. Một đồ thị vôhướng gọi là liên thông nếu có đường đi nối hai đỉnh bất kể của đồ thị. Trái lại, đồthị gọi là không liên thông. Đồ thị không liên thông sẽ bị tách thành 1 số ít đồ thịcon liên thông, đôi một không có đỉnh chung. Mỗi đồ thị con liên thông như thế làmột thành phần liên thông. Cạnh e gọi là một cầu ( bridge ) nếu xóa e ( không xóa10đỉnh ) thì đồ thị còn lại sẽ tăng thêm một thành phần liên thông, mỗi thành phầngồm tối thiểu một cạnh. Ví dụ, những đồ thị vẽ ở Hình 1.9 là liên thông, còn đồ thị vẽ ởHình 1.11 là không liên thông ( gồm 3 thành phần liên thông ). Một đồ thị vô hướng không có quy trình gọi là một rừng ( forest ). Một rừngliên thông gọi là một cây ( tree ), tức cây là một đồ thị liên thông và không có chutrình. Ví dụ phả hệ của một họ tộc là một cây ( cây phả hệ ). Rừng hoàn toàn có thể gồm nhiềuthành phần liên thông khác nhau, mỗi thành phần liên thông là một cây. Như vậy, rừng gồm nhiều cây. Đỉnh có bậc 1 trong cây gọi là một lá ( leaf ). Đồ thị hình sao làmột cây có duy nhất một đỉnh không phải là lá. Một đồ thị con, không chứa quy trình của đồ thị G gọi là một cây của G. Mộtđồ thị con bao trùm của G mà là một cây được gọi là một cây bao chùm ( spanningtree ) của G. Một số đặc thù đặc trưng của cây : cây n đỉnh có đúng n1 cạnh, trongmột cây, khi nào cũng có một đường đi duy nhất nối một cặp đỉnh bất kể của cây. Các ví dụ về rừng và cây được vẽ ở Hình 1.16. Hình 1.16. Ví dụ về rừng và cây1. 2.3. Đồ thị đầy đủMột đơn đồ thị trong đó mọi cặp đỉnh ( khác nhau ) đều kề nhau, gọi là một đồthị rất đầy đủ ( completed graph ). Đồ thị vừa đủ n đỉnh ký hiệu là K. Số cạnh của Kbằng n ( n1 ) / 2. Đồ thị Kvà Kđược vẽ ở Hình 1.17. Hình 1.17. Đồ thị vừa đủ Kvà K111. 2.4. Đồ thị vòng, đồ thị đường và đồ thị bánh xeMột đồ thị liên thông và mọi đỉnh bậc 2 gọi là một đồ thị vòng ( cycle graph ). Ký hiệu đồ thị vòng n đỉnh là C. Đồ thị nhận được từ Cbằng cách bỏ di một cạnhbất kỳ gọi là một đồ thị đường ( path graph ) n đỉnh, ký hiệu là P. Đồ thị nhận đượctừ Cn – 1 bằng cách thêm vào một đỉnh v và nối mỗi đỉnh của Cn – 1 với v bởi mộtcạnh, gọi là một đồ thị bánh xe ( wheel ) n đỉnh, ký hiệu là WCác đồ thị C, Pvà Wđược vẽ ở Hình 1.18. Hình 1.18. Đồ thị vòng C, đồ thị đường Pvà đồ thị bánh xe W1. 2.5. Đồ thị đều ( đồ thị chính qui ) Một đồ thị mà mọi đỉnh có bậc bằng nhau gọi là một đồ thị đều hay đồ thịchính qui ( regular graph ). Nếu mọi đỉnh có bậc r thì đồ thị được gọi là đồ thị đều ( chính qui ) bậc r hoặc rchính qui. Có tầm quan trọng đặc biệt quan trọng là những đồ thị bậc 3 ( cubic graph ), tức những đồ thị đều ( chính qui ) bậc 3. Một ví dụ nổi bật về đồ thịbậc 3 là đồ thị Petersen ( Petersen graph ), đồ thị này được vẽ ở Hình 1.19. Chú ýrằng đồ thị rỗng Nlà đồ thị chính qui bậc 0, đồ thị vòng Clà đồ thị chính qui bậc2 và đồ thị khá đầy đủ Klà đồ thị chính qui bậc n1. Hình 1.19. Đồ thị Petersen ( chính qui bậc 3 ) 1.2.6. Đồ thị PlatonTrong những đồ thị chính qui, đáng chú ý quan tâm là những đồ thị Platon ( Platonic graph ). Đồ thị Platon được hình thành từ những đỉnh và những cạnh của 5 khối đa diện đều : hình12tứ diện, hình tám mặt, hình lập phương, khối hai mươi mặt và khối mười hai mặt ( Hình 1.20 ). Hình 1.20. Đồ thị Platon1. 2.7. Đồ thị hai phầnNếu tập đỉnh của đồ thị G hoàn toàn có thể chia tách ra thành hai tập rời nhau A và B saocho mỗi cạnh của G nối một đỉnh thuộc A với một đỉnh thuộc B, thì G được gọi làmột đồ thị hai phần ( bipartite graph ) ( Hình 1.21 ). Nói một cách khác, đồ thị haiphần là đồ thị mà hoàn toàn có thể tô những đỉnh của nó bằng hai màu đen và trắng sao cho mỗicạnh nối một đỉnh đen ( trong A ) và một đỉnh trắng ( trong B ). Có thể chứng tỏ rằng đơn đồ thị G là đồ thị hai phần khi và chỉ khi mọi chutrình trong G đều có độ dài ( số cạnh ) chẵn. Đồ thị hai phần không thiếu ( complete bipartite graph ) là một đồ thị hai phần màmỗi đỉnh trong A được nối với mỗi đỉnh trong B bằng đúng một cạnh. Ta ký hiệuđồ thị hai phần có r đỉnh đen và s đỉnh trắng là Kr, s. Các đồ thị K1, 3 ; K2, 3, K3, 3 và K4, 3 được vẽ ở Hình 1.22. Dễ dàng kiểm tra lại rằng Kr, scó ( rs ) đỉnh và r × s cạnh. Hình 1.21. Đồ thị hai phần Hình 1.22. Đồ thị hai phần không thiếu : K1, 3, K2, 3, K3, 3, K4, 3T ứ diện Hình tám mặt Hình lập phương Khối 20 mặt Khối 12 mặt131. 2.8. Đồ thị lập phươngTrong những đồ thị hai phần đều ( mọi đỉnh có cùng bậc ), người ta đặc biệt quan trọng quantâm tới những đồ thị lập phương ( cubes ). Ký hiệu Qlà klập phương ( kcube ), đó làmột đồ thị đều, bậc k ( kchính qui ) mà những đỉnh của nó hoàn toàn có thể đặt tương ứng vớidãy số ( a, a, …, a ), trong đó mọi a = 0 hoặc 1, và những cạnh của đồ thị nối liềnhai đỉnh tương ứng với hai dãy số chỉ khác nhau ở một vị trí. Để ý rằng Qlà đồ thịhai phần đều, bậc 3 ( Hình 1.23 ). Có thể kiểm tra lại rằng Qcó 2 đỉnh và k × 2 k – 1 cạnh, và là đồ thị kchính qui ( đồ thị đều, bậc k ). Hình 1.23. Đồ thị hai phần đều, bậc 3 : QHình 1.24. Phần bù của đơn đồ thị G1. 2.9. Phần bù của đơn đồ thịNếu G là một đơn đồ thị với tập đỉnh V ( G ), thì phần bù ( complement ) củaG là một đơn đồ thị, với cùng tập đỉnh V ( G ) và hai đỉnh kề nhau trongkhi vàchỉ khi chúng không kề nhau trong G. Chẳng hạn, Hình 1.24 vẽ đồ thị G và phần bùcủa nó. Có thể thấy rằng phần bù của một đồ thị vừa đủ là một đồ thị rỗng vàphần bù của một đồ thị hai phần vừa đủ là hợp của hai đồ thị rất đầy đủ. 1.2.10. Đồ thị phẳngMột đồ thị ( hay đa đồ thị ) G gọi là đồ thị phẳng ( planar graph ) khi nào nó cóthể màn biểu diễn được trên một mặt phẳng sao cho ứng với mỗi đỉnh là một điểm vàứng với mỗi cạnh là một đoạn thẳng hay cong và bất kể hai cạnh nào cũng khôngcó điểm chung khác với những đầu mút của chúng. Chẳng hạn, đồ thị vẽ ở Hình 1.4 vàHịnh 1.5 là những ( đa ) đồ thị phẳng. Khi đó, mỗi miền mặt phẳng hạn định bởi những cạnh và không chứa đỉnh hoặccạnh ở bên trong của nó, gọi là một diện ( face ) của đồ thị phẳng G. Biên ( boundary ) của một diện là quy trình tạo nên bởi những cạnh hạn định nó. Hai diện gọi là kề nhau14 ( adjacent ) khi nào biên của chúng có tối thiểu một cạnh chung ( hai diện chỉ có đỉnhchung thì không xem là kề ). Rõ ràng mỗi đồ thị phẳng liên thông đều có một diệnvô hạn duy nhất, còn mọi diện khác đều là diện hữu hạn. Ví dụ. Một map địa lý không có hòn đảo ( không có khuyên ) là một đồ thị phẳng : mỗi đỉnh là điểm chung của tối thiểu ba đường biên giới ( bậc của đỉnh ≥ 3 ), mỗi cạnhlà một đoạn đường biên giới nối hai đỉnh và mỗi diện là một nước. Đồ thị phẳng có những đặc thù đáng chú ý quan tâm sau : • Trong một đồ thị phẳng liên thông, giữa số đỉnh n, số cạnh m và số diên d cóhệ thức : n – m + d = 2 ( công thức Euler ). • Trong một đơn đồ thị phẳng phải có tối thiểu một đỉnh với bậc ≤ 5. • Đồ thị K ( Hình 1.17 ) và K3, 3 ( Hình 1.22 ) là hai đồ thị không phẳng. • Một đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con nào thuộc kiểuhay K3, 3 ( Định lý Kuratowski ). Ví dụ. Hình lập phương vẽ ở Hình 1.25 a là một đồ thị phẳng. Biểu diễn phẳngcủa đồ thị được vẽ ở Hình 1.25 b. Đồ thị này có số đỉnh n = 8, số cạnh m = 12 và sốdiện d = 6 ( 5 diện hữu hạn và 1 diện vô hạn ). Công thức Ơle đương nhiên đúng đốivới đồ thị phẳng này ( 8 – 12 + 6 = 2 ). Hình 1.25. a ) Hình lập phương ; b ) Biểu diễn phẳngTóm lại, chương này đã đề cập tới những khái niệm cơ bản về đồ thị : đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và quy trình, đồ thị liênthông và không liên thông. Trình bày những phép toán thường dùng trên đồ thị ( thêm, bớt đỉnh hoặc cạnh ). Miêu tả nhiều dạng đồ thị đặc biệt quan trọng : rừng và cây, đồ thị hìnhsao, đồ thị vòng, đồ thị bánh xe, đồ thị khá đầy đủ, đồ thị hai phần, đồ thị hai phần đầyđủ, đồ thị đều ( chính qui ), đồ thị Petersen, đồ thị Platon, đồ thị phẳng, 15C hương 2B ÀI TOÁN TÔ MÀU ĐỒ THỊChương này đề cập tới bài toán tô màu đồ thị và trình làng định lý bốn màunổi tiếng. Mục 2.1 xét bài toán tô màu những đỉnh của đồ thị. Mục 2.2 xét bài toán tômàu map. Mục 2.3 xét bài toán tô màu những cạnh của đồ thị. Cuối chương, ở mục2. 4, đề cập tới đa thức màu và yếu tố có bao nhiêu cách tô màu hoàn toàn có thể. Nội dungcủa chương được tìm hiểu thêm hầu hết từ những tài liệu [ 2 ], [ 3 ], [ 5 ] và [ 6 ]. 2.1. TÔ MẦU CÁC ĐỈNH CỦA ĐỒ THỊNhiều yếu tố kỹ thuật tân tiến ( ví dụ điển hình, tin học và tự động hóa ) đưa tớiviệc tô màu những đỉnh của một đồ thị G, sao cho hai đỉnh kề nhau có những màu khácnhau. Để cho gọn, ta sẽ nói một cách tô như thế là một cách tô đúng. Đương nhiênnếu G có n đỉnh thì chỉ việc dùng n màu khác nhau là hoàn toàn có thể tô đúng được rồi. Nhưng nhiều khi không cần tới n màu mà chỉ cần 1 số ít màu ít hơn cũng tô đúngđược. Chẳng hạn, nếu đồ thị G không có quy trình thì chỉ cần 2 màu là đủ tô đúngtrong mọi trường hợp. Do đó yếu tố đặt ra là : số màu tối thiểu thiết yếu để tô đúngcác đỉnh của một đồ thị cho trước là bao nhiêu ? Ta nói một đồ thị là ksắc tính ( kcolourable ) nếu nó hoàn toàn có thể tô đúng bằng kmàu. Số k nhỏ nhất mà G còn là ksắc tính, nghĩa là số màu tối thiểu thiết yếu đểtô đúng được những đỉnh của G, gọi là số sắc tính hay sắc số ( chromatic number ) củađồ thị G và viết ( G ) = k. Hình 2.1. Sắc số của đồ thị : ( G ) = 416C hẳng hạn, đồ thị G vẽ ở Hình 2.1 có ( G ) = 4. Các màu được biểu lộ bằngchữ cái Hy lạp (, , và ). Vì vậy, G là ksắc tính với mọi k ≥ 4. Vấn đề tìm số sắc tính của một đồ thị thường rất phức tạp ( trừ khi G không cóchu trình ), và cho tới nay nó vẫn chưa có một lời giải thỏa đáng. Trong mục này sẽtrình bày 1 số ít tác dụng đáng quan tâm về những đồ thị ksắc tính. Sau đây ta giả thiết G là đơn đồ thị vô hướng, liên thông và không có khuyên. Rõ ràng, sắc số của đồ thị rất đầy đủ n đỉnh bằng n : χ ( K ) = n. Vì vậy có những đồthị với sắc số lớn tùy ý. Theo chiều ngược lại, χ ( G ) = 1 khi và chỉ khi G là đồ thịkhông ( null graph ), tức là đồ thị G có đỉnh nhưng không có cạnh, và χ ( G ) = 2 khivà chỉ khi G là một đồ thị hai phần khác không ( non-null bipartite graph ). Chú ýrằng một cây bất kể, cũng như mọi chu trình độ dài chẵn bất kể là 2 sắc tính. Ta hoàn toàn có thể thuận tiện lấy ví dụ về đồ thị là 3 – sắc tính. Chẳng hạn, những chu trìnhđộ dài lẻ hay những đồ thị bánh xe với một số lẻ đỉnh và đồ thị Petersen là 3 sắc tính. Các đồ thị bánh xe với một số ít chẵn đỉnh là 4 sắc tính. Trong [ 1 ] đưa ra một lớp đồthị phẳng 3 sắc tính đáng quan tâm, đó là những đồ thị với n ≥ 6 đỉnh và mọi đỉnh có bậc3 ( Hình 2.2 ). Hình 2.2. Đồ thị phẳng đẳng cấp bậc 3 là 3 sắc tínhTa hoàn toàn có thể nói đôi điều về số sắc tính ( sắc số ) của một đồ thị tuỳ ý : Nếu đồ thịcó n đỉnh thì sắc số của nó không vượt quá n, và nếu đồ thị chứa K ( đồ thị không thiếu rđỉnh ) như một đồ thị con thì sắc số của nó không ít hơn r. Nhìn chung, những kết quảnày không giúp ta biết đúng chuẩn sắc số của một đồ thị. Tuy nhiên, nếu biết bậc củacác đỉnh trong đồ thị thì ta hoàn toàn có thể biết nhiều hơn. Định lý 2.1. Nếu đơn đồ thị G có bậc lớn nhất của đỉnh bằng Δ thì G là ( Δ1 ) sắc tính. 17C hứng minh. Dùng giải pháp quy nạp toán học theo số đỉnh của G. Giảsử G là một đơn đồ thị n đỉnh. Nếu ta xoá một đỉnh bất kể v, cùng với những cạnh liênthuộc nó, thì đồ thị còn lại là một đơn đồ thị ( n1 ) đỉnh và bậc lớn nhất của đỉnhcùng lắm bằng Δ ( xem Hình 2.3 ). Theo giả thuyết quy nạp, đồ thị này là ( Δ1 ) sắc tính. Giữ nguyên màu của những đỉnh trong đồ thị này, ta sẽ tô cho đỉnh v mộtmàu, khác với những màu đã tô cho những đỉnh kề v ( số này nhiều nhất bằng ). Kếtquả là G được tô bằng ( + 1 ) màu, tức G là ( + 1 ) sắc tính. Hình 2.3. Minh họa chứng minh Định lý 2.1 Bằng giải quyết và xử lý tinh xảo hơn, hoàn toàn có thể làm mạnh thêm Định lý 2.1 và đi tới tác dụng sauđây, với tên gọi Định lý Brooks. Chứng minh xem [ 5 ], tr. 86 – 88. Định lý 2.2. ( Brooks, 1941 ) Nếu G là một đơn đồ thị liên thông mà khôngphải là một đồ thị rất đầy đủ và nếu bậc lớn nhất của đỉnh là ≥ 3 thì G làsắc tính. Cả hai định lý trên đều rất hữu dụng, đặc biệt quan trọng khi bậc của những đỉnh giao động nhưnhau. Chẳng hạn theo Định lý 2.1, mỗi đồ thị lập phương ( cubic graph ) là 4 sắctính, và theo Định lý 2.2, mỗi đồ thị lập phương liên thông, khác đồ thị khá đầy đủ Klà 3 sắc tính. Mặt khác, nếu đồ thị có vài đỉnh với bậc lớn thì những định lý này chota rất ít thông tin. Điều này được minh hoạ rõ bởi đồ thị hai phần vừa đủ K1, s. Địnhlý Brooks cho thấy đồ thị này là ssắc tính, nhưng trong thực tiễn chỉ cần dùng 2 màu là cóthể tô đúng những đỉnh của đồ thị loại này, nghĩa là K1, slà 2 sắc tính với mọi s. Không có cách nào hiệu suất cao để thoát khỏi thực trạng này. Tình trạng tồi tệ này sẽ không xảy ra, nếu ta số lượng giới hạn chỉ xét những đồ thị phẳng. Trên thực tiễn, hoàn toàn có thể thuận tiện chứng tỏ hiệu quả khá mạnh nói rằng mọi đơn đồ thịphẳng là 6 sắc tính. Định lý 2.3. Mọi đơn đồ thị phẳng là 6 sắc tính. 18C hứng minh. ( Tương tự như Định lý 2.1, tức là dùng phương pháp quy nạptheo số đỉnh của đồ thị ) Hiển nhiên định lý đúng so với những đơn đồ thị phẳngkhông quá 6 đỉnh. Giả sử G là một đơn đồ thị phẳng n đỉnh, và mọi đơn đồ thịphẳng ( n1 ) đỉnh là 6 sắc tính. Do đồ thị G phẳng nên G chứa một đỉnh v có bậcnhiều nhất là 5. Nếu xoá v và những cạnh liên thuộc v thì đồ thị còn lại có n1 đỉnh, và thế cho nên nó là 6 – sắc tính ( xem Hình 2.4 ). Giữ nguyên màu của những đỉnh trong đồthị này, ta tô cho đỉnh v bằng màu, khác với những màu đã tô cho những đỉnh kề v ( sốnày không quá 5 ). Kết quả là G được tô bằng 6 màu, tức G là 6 sắc tính. ∎ Hình 2.4. Minh họa chứng minh Định lý 2.3 Cũng như Định lý 2.1, hoàn toàn có thể làm mạnh thêm Định lý 2.3 này bằng cách xử lýtinh tế hơn. Kết quả nhận được gọi là Định lý 5 màu ( Five Colour Theorem ). Định lý 2.4. Một đơn đồ thị phẳng khi nào cũng là 5 sắc tính. Chứng minh. Tương tự như định lý 2.3, tuy nhiên những chi tiết cụ thể sẽ phức tạp hơn. Ta chứng minh định lý bằng chiêu thức quy nạp theo số đỉnh. Hiển nhiên định lýđúng so với đơn đồ thị phẳng ít hơn 6 đỉnh. Giả sử G là một đơn đồ thị phẳng nđỉnh, và mọi đơn đồ thị phẳng n1 đỉnh là 5 sắc tính. Do đồ thị G phẳng nên Gchứa một đỉnh v với bậc không quá 5. Cũng như trong chứng minh định lý trước, sau khi xoá đỉnh v và những cạnh liên thuộc v, ta được một đơn đồ thị n1 đỉnh và đồthị này là 5 sắc tính. Mục đích của ta giờ đây là tô đỉnh v bằng một trong 5 màunày, và như vậy sẽ hoàn thành xong việc tô những đỉnh của G bằng 5 màu. Nếu bậc của đỉnh v nhỏ hơn 5 thì v hoàn toàn có thể được tô bằng màu bất kể, chưadùng để tô cho những ( tối đa là 4 ) đỉnh kề v, và như vậy triển khai xong chứng tỏ địnhlý trong trường hợp này. Giả sử bậc của v bằng 5 và 5 đỉnh kề v là v, , v, được19sắp xếp quanh v theo chiều kim đồng hồ đeo tay như vẽ ở Hình 2.5. Nếu những đỉnh v, , vđôi một kề nhau thì G chứa đồ thị không phẳng Knhư một đồ thị con, vô lý ! Vậyphải có tối thiểu 2 trong số những đỉnh v ( ví dụ điển hình, vvà v ) không kề nhau. Bây giờ ta co hai cạnh vvvà vvvề đỉnh v, và nhận được một đồ thị phẳng cón – 2 đỉnh. Theo giả thiết qui nạp, ta hoàn toàn có thể tô đúng nó bằng 5 màu. Sau khi tô đồ thịnày, ta Phục hồi trở lại hai cạnh bắt đầu và tô cho vvà v. bằng màu đã tô cho v, còn v thì tô bằng màu thứ 5 còn lại ( ngoài những màu đã tô cho những đỉnh kề v ). Kếtquả là khi nào ta cũng hoàn toàn có thể tô cho những đỉnh của G bằng 5 màu, nghĩa là G là 5 sắc tính. Một câu hỏi tự nhiên đặt ra là liệu hoàn toàn có thể làm mạnh hơn nữa định lý này đượckhông. Điều này dẫn đến một trong những bài toán nổi tiếng nhất trong toán học, sống sót hơn một thế kỷ, đó là bài toán bốn màu ( Four-Colour Problem ). Theo mộtcách diễn đạt khác, bài toán này đã được đặt ra lần tiên phong vào năm 1852, và cuốicùng được K. Appel và W. Haken xử lý năm 1976. Hình 2.5. Minh họa Định lý 2.4 Hình 2.6. Tìm nơi để hóa chất a – eĐịnh lý 2.5. ( Appel và Haken, 1976 ) Mọi đơn đồ thị phẳng là 4 sắc tính. Chúng minh định lý này được triển khai trong 1 số ít năm và tiêu tốn nhiềuthời gian chạy máy tính, suy cho cùng nó dựa trên việc lan rộng ra phức tạp những ýtưởng trong chứng minh định lý 5 màu. Ứng dụng trong thực tiễn. Ta nêu một ứng dụng đơn thuần của việc tô màu đỉnh. Giảsử một nhà hóa học muốn cất giữ 5 loại hóa chất a, b, c, d và e trong kho. Một sốhóa chất có tương tác mạnh khi tiếp xúc, vì thể chúng cần được để cách xa nhau20trong kho. Dấu * trong bảng sau cho biết những cặp hóa chất không được để gầnnhau. Cần bao nhiêu nơi trong kho để cất giữ hóa chất ? Để vấn đáp thắc mắc này, ta vẽ một đồ thị 5 đỉnh, mỗi đỉnh đại diện thay mặt cho một loạihóa chất, hai đỉnh là kề nhau khi những hóa chất tương ứng cần để xa nhau ( xem Hình2. 6 ). Tô màu cho những đỉnh bằng những vần âm Hy Lạp (, ,, ). Khi đó số màu sẽtương ứng với số nơi cần để hóa chất. Với ví dụ này do cần tối thiểu 4 màu để tô, nêncần 4 nơi khác nhau để hóa chất trong kho. Chẳng hạn, hóa chất a và e hoàn toàn có thể để ởnơi có màu α, những hóa chất b, c và d để ở nơi có màu tương ứng là β, γ và δ. Ta kết thúc yếu tố tô màu những đỉnh bằng Định lý Minty nêu một đặc thù đặctrưng của đồ thị ksắc tính. Trong đồ thị G cho trước, ta chọn một hướng tùy ý trênmỗi cạnh. Nếu là một quy trình thì ta gọi t ( ) là số cạnh hướng theo cùng mộtchiều của, t ( ) là số cạnh hướng theo chiều ngược lại, và giả thiêt t ( ) ≥ t ( ). Định lý 2.6. ( G. J. Minty, 1962 ) Một đồ thị là ksắc tính khi và chỉ khi có thểchọn hướng trên mỗi cạnh của nó sao cho trên mọi quy trình sơ cấp ( chu trìnhkhông đi qua đỉnh nào hai lần trở lên ) đều có t ( ) ≤ ( k1 ) × t ( ). Chứng minh. Xem [ 2 ], tr. 44 – 46. ∎ 2.2. TÔ MẦU BẢN ĐỒVề lịch sử dân tộc, bài toán bốn màu tương quan tới yếu tố tô màu những map. Chotrước một map địa lý gồm một số ít nước, câu hỏi đặt ra là : cần dùng tối thiểu baonhiêu màu để hoàn toàn có thể tô cho mỗi nước một màu, sao cho hai nước có đường biêngiới chung phải có màu khác nhau. Dạng thân thiện nhất với định lý bốn màu là mệnhđề nói rằng hoàn toàn có thể tô mọi map địa lý chỉ bằng bốn màu. Chẳng hạn, Hình 2.7 vẽmột map được tô bằng bốn màu. 21H ình 2.7. Bản đồ tô bằng 4 màuHình 2.8. Cầu trong map Hình 2.9. Đỉnh bậc 2 Để đúng chuẩn hóa mệnh đề này, ta cần lý giải rõ thế nào là một map. Dohai màu ở mỗi phía của một cạnh phải khác nhau, nên ta cần loại trừ những bản đồcó chứa cầu nối ( xem Hình 2.8 ). Ta cũng cần loại trừ những đỉnh bậc 2, vì chúng cóthể thuận tiện bị vô hiệu ( xem Hình 2.9 ). Để bao quát được những trường hợp này và cáctrường hợp tương tự như, ta ý niệm map là một đồ thị phẳng 3 liên thông, nghĩalà phải bỏ đi tối thiểu 3 đỉnh mới hoàn toàn có thể làm đồ thị mất liên thông. Như vậy bản đồkhông có ” tập cắt ” ( tập cạnh bó đi thì đồ thị sẽ mất liên thông ) gồm 1 hoặc 2 cạnh, và nói riêng không có đỉnh bậc 1 hoặc 2. Vì vậy như ta sẽ thấy, việc vô hiệu cầu nốiở đây tương ứng với việc vô hiệu những khuyên ( cạnh nối một đỉnh với chính nó ). Ta nói một map là ksắc tính diện nếu hoàn toàn có thể tô những nước ( diện ) bằng kmàu sao cho hai nước có đường biên giới ( cạnh ) chung được tô bằng hai màu khácnhau. Để tránh nhầm lẫn, ta dùng ksắc tính đỉnh để chỉ ksắc tính theo nghĩa tôcác đỉnh. Chẳng hạn, map ở Hình 2.10 là 3 sắc tính diện và 4 sắc tính đỉnh. Hình 2.10. Tô đỉnh và tô diệnHình 2.11. Minh họa Định lý 2.7 Định lý bốn màu so với map nói rằng mọi map là 4 sắc tính diện. Hệquả 2.1 sẽ cho thấy hai dạng của định lý bốn màu là tương tự. Trước hết, ta hãytìm điều kiện kèm theo để hoàn toàn có thể tô map bằng 2 màu. Các điều kiện kèm theo này khá đơn thuần. Định lý 2.7. Bản đồ G là 2 sắc tính diện khi và chỉ khi mọi đỉnh của G có bậcchẵn. 22C hứng minh. ⇒ Với mỗi đỉnh v của G, số diện xung quanh v phải là số chẵn, chính bới chúng được tô bằng 2 màu. Từ đó suy ra mọi đỉnh của G có bậc chẵn. ⇐ Nếu mọi đỉnh của G có bậc chẵn thì ta sẽ tô những diện của G bằng 2 màu nhưsau : Chọn diện bất kỳ F và tô nó bằng màu đỏ. Vẽ một đường cong từ điểm x trongF tới điểm y trong diện khác F ‘ và không đi qua đỉnh nào của G. Nếu đường congđó đi qua 1 số ít chẵn cạnh thì tô màu đỏ cho diện chứa y. Nếu trái lại, tô màu xanh. ( xem Hình 2.11 ). Việc tô màu này được trọn vẹn xác lập, vì hoàn toàn có thể lấy một chutrình gồm hai đường như thế và chứng tỏ rằng quy trình đi qua 1 số ít chẵn cạnhcủa G, nhờ dựa trên sự kiện là mỗi đỉnh có một số ít chẵn cạnh liên thuộc nó. ∎ Một chứng tỏ đơn thuần hơn của Định lý 2.7 dựa trên việc chuyển về bàitoán tô màu những đỉnh của đồ thị đối ngẫu. Cho đồ thị phẳng G, đồ thị đối ngẫu ( dualgraph ) G * của G được thiết kế xây dựng như sau : trong mỗi diện f của G, chọn một điểmv *, những điểm này là những đỉnh của G * ; với mỗi cạnh e của G, ta vẽ một cạnh e *, cắt e ( không cắt những cạnh khác của G ) và nối hai đỉnh thuộc hai diện có chung cạnh e, những cạnh như vậy tạo nên tập cạnh của G * ( xem Hình 2.12 ), Định lý 2.8. Cho G là một đồ thị phẳng, không có khuyên và G * là đồ thị đốingẫu của G. Khi đó, G là ksắc tính đỉnh khi và chỉ khi G * là ksắc tính diện. Chứng minh. ⇒ Ta hoàn toàn có thể giả thiết G là một đơn đồ thị liên thông, do đó G * là một map. Nếu G là ksắc tính đỉnh thì ta hoàn toàn có thể dùng k màu để tô những diện củaG * sao cho mỗi diện thừa kế màu của đỉnh duy nhất nằm trong diện đó ( xemHình 2.12 ). Hai diện kề nhau trong G * có màu khác nhau, chính do những đỉnh của Gnằm trong hai diện này là kề nhau trong G, nên chúng có màu khác nhau. Vì vậyG * là k-sắc tính diện. Hình 2.12. Đồ thị đối ngẫu G * : tô đỉnh của G tương tự tô diện của G * 23 ⇐ Bây giờ giả sử rằng G * là ksắc tính diện. Khi đó dùng k màu ta hoàn toàn có thể tôcác đỉnh của G sao cho mỗi đỉnh thừa kế màu của diện chứa nó. Bằng lập luậntương tự như trên hoàn toàn có thể thấy rằng không có hai đỉnh kề nhau nào trong G lại cómàu như nhau. Vì vậy G là ksắc tính đỉnh. Từ đó suy ra hoàn toàn có thể phát biểu dạng đối ngẫu cho định lý bất kể về tô đỉnh củamột đồ thị phẳng để đưa ra định lý về tô diện của map và ngược lại. Để làm ví dụ, ta trở lại Định lý 2.7 và xét cách chứng tỏ khác của định lý này. Ta nhắc lạiĐịnh lý 2.7. Bản đồ G là 2 sắc tính khi và chỉ khi mọi đỉnh của G có bậcchẵn. Chứng minh thứ hai. Có thể chỉ ra rằng đối ngẫu của đồ thị phẳng mà mọiđỉnh có bậc chẵn là một đồ thị phẳng hai phần và ngược lại. Vì vậy ta chỉ cần để ýrằng một đồ thị phẳng, liên thông và không có khuyên là 2 sắc tính đỉnh khi và chỉkhi nó là một đồ thị hai phần. ∎ Tương tự, ta hoàn toàn có thể chứng tỏ hai dạng của định lý bốn màu là tương tự. Hệ quả 2.1. Định lý bốn màu so với những map tương tự với định lý bốnmàu so với những đồ thị phẳng. Chứng minh. ⇒ Ta hoàn toàn có thể giả thiêt G là một đơn đồ thị phẳng liên thông. Khiđó, đồ thị đối ngẫu G * là một map. Theo Định lý 2.8, nếu G * là 4 – sắc tính diệnthì G là 4 sắc tính đỉnh. ⇐ trái lại, giả sử G là một map và G * là đồ thị đối ngẫu của G. Khi đó, G * là một đơn đồ thị phẳng và vì thế theo định lý 2.8, nếu G * là 4 sắc tính đỉnhthì G là 4 sắc tính diện. ∎ Cũng hoàn toàn có thể sử dụng tính đối ngẫu để chứng minh định lý sau đây. Định lý 2.9. Giả sử G là một map lập phương. Khi đó, G là 3 sắc tính diệnkhi và chỉ khi mỗi diện được số lượng giới hạn bởi 1 số ít chẵn cạnh. Chứng minh. ⇒ Cho một diện bất kỳ F của G, những diện của G xung quanh Fphải luân phiên đổi màu. Như vậy phải có 1 số ít chẵn diện quanh F, và vì thế mỗidiện được số lượng giới hạn bởi một số ít chẵn cạnh ( xem Hình 2.13 ) .
