Tài liệu Thuật toán tô màu đồ thị và ứng dụng (lv01834)

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 ĐỖ ANH SƠN THUẬT TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, NĂM 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 ĐỖ ANH SƠN THUẬT 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: TS. Trần Vĩnh Đức HÀ NỘI, NĂM 2015 LỜI CẢM ƠN Lời đầu tiên em xin trân trọng gửi lời cảm ơn sâu sắc nhất đến thầy Trần Vĩnh Đức, thầy đã tận tình chỉ bảo và hƣớng dẫn em trong suốt quá trình nghiên cứu đề tài để em hoàn thành tốt luận văn của mình! Tiếp đến em xin chân thành gửi lời cảm ơn đến các thầy giáo, cô giáo trong Phòng sau Đại học, các thầy giáo, cô giáo trong trƣờng Đại học Sƣ phạm Hà Nội 2 và các thầy giáo, cô giáo thỉnh giảng từ các trƣờng Đại học trên địa bàn Thủ đô Hà Nội đã nhiệt tình truyền tải những kiến thức, kinh nghiệm cho em trong suốt 2 năm học tại trƣờng. Em xin chân thành biết ơn gia đình, bạn bè và các đồng nghiệp đã hết sức tạo điều kiện, luôn giúp đỡ và động viên em trong suốt quá trình học tập, nghiên cứu và làm việc. Trân trọng cảm ơn! Đại học Sƣ phạm Hà Nôi 2. Ngày tháng 12 năm 2015. Đỗ Anh Sơn LỜI CAM ĐOAN Tô xin cam đoan: a) Những nội dung trong luận văn này là do tôi thực hiện dƣới sự hƣớng dẫn trƣợc tiếp của Tiến sĩ Trần Vĩnh Đức. b) Mọi tham khảo dùng trong luận văn này đều đƣợc trích dẫn rõ ràng và trung thực tên tác giả, tên công trình, thời gian, địa điểm công bố. c) Mọi sao chép không hợp lệ, vi phạm quy tắc đào tạo, hay gian dối, tôi xin chịu hoàn toàn trách nhiệm. Xuân Hòa, tháng 12 năm 2015 TÁC GIẢ Đỗ Anh Sơn MỤC LỤC MỞ ĐẦU…………………………………………………...…………………1 NỘI DUNG…………………………………………………………………...3 CHƢƠNG 1: TỔNG QUAN VỀ ĐỒ THỊ……………………………………3 1.1. Một số khái niệm cơ bản..………………………...……………….3 1.2. Hành trình, chu trình và đƣờng đi……….……………...…..……..6 1.3. Cây...…………………..…………………………...……………...7 1.4. Đồ thị phẳng…….................……………………………….….…..9 1.5. Biểu diễn đồ thị bằng ma trận……………………………………13 1.5.1. Biểu diễn đồ thị bằng ma trận kề……………………….…..….13 1.5.2. Biểu diễn đồ thị bằng ma trận liên thuộc…………...………….14 CHƢƠNG 2: TÔ MÀU ĐỒ THỊ……………………………………………16 2.1. Định nghĩa và một số kết quả cơ bản………………………...…..16 2.2. Đa thức tô màu………………………………..………...………..20 2.3. Thuật toán tham lam tô màu đồ thị………………………………23 2.4. Một số bài toán………………………….…...…………..……….25 2.4.1. Bài toán điều khiển đèn hiệu nút giao thông..……………….....25 2.4.2. Bài toán lập lịch thi………………………………………….....28 2.4.3. Bài toán phân chia tần số……...…………………………….....29 2.4.4. Bài nữ sinh của Kirkman…………………………………….....31 CHƢƠNG 3: ỨNG DỤNG…..……………………….……………………..33 3.1. Bài toán lập thời khóa biểu………………………………..……..33 3.2. Mô hình bài toán bằng đồ thị………………………...........……..36 3.3. Siêu đồ thị……………...………………………………….……..41 3.3.1. Khái niệm siêu đồ thị ………………………………………….41 3.3.2. Tô màu siêu đồ thị ………………………………………….….43 3.4. Mô hình bài toán bằng siêu đồ thị………………………...….…..46 3.5. Xếp thời khóa biểu…………………...…………………...….…..51 3.6. Kết luận chƣơng 3.…………………...…………………...….…..57 KẾT LUẬN…………..……………………………………………………...58 TÀI LIỆU THAM KHẢO……………………………………………..…….59 KÍ HIỆU CÁC CHỮ VIẾT TẮT Kí hiệu LTĐT THCS CN GDCD TBK Từ đƣợc viết tắt Lý thuyết đồ thị Trung học cơ sở Công nghệ Giáo dục công dân Thời khóa biểu DANH MỤC CÁC BẢNG Số hiệu bảng 2.1 2.2 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 Tên bảng Khoảng cách các đài phát thanh Gán màu theo bậc của đỉnh Môn học và khối lƣợng tiết học trên tuần Phân công chuyên môn 30 giáo viên Phân công chuyên môn 5 giáo viên Môn học ứng với đỉnh đồ thị Tô màu đỉnh tƣơng ứng Bậc của đỉnh và cạnh liên thuộc Số hóa tiết học của các môn trong tuần Mã số tiết dạy của giáo viên và ký hiệu Đỉnh đồ thị H và màu tô tƣơng ứng Tham chiếu màu tô của đỉnh với các siêu cạnh A, B, C,..., AA, AB, ..., AE Trang 30 31 33, 34 34, 35 36 37, 38 39 43 47 48, 49 53, 54 55, 56, 57 DANH MỤC CÁC HÌNH VẼ Số hiệu hình vẽ 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 2.1 2.2 2.3 2.4 2.5 3.1 3.2 3.3 3.4 Tên hình vẽ Đồ thị G = (V, E) Hai đồ thị đẳng cấu Đồ thị Petersen Một rừng gồm 4 cây Đồ thị phẳng và đồ thị không phẳng Ví dụ đồ thị phẳng G Đồ thị đẳng cấu với độ chính xác tới đỉnh bậc 2 Biểu diễn đồ thị G Đồ thị G và G e Tô màu đồ thị G Đồ thị mô phỏng pha điều khiển giao thông Đồ thị mô phỏng 7 môn thi Đồ thị mô phỏng 6 đài phát thanh Đồ thị môn dạy của 5 giáo viên Tô màu đồ thị môn dạy của 5 giáo viên Siêu đồ thị H Hàng xóm của đỉnh vn+1 Trang 3 6 7 8 9 11 12 14 22 25 27 28 30 38 40 42 45 1 MỞ ĐẦU Có thể nói, Leonhard Euler là ngƣời đầu tiên nghiên cứu về lý thuyết đồ thị (LTĐT). Bài báo của ông về Bảy Cây Cầu ở thành phố Königsberg đƣợc xem nhƣ xuất bản đầu tiên của LTĐT. Đến nay, LTĐT có nhiều ứng dụng sâu sắc trong nhiều lĩnh vực khác nhau nhƣ trong kinh tế tài chính, trong công nghiệp, trong công nghệ thông tin... LTĐT thực sự bắt đầu đƣợc nghiên cứu rộng rãi từ những năm 60 của thế kỷ trƣớc do sự phát triển mạnh mẽ của máy tính điện tử. Một cách không hình thức, đồ thị gồm hai loại đối tƣợng: tập đỉnh và một quan hệ trên tập đỉnh này. Không bất ngờ, mô hình rất tự nhiên này cho phép mô hình hóa rất hiệu quả các bài toán thực tế. Các bài toán thực tế thƣờng đƣợc chuyển một cách tự nhiên thành bài toán trên đồ thị, từ đó dễ dàng thiết kế thuật toán để giải bằng máy tính. Ngƣợc lại, nhiều khái niệm trong đồ thị đƣợc lấy từ thực tế. Ví dụ, khái niệm đƣờng đi, cây, rừng... Quan hệ hai chiều này làm cho LTĐT trở thành một lĩnh vực hấp dẫn không chỉ cho các nhà lý thuyết mà còn cho cả những ngƣời làm thực hành. Một trong những bài toán quan trọng của LTĐT là bài toán tô màu. Tô màu đồ thị là cách gán giá trị màu cho mỗi đỉnh sao cho hai đỉnh kề nhau có màu khác nhau. Khái niệm tô màu đồ thị cho phép mô hình các bài toán lập lịch, phân công công việc, các bài toán thỏa mãn ràng buộc... Tìm cách tô màu đồ thị bằng một số ít màu là bài toán khó, nhƣng vô cùng quan trọng. Lợi ích tƣơng ứng của nó trong thực tế là lời giải cho vấn đề lập lịch công việc tối ƣu, phân công công việc hợp lý... Mục đích của luận văn “Thuật toán tô màu đồ thị và ứng dụng” là nghiên cứu các thuật toán tô màu đồ thị và ứng dụng nó vào trong bài toán xếp thời khóa biểu của Trƣờng THCS Trƣng Vƣơng, Mê Linh, Hà Nội. 2 Mục đích nghiên cứu Nghiên cứu lý thuyết đồ thị và tìm hiểu thuật toán tô màu đồ thị để giải quyết bài toán xếp thời khóa biểu. Nhiệm vụ nghiên cứu Nghiên cứu lý thuyết đồ thị, chỉ ra các bài toán vận dụng thuật toán tô màu trên đồ thị và giải quyết bài toán thực tế lập thời khóa biểu cho giáo viên, học sinh trong các trƣờng phổ thông. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng đƣợc nghiên cứu cụ thể là lý thuyết đồ thị, bài toán tô màu đồ thị và ứng dụng thực tế lập thời khóa biểu. Trong phạm vi giới hạn của đề tài, luận văn nghiên cứu các giải quyết một số bài toán thực tế và mô hình lập lịch thời khóa biểu ở trƣờng Trung học cơ sở Trƣng Vƣơng huyện Mê Linh. Phƣơng pháp nghiên cứu Đọc, phân tích và tổng hợp tài liệu. Giả thuyết khoa học Phần nghiên cứu lý thuyết sẽ cung cấp một cách nhìn tổng quát về lý thuyết đồ thị và các thuật toán đồ thị. Kết quả nghiên cứu có thể áp dụng cho các trƣờng học phổ thông. Cấu trúc luận văn: Ngoài chƣơng mở đầu và kết luận, luận văn gồm 3 chƣơng:  Chƣơng 1 đƣa ra một số khái niệm của lý thuyết đồ thị, cách biểu diễn đồ thị và một số thuật toán liên quan đến đồ thị.  Chƣơng 2 đƣa ra các khái niệm về tô màu đồ thị, đa thức tô màu và trình bày thuật toán tham lam tô màu đồ thị, và một vài ứng dụng đơn giản.  Chƣơng 3 trình bày ứng dụng tô màu đồ thị để giải quyết bài toán lập thời khóa biểu trƣờng THCS Trƣng Vƣơng, Mê Linh, Hà Nội. 3 CHƢƠNG 1 TỔNG QUAN VỀ ĐỒ THỊ Trong chƣơng này chúng ta trình bày một số khái niệm cơ bản về đồ thị, về cây, đƣờng, liên thông, đẳng cấu,…, và biểu diễn đồ thị. 1.1. Một số khái niệm cơ bản Định nghĩa 1.1. Một đồ thị G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là tập với các phần tử là các tập con hai phần tử của V. Các phần tử của V cũng đƣợc gọi là các đỉnh, còn các phần tử của E đƣợc gọi là các cạnh của đồ thị G. Nếu e = {a,b} là một cạnh của G thì a và b đƣợc gọi là các đỉnh đầu mút của cạnh e hay các đỉnh liên thuộc với e, và ta nói đỉnh a kề với đỉnh b. Ta cũng thƣờng ký hiệu canh {a,b} ngắn gọn là ab. Đồ thị thƣờng đƣợc biểu diễn trên mặt phẳng bằng các điểm và đƣờng. Mỗi điểm thể hiện một đỉnh của đồ thị, còn mỗi đƣờng nối hai điểm thể hiện một cạch nối hai điểm đầu mút. Ví dụ 1.2. Xét đồ thị G = (V, E) với V = {a,b,c,d} và E = {{a,b}, {b,d}, {b,c}, {c,d}}. Khi đó G đƣợc biển diễn trên mặt phẳng bằng Hình 1.1 dƣới đây a b d c Hình 1.1: Đồ thị G = (V,E) 4 Định nghĩa 1.3. Đồ thị G’ = (V’, E’) đƣợc gọi là đồ thị con của đồ thị G = (V, E) nếu V '  V và E '  E . Đồ thị con G’ = (V’, E’) của đồ thị G = (V, E) đƣợc gọi là đồ thị con bao trùm của G nếu V’ = V. Nếu E’ chứa tất cả các cung hay cạnh của G, mà cả hai đỉnh liên thuộc với nó đều thuộc V’, thì G’ = (V’,E’) đƣợc gọi là đồ thị con của G = (V, E) cảm sinh bởi tập đỉnh V’ hay cũng đƣợc gọi là đồ thị con cảm sinh bởi G = (V, E) trên tập đỉnh V’. Khi đó G’ cũng đƣợc ký hiệu là G’ = G[V’]. Ta cũng có thể xây dựng đồ thị mới từ các đồ thị đã cho bằng cách xóa hay thêm một số đỉnh hoặc cạnh. Nếu W V , thì G  W  G V \ W  , tức là đồ thị con của G nhận đƣợc từ G bằng cách xóa đi các đỉnh thuộc W và mọi cung (hay cạch) liên thuộc với các đỉnh trong W. Hiển nhiên là nếu một đồ thị có cấp bằng n thì cỡ m của nó thỏa mãn n 0  m    . Đồ thị cấp n và cỡ m = 0 đƣợc gọi là n-đồ thị rỗng hay n-đồ thị  2 hoàn toàn rời rạc và đƣợc ký hiệu là On hay En. Còn đồ thị cấp n và cỡ n m    đƣợc gọi là n-đồ thị đầy đủ và thƣờng đƣợc ký hiệu Kn.  2 Định nghĩa 1.4. Giả sử G = (V, E) là một đồ thị với V  n . Ta định nghĩa đồ thị bù của G, ký hiệu G , là đồ thị với tập đỉnh cũng là V, còn cạnh là E(Kn)\E. Định nghĩa 1.5. Một đồ thị G = (V, E) đƣợc gọi là đồ thị m-phần nếu ta có thể phân loại V thành dạng V  V1  V2  ...  Vm với Vi   , i = 1,2,3,…,m, sao cho các đỉnh trong cùng Vi , i = 1,2,3,…,m là không kề nhau. Nếu G là một đồ thị m-phần và tồn tại cạnh nối một đỉnh bất kỳ của Vi với một đỉnh bất kỳ của V j cho mọi i  j thì G đƣợc gọi là m-phần đầy đủ. 5 Đồ thị 2-phần đầy đủ, trong đó các phần V1 và V2 có |V1| = m, |V2| = n đƣợc ký hiệu là Km,n. Định nghĩa 1.6. Xét đồ thị G = (V, E) và một đỉnh v V . Ta ký hiệu tập các hàng xóm của v là NG (v)  {x V | x  v và {x, v} E} Trong trƣờng hợp đồ thị G đƣợc hiểu ngầm, ta ký hiệu NG (v) đơn giản bằng N (v) . Định nghĩa 1.7. Bậc của đỉnh v trong đồ thị G, ký hiệu là degG(v) hay ngắn gọn là deg(v), là lực lƣợng của tập NG (v) . Định lý 1.8 (Bổ đề bắt tay - Hand Shaking Lemma). Trong đồ thị G = (V, E) bất kỳ ta luôn có  deg(v)  2 | E | vV Chứng minh: Vì mỗi cạnh trong đồ thị đƣợc tính hai lần (tƣơng ứng cho hai đỉnh đầu mút) trong tổng bậc. □ Ta cũng ký hiệu  (G)  min deg(v), vV (G)  max deg(v), vV tƣơng ứng với bậc nhỏ nhất và bậc lớn nhất của các đỉnh của G. Nếu  (G)  (G)  k , thì mọi đỉnh của G đều có bậc bằng k và G đƣợc gọi là đồ thị chính quy bậc k hay gắn gọn là k-chính quy. Một đồ thị đƣợc gọi là chính quy nếu nó là k-chính quy với một k nào đấy. Đồ thị k-chính quy cũng đƣợc gọi là đồ thị bậc k. Đỉnh v đƣợc gọi là đỉnh treo nếu deg(v) = 1, đƣợc gọi là đỉnh cô lập nếu deg(v) = 0. 6 Định nghĩa 1.9. Đồ thị G = (V,E) và G’ = (V’, E’) đƣợc gọi là đẳng cấu với a, b  E ) nhau nếu tồn tại song ánh  :V  V  , sao cho khi và chỉ khi { (a), (b)} E . Song ánh  nhƣ trên đƣợc gọi là đẳng cấu của G và G’. Hai đồ thị đẳng cấu với nhau G và G’ đƣợc ký hiệu là G  G . Ví dụ 1.10. Hai đồ thị G = (V, E) và G’ = (V’, E’) là các đồ thị biểu diễn nhƣ trong Hình 1.2. Khi đó G  G và ánh xạ  :V  V  với  (1)  a ,  (5)  b ,  (2)  c ,  (6)  d ,  (3)  e ,  (4)  f , là đẳng cấu của G và G’. a 1 2 5 4 3 f b e c 6 G = (V,E) d G’ = (V’,E’) Hình 1.2: Hai đồ thị đẳng cấu 1.2. Hành trình, chu trình và đƣờng đi Trong mục này chúng ta đề cập đến khái niệm hành trình, chu trình và đƣờng đi trong đồ thị. Định nghĩa 1.11. Xét đồ thị G = (V, E). Một hành trình trong G là một dãy đỉnh v0,v1,v2,…,vn thỏa mãn vi và vi+1 kề nhau với với mọi i = 0,1,…,n-1. Khi đó n cũng đƣợc gọi là độ dài, đỉnh v0 đƣợc gọi là đỉnh đầu, vn đƣợc gọi là đỉnh cuối của hành trình. Hành trình mà trong đó mọi đỉnh đều khác nhau đƣợc gọi là đường đi. 7 Định nghĩa 1.12. Một hành trình đƣợc gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Một hành trình khép kín, mà khi xóa đỉnh cuối thì trở thành một đƣờng đi đƣợc gọi là một chu trình. Ví dụ 1.13. Cho đồ thị G = (V, E) nhƣ Hình 1.3. Đồ thị này đƣợc gọi là đồ thị Petersen. Khi đó, a) abcde là một đƣờng; b) abcdea là một chu trình; a e’ e d’ d a’ ’ b’ b c’ c Hình 1.3: Đồ thị Petersen Định nghĩa 1.14. Một đồ thị G = (V, E) đƣợc gọi là liên thông nếu với hai đỉnh vi và vj khác nhau bất kỳ của G tồn tại một hành trình trong G với đỉnh đầu là vi và đỉnh cuối là vj. Trong trƣờng hợp ngƣợc lại, đồ thị đƣợc gọi là không liên thông. Định nghĩa 1.15. Đồ thị con liên thông G’ = (V’, E’) của một đồ thị G = (V, E) đƣợc gọi là một thành phần liên thông của G, nếu G’ = G[V’] và với mọi V "  V , mà thực sự chứa V’, đồ thị G[V’] là không liên thông. 8 1.3. Cây Trong mục này chúng ta đề cập đến khái niệm một lớp mô hình đồ thị không có chu trình và các điều kiện tƣơng đƣơng. Định nghĩa 1.16. Một đồ thị liên thông và không có chu trình đƣợc gọi là cây. Một đồ thị (không nhất thiết phải là liên thông) không có chu trình đƣợc gọi là rừng. Các đỉnh bậc một của cây đƣợc gọi là đỉnh lá hay đỉnh cuối, còn các đỉnh bậc lớn hơn 1 của cây đƣợc gọi là đỉnh cành hay đỉnh trong. Ví dụ 1.17. Đồ thị G = (V, E) Hình 1.4 là rừng gồm 4 cây G1, G2, G3, G4. G1 G2 G3 G4 Hình 1.4: Một rừng gồm 4 cây Định lý 1.18. Giả sử T = (V, E) là đồ thị. Khi đó các khẳng định sau đây là tương đương với nhau: (a) T là cây; (b) T không chứa chu trình và |E| = |V| - 1; (c) T liên thông và |E| = |V| - 1; 9 (d) T là đồ thị liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì đồ thị nhận được là không liên thông; (e) Hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng một đường; (f) T không chứa chu trình, nhưng nếu ta thêm một cạnh nối hai đỉnh không kề nhau trong T thì đồ thị nhận được có đúng một chu trình. 1.4. Đồ thị phẳng Trong mục này chúng ta đề cập đến lớp đồ thị đặc biệt: Các đồ thị có thể vẽ trên mặt phẳng bởi các điểm và các đƣờng không cắt nhau. Định nghĩa 1.19. Đồ thị G = (V, E) đƣợc gọi là đồ thị phẳng nếu nhƣ nó có thể biểu diễn đƣợc ở trên mặt phẳng sao cho các đƣờng cong biểu diễn các cạnh hoặc không giao nhau hoặc giao nhau ở các đỉnh chung. Biểu diễn nói trên của đồ thị phẳng đƣợc gọi là biểu diễn phẳng. Ví dụ 1.20. Trên Hình 1.5. Đồ thị đầy đủ K4 biểu diễn bên trái không là đồ thị phẳng, còn biểu diễn ở là biểu diễn phẳng của K4. Đồ thị đầy đủ K5 và đồ thị 2-phần đầy đủ K3,3 không là đồ thị phẳng. K4 K4 K5 Hình 1.5: Đồ thị phẳng và đồ thị không phẳng K3,3 10 Định nghĩa 1.21. Giả sử G = (V, E) là một đồ thị phẳng. Khi đó, phần mặt phẳng đƣợc giới hạn bởi các cạnh của G và không bị chia thành các phần nhỏ hơn bởi các cạnh khác đƣợc gọi là một miền (hay cũng gọi là một mặt) của G. Định lý 1.22 (Công thức Euler). Nếu đồ thị phẳng liên thông G = (V, E) có v đỉnh, e cạnh và f miền, thì v - e + f = 2. Chứng minh. Ta chứng minh định lý bằng quy nạp theo số miền f. Với f = 1 khi đó G không có chu trình, nhƣng G liên thông suy ra G là cây. Vậy e = v - 1. Suy ra v - e + f = v - v + 1 + 1 = 2 vậy đúng với f = 1. Giả sử định lý đã đƣợc chứng minh cho mọi đồ thị phẳng liên thông có số miền nhỏ hơn f. Do f = 1 định lý đã đúng nên ta có thể giả thiết f ≥ 2. Do f ≥ 2 nên G có một chu trình C. Giả sử e là một cạnh của chu trình C. Giả sử S là miền của G nằm phần bên trong giới hạn bởi C và T là miền của G nằm phần bên ngoài giới hạn bởi C sao cho e là cạnh chung của S và T đƣợc biểu diễn trong hình vẽ sau đây T S e C G Xét đồ thị G’ có tập đỉnh là V và E’. G = (V, E) với E’ = E\{e}. Khi đó G’ là đồ thị con của đồ thị phẳng (vì G’ là đồ thị con của đồ thị phẳng G) với số đỉnh bằng v và số cạnh bằng e - 1. Do F và T nhập một nên số miền bằng f - 1 < f. 11 Do đó v - (e - 1) + (f - 1) = 2 tƣơng đƣơng v - e + f = 2 theo giả thiết quy nạp suy ra điều phải chứng minh. □ Định lý 1.23 (Bất đẳng thức cạnh đỉnh). Trong đồ thị phẳng liên thông G = (V, E) bất kỳ với chu vi nhỏ nhất g (girth) thỏa mãn 3  g   ta luôn có g ( V  2) g 2 E Chứng minh. Giả sử G có các cạnh là e1 ,e2,…,em và có các miền T1,T2,…,Tl Xác đinh ma trận l cột và m hàng M = (mi,j)m × l Với      mij = 1 nếu ei nằm trên biên của Tj. mij = 0 nếu ei không nằm trên biên của Tj. Xét ví dụ đồ thị phẳng G nhƣ Hình 1.6 ta có ma trận 1 0  0 M  1 1  0 0 0 1 1 0 1  1 1 0  0 1 0 1 0 0  0 1 1 e2 T2 e5 e1 e3 T1 e4 T3 T4 e6 Hình 1.6 Ví dụ đồ thị phẳng G 12 Tính số s phần tử 1 trong M. Nếu tính theo hàng ta có s ≤ 2m  Tính theo cột ta có số phần tử s chính là số cạnh nằm trên biên của miền suy  ra chính là chu trình. Do đó ta có g.l ≤ s Từ  và  ta suy ra g.l ≤ 2m Áp dụng công thức Euler cho đồ thị phẳng, ta có: |V| - m + l = 2  l = 2 - |V| + m Với g.l ≤ 2m ta có g.( 2 - |V| + m) ≤ 2m  m.(g - 2) ≤ g.( |V| - 2)  m m chính là số cạnh nên suy ra | E | g (| v | 2) g 2 g (| v | 2) g 2 □ Hệ quả 1.24. Đồ thị đầy đủ K5 và đồ thị 2-phần đầy đủ K3,3 không là đồ thị phẳng. Chứng minh. Đồ thị K5 có 5 đỉnh, 10 cạnh và chu vi nhỏ nhất g bằng 3. Nếu K5 là đồ thị phẳng, thì theo bất đẳng thức cạnh đỉnh 10  3 (5  2)  9 , điều 3 2 này mâu thuẫn. Vậy K5 không là đồ thị phẳng. Tƣơng tự, đồ thị K3,3 có 6 đỉnh, 9 cạnh và chu vi nhỏ nhất g bằng 4. Nếu K3,3 là đồ thị phẳng, thì theo bất đẳng thức cạnh đỉnh 9  điều này mâu thuẫn. Vậy K3,3 không là đồ thị phẳng. 4 (6  2)  8 42 □ Định nghĩa 1.25. Hai đồ thị G1 và G2 đƣợc gọi là đẳng cấu với độ chính xác tới các đỉnh bậc 2, nếu chúng hoặc đẳng cấu với nhau hoặc có thể biến đổi thành các đồ thị đẳng cấu với nhau bằng cách chèn thêm hay xóa đi các đỉnh bậc 2. Ví dụ 1.26. Hai đồ thị G1 và G2 trên Hình 1.7 là các đồ thị đẳng cấu với độ chính xác tới đỉnh bậc 2.