Tóm tắt luận văn Thạc sĩ Toán học: Đồ thị phẳng và bài toán tô màu bản đồ

Chia sẻ: Huyen Nguyen My | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

39
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn với mục tiêu tìm hiểu và trình bày một số kiến thức cơ bản về đồ thị, đồ thị phẳng và các kết quả lý thuyết, các định lý liên quan đến bài toán tô màu (tô đỉnh, tô cạnh và tô diện - tô màu bản đồ) trên các loại đồ thị khác nhau, cách tô màu đỉnh, cạnh và diện dựa trên các kết quả lý thuyết đã có và đề cập một số ứng dụng thiết thực của bài toán tô màu trong thực tế.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ Toán học: Đồ thị phẳng và bài toán tô màu bản đồ

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG ĐINH THỊ DỊU - C01055 ĐỒ THỊ PHẲNG VÀ BÀI TOÁN TÔ MÀU BẢN ĐỒ Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8.46.01.13 TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2019
MỞ ĐẦU Các sơ đồ giao thông, sơ đồ mạng lưới thông tin hay sơ đồ tổ chức của một cơ quan, trường học đã khá quen thuộc với nhiều người. Đó là những hình ảnh sinh động và cụ thể của một khái niệm toán học trừu tượng - khái niệm đồ thị. Có thể hiểu đơn giản đồ 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, cùng mối quan hệ giữa chúng. Đồ thị là một mô hình toán học cho nhiều vấn đề lý thuyết và thực tiễn đa dạng. Lý thuyết đồ thị đề cập tới nhiều bài toán có ý nghĩa thực tiến thiết thực, cùng nhiều phương pháp xử lý và thuật toán giải độc đáo hiệu quả, giúp ích cho sự phát triển tư duy toán học nói chung và khả năng vận dụng trong cuộc sống thường ngày nói riêng. Chủ đề về đồ thị còn có trong các đề thi Olympic về toán học ở một số nước. Đồ thị phẳng và bài toán tô màu bản đồ là một trong những chủ đề quan trọng và hấp dẫn của lý thuyết đồ thị. Bài toán tô màu cho đồ thị có nhiều tác dụng trong khoa học và đời sống, được nhiều người quan tâm nghiên cứu và vận dụng. Chẳng hạn tô màu bản đồ, xếp lịch học tập, lập kho chứa hóa chất, thiết kế các bản mạch điện tử, 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... Đề tài luận văn cao học: "Đồ thị phẳng và bài toán tô màu bản đồ" nhằm mục đích tìm hiểu và trình bày một số kiến thức cơ bản về đồ thị, đồ thị phẳng và các kết quả lý thuyết, các định lý liên quan đến bài toán tô màu (tô đỉnh, tô cạnh và tô diện - tô màu bản đồ) trên các loại đồ thị khác nhau, cách tô màu đỉnh, cạnh và diện dựa trên các kết quả lý thuyết đã có và đề cập một số ứng dụng thiết thực của bài toán tô màu trong thực tế. Nội dung luận văn được viết trong ba chương. 1
Chương 1 Đồ thị phẳng và tính chất Chương này trình bày một số kiến thức cơ bản về đồ thị và đồ thị phẳng. Mục 1.1 nhắc lại các 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 nêu khái niệm về đồ thị phẳng, tính chất đặc trưng của các đồ thị phẳng. Trong chương dẫn ra nhiều ví dụ minh họa các khái niệm và kết quả đã trình bày 1.1 Khái niệm cơ bản về đồ thị 1.1.1 Đồ thị vô hướng 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 một sơ đồ vẽ ở Hình 1.34. Hình 1.1: Sơ đồ Hình 1.2: Sơ đồ Hình 1.3: Đồ thị đại khu phố mạch điện diện 2
Từ đó ta đi tới định nghĩa sau. Định nghĩa 1.1. Đồ thị là một tập hợp hữu hạn và khác rỗng các điểm, gọi là đỉnh, và một tập hợp các đoạn (thẳng hay cong) nối liền một số cặp điểm này, gọi là cạnh 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 . . .) hoặc một chữ số (1, 2, 3, . . .). Cạnh nối đỉnh i và đỉnh j (i 6= j) được ký hiệu là (i, j) hoặc (j, i). Một đồ thị như thế còn có tên gọi là đồ thị vô hướng và thường được ký hiệu bằng một chữ cái in hoa (có thể kèm theo chỉ số), như G, G1 , G2 , H, K, N ,. . . Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ V × V thì ta viết G = (V, E). Ta dùng ký hiệu n = |V | là số đỉnh và m = |E| là số cạnh của đồ thị (n > 0, m ≥ 0). Để 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: a, b, c, d, e và 8 cạnh: (a, b), (a, d), (a, e), (b, c), (b, d), (b, e), (c, d) và (d, e). Chú ý rằng điểm cắt nhau của hai cạnh (a, d) và (b, e) trong hình vẽ không phải là một đỉnh của đồ thị. Đỉnh i gọi là kề đỉnh j nếu có một cạnh của đồ thị nối i với j. Nếu ký hiệu cạnh này là e thì ta viết e = (i, j) và nói cạnh e liên thuộc đỉnh i và đỉnh j. Ta cũng nói i và j là hai đầu mút của e. Cạnh e và e0 gọi là kề nhau nếu e, e0 có chung đỉnh. Định nghĩa 1.2. Bậc của một đỉnh v trong đồ thị 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, đỉnh có bậc 1 gọi là đỉnh treo. Ví dụ trong đồ thị vẽ ở Hình 3 ta có ρ(a) = ρ(e) = 3, ρ(b) = ρ(d) = 4, ρ(c) = 2. Dễ dàng chứng minh: 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. Cùng với bậc của đỉnh, ta còn dùng các khái niệm sau: + Bậc nhỏ nhất của G là số δ(G) := min{ρ(v)|v ∈ V }. 3
+ Bậc lớn nhất của G là số ∆(G) := max{ρ(v)|v ∈ V }. + Bậc trung bình của G là số X 2m d(G) := |V1 | ρ(v) = (trong đó n = |V |, m = |E|) n v∈V Rõ ràng là δ(G) ≤ d(G) ≤ ∆(G). Với đồ thị vẽ ở Hình 1.3 thì δ(G) = 2, ∆(G) = 4 và d(G) = 165 = 3, 2. 1.1.2 Các phép toán trên đồ thị Cho đồ thị vô hướng G = (V, E) với tập đỉnh V , tập cạnh E. Xét các phép toán: • Bỏ đỉnh. Với v ∈ V , ta ký hiệu G − v là đồ thị nhận được từ G bằng cách bỏ đỉnh v và các cạnh liên thuộc v. • Bỏ cạnh. Với e ∈ E, ta ký hiệu G − e là đồ thị nhận được từ G bằng cách bỏ cạnh e (không bỏ hai đỉnh đầu mút của e). • Co cạnh. Với e ∈ E, ta ký hiệu 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.4 minh họa các đồ thị G, G − e và G \ e. Hình 1.4: Đồ thị G, cạnh e và các đồ thị G − e và G \ e tương ứng • Đồ thị con của đồ thị G = (V, E) là đồ thị nhận được từ G bằng cách bỏ một số đỉnh và một số cạnh của G. Lưu ý là khi bỏ đi một đỉnh của đồ thị ta đồng thời bỏ đi tất cả các cạnh liên thuộc đỉnh ấy, còn khi bỏ đi một cạnh thì hai đỉnh đầu mút của cạnh ấy vẫn được giữ nguyên. Nói chính xác, H = (V 0 , E 0 ) là một đồ thị con của G = (V, E) nếu V 0 ⊆ V và E 0 ⊆ E. Ta cũng nói G chứa H. Ta nói H là một đồ thị con cảm sinh của G nếu H là một đồ thị con của G và E 0 = {(x, y) ∈ E : x, y ∈ V 0 }. Ở đây H là đồ thị con của G sinh bởi tập đỉnh V 0 ⊆ V . Vì thế ta còn viết H = G[V 0 ]. Đồ thị con 4
H = (V 0 , E 0 ) gọi là đồ thị con bao trùm của G nếu V 0 = V , tức tập đỉnh của H và của G trùng nhau 1.1.3 Đồ thị đẳng cấu Hai đồ thị G1 và G2 gọi là đẳng cấu 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 G1 và G2 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.5 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.5 chỉ gặp nhau ở đỉnh. Các đồ thị đẳng cấu được xem là tương đương (là một) Hình 1.5: Các đồ thị đẳng cấu với đồ thị ở hình 1.3 1.1.4 Phần bù của đơn đồ thị Định nghĩa 1.3. Một đồ thị mà giữa hai đỉnh bất kỳ của nó có không quá một cạnh nối được gọi là một đơn đồ thị. Cho G là một đơn đồ thị với tập đỉnh V , thì phần bù hay đồ thị bù G của G là một đơn đồ thị, với cùng tập đỉnh V và hai đỉnh kề nhau trong G khi và chỉ khi chúng không kề nhau trong G. Hình 1.6: Phần bù G của đơn đồ thị G Định nghĩa 1.4. Đường P từ đỉnh v tới đỉnh w là một dãy liên tiếp các cạnh: (a0 , a1 ), (a1 , a2 ),. . . ,(ak−1 , ak ) với (ai−1 , 5
ai ) ∈ E, a0 = v, ak = w và k ≥ 1, trong đó các đỉnh a0 , a1 ,. . . , ak đều khác nhau. Để đơn giản, đôi khi ta viết P = {a0 , a1 , . . . , ak } 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. Độ dài 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.3, một đường nối đỉnh a và đỉnh c là (a, e), (e, b), (b, c) hay viết gọn là {a, e, b, c}. Hai đường khác từ a tới c là {a, e, d, c} và {a, b, c}. Đồ thị này có các chu trình sau: {a, b, c, d, e, a}; {b, d, e, b},. . . Hình 1.7: Đồ thị liên thông Hình 1.8: Đồ thị không liên thông Định nghĩa 1.5. Một đồ thị gọi là liên thông nếu có đường 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 và cạnh chung. Mỗi đồ thị con liên thông như thế gọi là một thành phần liên thông. Ví dụ đồ thị vẽ ở Hình 1.7 là liên thông, còn đồ thị vẽ ở Hình 1.8 là không liên thông (gồm 3 thành phần liên thông). Định nghĩa 1.6. Một đồ thị không có chu trình gọi là một rừng. Một rừng liên thông gọi là một cây, tức cây là một đồ thị liên thông và không có chu trình. 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á. Đồ thị hình sao là một cây có duy nhất một đỉnh không phải là lá. Ví dụ phả hệ của một họ tộc là một cây (cây phả hệ). 6
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 duy nhất nối một cặp đỉnh bất kỳ của cây. Hình 1.9: Ví dụ về rừng, cây và đồ thị hình sao 1.2 Đồ thị phẳng và công thức Euler Mục này nêu khái niệm về đồ thị phẳng, ví dụ về hai đồ thị không phẳng, định lý đặc trưng cho các đồ thị phẳng và nêu công thức Euler liên hệ giữa số đỉnh, số cạnh và số diện của một đồ thị phẳng, cùng các hệ quả có liên quan. Định nghĩa 1.7. Một đồ thị G gọi là đồ thị phẳng nếu nó có thể biểu diễn được trên một mặt phẳng (hay tương đương, trên mặt cầu) 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 các đầu mút của chúng. Rừng hay cây (Hình 1.9) và hai đồ thị vẽ ở Hình 1.5 là các đồ thị phẳng. K. Wagner (1936) và I. Fáry (1948) đã chứng minh (độc lập nhau) được rằng mọi đơn đồ thị phẳng có thể vẽ trên mặt phẳng sao cho các cạnh là các đoạn thẳng. Khi đó, mỗi miền mặt phẳng giới hạn 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 của đồ thị phẳng. Biên của một diện là tập hợp các cạnh giới hạn diện đó. Hai diện khác nhau gọi là kề nhau 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ề nhau). Diện giới hạn bởi 3 cạnh gọi là một tam giác. 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. 7
Ví dụ, một bản đồ địa lý không có đảo và không có khuyên (tức cạnh nối một đỉnh với chính 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 (mọi đỉnh đều có bậc ≥ 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. Hình 1.10: a) và b).Ví dụ về đồ thị phẳng Sau đây là hai ví dụ điển hình về các đồ thị không phẳng a) Đồ thị 5 đỉnh và mọi cặp đỉnh đều kề nhau là một đồ thị không phẳng xem hình 1.14. b) Đồ thị biểu diễn ba nhà, ba giếng và các con đường nối mỗi nhà với mỗi giếng là một đồ thị không phẳng . Nhận xét rằng mọi đồ thị con của một đồ thị phẳng cũng đều là đồ thị phẳng và một đồ thị mà chứa dù chỉ một đồ thị con không phẳng ắt phải là một đồ thị không phẳng. Từ đó suy ra rằng một đồ thị bất kỳ mà chứa đồ thị con thuộc một trong hai loại đồ thị không phẳng vừa kể trên đương nhiên là một đồ thị không phẳng. Thực ra, như sau đây sẽ thấy, các đồ thị con này là nguyên nhân sinh ra các đồ thị không phẳng theo nghĩa, mỗi đồ thị không phẳng phải chứa một trong hai loại đồ thị không phẳng này. Để phát biểu chính xác hơn, ta cần tới khái niệm về đồ thị đồng cấu như sau. Định nghĩa 1.8. Hai đồ thị gọi là đồng cấu nếu cả hai nhận được từ cùng một đồ thị thứ ba bằng cách thêm các đỉnh bậc hai vào các cạnh của đồ thị đó. Chẳng hạn, hai đồ thị vẽ ở Hình 1.13 là đồng cấu nhau. Khái niệm đồng cấu cho phép phát biểu kết quả quan trọng sau đây, được biết với tên gọi định lý Kuratowski, nêu điều kiện cần và đủ để một đồ thị là phẳng. 8
Hình 1.13: a) và b).Ví dụ về các đồ thị đồng cấu Định lý 1.1. (Kuratowski, 1930).Một đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng cấu với một trong hai kiểu đồ thi không phẳng đã nêu ở trên Đồ thị phẳng có các đặc điểm đáng chú ý sau: Định lý 1.2. 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ủa đồ thị có hệ thức: n − m + d = 2 (Công thức Euler). Dễ dàng mở rộng công thức Euler cho các đồ thị không liên thông. Hệ quả 1.1. Giả sử G là một đồ thị phẳng có n đỉnh, m cạnh, d diện và k thành phần liên thông. Khi đó n − m + d = k + 1. Sau đây ta hạn chế xét các đơn đồ thị (theo Định ngĩa 1.3). Hệ quả 1.2. a) Nếu G là một đơn đồ thị phẳng liên thông có n ≥ 3 đỉnh và m cạnh thì m ≤ 3(n − 2). b) Hơn nữa, nếu G không chứa tam giác (diện có 3 cạnh) thì m ≤ 2(n − 2). Sử dụng hệ quả này ta có thể đưa ra một chứng minh khác cho hai ví dụ đã nêu trên đây (được vẽ lại ở Hình 1.14) là các đồ thị không phẳng Hình 1.14: Minh họa về hai đồ thị không phẳng Bằng lập luận tương tự ta có thể chứng minh định lý sau đây, rất hữu ích khi nghiên cứu vấn đề tô màu đồ thị. 9
Định lý 1.3. Trong một đơn đồ thị phẳng phải có ít nhất một đỉnh với bậc ≤ 5 Cuối cùng, ta nêu một vài nhận xét về "độ dày đặc" của một đồ thị. Trong kỹ thuật điện, các bộ phận của một mạng điện đôi khi được gắn trên một mặt của các tấm phẳng cách điện, gọi là các bản mạch in. Vì các dây dẫn không được bọc cách điện nên chúng không được cắt nhau và đồ thị tương ứng nhận được cần phải là một đồ thị phẳng (Hình 1.15). Hình 1.15: Bản mạch in Với mỗi mạng, ta muốn biết cần bao nhiêu bản mạch in để hoàn chỉnh toàn bộ mạng. Muốn thế, ta định nghĩa độ dày đặc t(G) của đồ thị G là số tối thiểu các đồ thị phẳng mà có thể xếp chồng lên nhau để tạo thành đồ thị G. Giống như số giao cắt của các cạnh, độ dày đặc là số đo mức độ không phẳng của một đồ thị. Chẳng hạn, độ dày đặc của đồ thị phẳng là 1, của các đồ thị không phẳng đã xét là 2. Như sẽ thấy sử dụng công thức Euler dễ dàng có thể tính được một cận dưới cho độ dày đặc của một đồ thị. Điều đáng ngạc nhiên là cận dưới tầm thường này đôi khi lại là giá trị đúng của độ dày đặc. Có thể kiểm tra điều này bằng cách xây dựng trực tiếp. Để đưa ra cận dưới này, ta dùng các ký hiệu bxc và dxe để lần lượt chỉ số nguyên lớn nhất không vượt quá x và số nguyên nhỏ nhất không bé hơn x. Chẳng hạn, b3c = d3e = 3; bπc=3; dπ e= 4. Định lý 1.4. Định lý 1.4.Cho G là một đơn đồ thị phẳng với n ≥ 3 đỉnh và m cạnh. Khi đó, độ dày đặc t(G) của G thỏa mãn các bất đẳng thức 10
m t(G) ≥ d 3n−6 e và t(G) ≥ b m+3n−7 3n−6 c. Đồ thị Platon Trong các đồ thị phẳng, đáng chú ý là các đồ thị Platon. Đồ 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 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.16). Hình 1.6: Đồ thị Planton Dễ dàng kiểm tra lại rằng công thức Euler đúng cho các đồ thị phẳng đặc biệt này. Vì lý do đó công thức Euler đôi khi còn được gọi là "Công thức đa diện Euler". 11
Chương 2 Bài toán tô màu đồ thị Chương này đề cập đến bài toán tô màu đồ thị và trình bày một số kết quả cơ bản về tô màu các đỉnh và các cạnh của đồ thị. Mục 2.1 xét bài toán tô màu các đỉnh của đồ thị, nêu kết quả về tô màu đỉnh cho một số đồ thị đặc biệt. Mục 2.2 xét bài toán tô màu các cạnh của đồ thị, đặc biệt là đồ thị đầy đủ và đồ thị hai phần. 2.1 Tô màu các đỉnh của đồ thị Định nghĩa 2.1. Cho một đồ thị G, ta cần tô màu các đỉnh của G, mỗi đỉnh một màu sao cho hai đỉnh kề nhau có hai màu khác nhau. Ta nói cách tô màu 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 G là một cây thì chỉ cần 2 màu là đủ (Hình 2.1). Định nghĩa 2.2. Số màu tối thiểu cần thiết để tô đúng được các đỉnh của một đồ thị G, gọi là số sắc tính hay sắc số của G và ký hiệu là χ(G) (đọc "khi của G”). 12
Hình 2.1: G không có chu trình Hình 2.2: Sắc số của đồ χ(G) = 2 thị χ(G) = 4 Sau đây là một số dạng đồ thị đặc biệt và sắc số của chúng (1 ≤ χ(G) ≤ n). • Đồ thị rỗng. Một đồ thị có đỉnh, nhưng không có cạnh gọi là một đồ thị rỗng. Đồ thị rỗng n đỉnh được ký hiệu là Nn . Có thể dùng một màu duy nhất để tô cho mọi đỉnh của một đồ thị rỗng: χ(Nn ) = 1 với mọi n ≥ 1 (Hình 2.3). • Đồ thị đầy đủ. Một đồ thị trong đó mọi cặp đỉnh (khác nhau) đều kề nhau, gọi là đồ thị đầy đủ. Đồ thị đầy đủ n đỉnh ký hiệu là Kn . Số cạnh của Kn bằng n(n − 1)/2. Để tô mọi đỉnh của Kn cần dùng n màu: χ(Kn ) = n với mọi n ≥ 1 (Hình 2.4). Hình 2.3: Đồ thị rỗng N4 Hình 24: Đồ thị đầy đủ K3 , K4 và K5 • Đồ thị vòng, đồ thị đường và đồ thị bánh xe. Một đồ thị liên thông và mọi đỉnh có bậc 2 gọi là một đồ thị vòng. Ký hiệu đồ thị vòng n đỉnh là Cn (n ≥ 3). Đồ thị nhận được từ Cn bằng cách bỏ di một cạnh bất kỳ gọi là một đồ thị đường n đỉnh, ký hiệu là Pn . Đồ thị nhận được từ 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ột cạnh, gọi là đồ thị bánh xe n đỉnh, ký hiệu là Wn . Có thể thấy χ(Cn ) = 2 ∀n chẵn và χ(Cn ) = 3 ∀n lẻ (Hình 2.5), χ(Pn ) = 2 với mọi n ≥ 3 (Hình 2.6), χ(Wn ) = 3 ∀n lẻ ≥ 5 và χ(Wn ) = 4 ∀n chẵn ≥ 4 (Hình 2.7). 13
Hình 2.5: Đồ thị vòng C5 và C6 Hình 2.6: Đồ thị đường P5 và P6 Hình 2.7: Đồ thị bánh xe W5 và W6 • Đồ 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 (Hình 2.8). 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). • Đồ thị hai phần đầy đủ 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 đầy đủ 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 2.9. Dễ dàng kiểm tra lại rằng Kr,s có (r + s) đỉnh và r × s cạnh. Hình 2.8: Đồ thị Hình 2.9: Đồ thị hai phần đầy đủ: K1,3 , hai phần K2,3 , K3,3 , K4,3 • Đồ thị chính qui. Một đồ thị mà mọi đỉnh có bậc bằng nhau gọi là một đồ thị chính qui hay đồ thị đều. Một ví dụ điển hình về đồ thị chính qui bậc 3 là đồ thị Petersen (Hình 2.10). Chú ý rằng đồ thị rỗng Nn là đồ thị chính qui bậc 0, đồ thị vòng Cn là đồ thị chính qui bậc 2 và đồ thị đầy đủ Kn là đồ 14
thị chính qui bậc n − 1. Đồ thị Petersen và các đồ thị phẳng chính qui bậc 3 với n ≥ 6 đỉnh có sắc số bằng 3 (Hình 2.11). Hình 2.10: Đồ thị Hình 2.11:Đồ thị phẳng chính Petersen qui bậc 3 Vấn đề tìm sắc số của một đồ thị thường rất phức tạp và cho tới nay nó vẫn chưa có một lời giải thỏa đáng (trừ một số trường hợp kể trên). Dưới đây sẽ trình bày một số kết quả đáng chú ý về các đồ thị có thể tô đúng bằng k màu, gọi tắt là đồ thị k - sắc tính. Sau đây ta giả thiết G là một đơn đồ thị liên thông. Định lý 2.1. Nếu đơn đồ thị liên thông G có bậc lớn nhất của đỉnh bằng ∆ thì G là (∆ + 1) - sắc tính. 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. Đị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. Với đồ thị phẳng ta có định lý 5 màu đáng chú ý của Heawood (1890) Định lý 2.3. Mọi đơn đồ thị phẳng là 5 - sắc tính (dùng 5 màu có thể tô đúng). Một câu hỏi đặt ra là liệu có thể làm mạnh hơn đị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à giả thuyết bốn màu. Theo một cách diễn đạt khác, giả thuyết này đã được Guthrie nêu ra lần đầu tiên năm 1852, và cuối cùng đã được K. Appel và W. Haken giải quyết năm 1976. 15
Định lý 2.4. (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 dùng trong chứng minh định lý 5 - màu (Định lý 2.3). Sau đây là hai ví dụ về ứng dụng tô màu đỉnh của đồ thị. • Xếp lịch giảng chuyên đề. Giả sử cần tổ chức giảng 7 chuyên đề tự chọn cho học viên. Các chuyên đề này ký hiệu là a, b, c, d, e, f và g. Mỗi chuyên đề cần giảng trong 1 tuần (thường bố trí vào các ngày cuối tuần). Do có học viên muốn tham gia học nhiều chuyên đề khác nhau, nên một số chuyên đề không được bố trí học đồng thời. Các dấu * trong bảng dưới đây chỉ rõ các cặp chuyên đề không được xếp lịch học đồng thời. Với qui định như vậy, cần bao nhiêu tuần để hoàn thành lịch giảng tất cả 7 chuyên đề này? Lời giải trình bày trong luận văn • Kho chứa hóa chất. Cầ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 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? Lời giải chi tiết nêu trong luận văn 16
2.2 Tô màu các cạnh của đồ thị Mục này đề cập tới bài toán tô màu cho các cạnh của một đồ thị. Định nghĩa 2.3. Một đồ thị G gọi là k - sắc tính cạnh nếu các cạnh của G có thể tô được bằng k màu sao cho hai cạnh kề nhau có hai màu khác nhau. Nếu G là k - sắc tính cạnh nhưng không là (k − 1) - sắc tính cạnh, thì ta nói rằng chỉ số màu của G là k 0 và viết χ (G) = k. 0 Chẳng hạn, đồ thị G vẽ ở Hình 2.16 có chỉ số màu χ (G) = 4 (các số 1, 2, 3 và 4). Hình 2.16: Chỉ số Hình 2.17: Tô cạnh Hình 2.18: Tô cạnh màu Kn , n lẻ Kn , n chẵn Chú ý rằng nếu ∆ là bậc lớn nhất của các đỉnh trong G thì 0 χ (G) ≥ ∆. Kết quả sau đây, được biết với tên gọi Định lý Vizing, cho một cận khá sát đối với chỉ số màu của một đơn đồ thị G. (Có thể tìm chứng minh trong [4], các trang 455 - 457). Định lý 2.5. (Vizing, 1964) Nếu G là một đơn đồ thị với bậc 0 lớn nhất của đỉnh bằng ∆ thì ∆ ≤ χ (G) ≤ ∆ + 1. Không biết đồ thị nào có chỉ số màu ∆ và đồ thị nào có chỉ số màu ∆ + 1. Tuy nhiên, dễ dàng tìm được chỉ số màu của một 17
0 số loại đồ thị đặc biệt. Chẳng hạn, χ (Cn ) = 2 hoặc 3 phụ thuộc 0 số đỉnh n chẵn hay lẻ, và χ (Wn ) = n − 1 nếu n ≥ 4 Bây giờ ta xác định chỉ số màu của các đồ thị đầy đủ. 0 0 Định lý 2.6. χ (Kn ) = n nếu n lẻ ≥ 3 và χ (Kn ) = n − 1 nếu n chẵn ≥ 2 Ta kết thúc mục này bằng định lý D. K¨onig về chỉ số màu của đồ thị hai phần. Định lý 2.7. (K¨onig, 1916) Nếu G là một đồ thị hai phần với bậc 0 0 lớn nhất của đỉnh bằng ∆ thì χ (G) = ∆. Nói riêng, χ (Kr,s ) = max(r, s). Sau đây là một ví dụ về ứng dụng tô màu cạnh của đồ thị hai phần • Hỏi thi vấn đáp. Cần xếp lịch hỏi thi vấn đáp, mỗi ca thi diễn ra trong 1 giờ, cho 4 sinh viên: a, b, c, d. Co 3 giáo viên tham gia hỏi thi: A, B, C. Đồ thị vẽ ở Hình 2.20 (bên trái) cho biết lịch thi của sinh viên với giáo viên. Hình 2.20: Xếp lịch hỏi thi Ví dụ sinh viên a cần thi hai môn với thầy A và C,. . . Vấn đề là cần bố trí các ca thi sao cho hoàn thành việc hỏi thi sớm nhất có thể? Giải. Có thể giải bài toán này nhờ dùng lý thuyết tô màu cạnh của đồ thị: Tô cho mỗi cạnh một màu sao cho hai cạnh có đỉnh chung phải có màu khác nhau. Khi đó, số màu tối thiểu cần dùng để tô cạnh sẽ xác định số ca cần xếp lịch hỏi thi 18
Theo Định lý 2.7 (Kônig, 1916) thì trong một đồ thị hai phần, số màu tối thiểu cần để tô cạnh bằng bậc lớn nhất của các đỉnh trong đồ thị đó. Với ví dụ này, đó là số 3. Cách tô màu cạnh được chỉ ra ở Hình 2.20 (bên phải): cạnh đậm: tô màu xanh, cạnh kép: tô màu đỏ và cạnh nét đứt: tô màu đen. Lịch hỏi thi như sau: + Ca 1 (các cạnh màu xanh): 3 cặp sinh viên - giáo viên a − A, b − B và d − C. + Ca 2 (các cạnh màu đỏ): 3 cặp sinh viên - giáo viên a − C, b − A và c − B. + Ca 3 (các cạnh màu đen): 3 cặp sinh viên - giáo viên b − C, c − A và d − B. 19