Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 3: Đồ thị phẳng và các bài toán về tô màu đồ thị - Cao Thanh Tình

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌCĐỒ THỊ PHẲNG VÀ CÁC BÀI TOÁN VỀ TÔ MÀU ĐỒ THỊ1ĐỒ THỊ PHẲNGBài toánTìm cách làm cho các con đường đi dẫn từ 3 ngôi nhà tới 3 cái giếng sao cho không có 2 con đường nào cắt nhau?Mô hình bài toánĐỉnh: các gia đình và giếng nướcCạnh: đường đi từ nhà đến các giếngCó thể vẽ đồ thị mà không có 2 cạnh nào cắt nhau?2ĐỒ THỊ PHẲNGĐồ thị phẳngMột đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau ở điểm không phải là điểm mút của mỗi cạnh. Hình vẽ như vậy được gọi là một biểu diễn phẳng của đồ thị.3ĐỒ THỊ PHẲNGĐồ thị phẳngVí dụĐồ thị sau có phải là đồ thị phẳng không?4ĐỒ THỊ PHẲNGĐồ thị phẳngVí dụĐồ thị sau có phải là đồ thị phẳng không?5ĐỒ THỊ PHẲNGĐồ thị phẳngVí dụChứng minh K3,3 không phẳng.6ĐỒ THỊ PHẲNGĐồ thị phẳngCông thức EulerTất cả biểu diễn phẳng của cùng một đồ thị có số miền bằng nhauĐịnh lý 1Trong đơn đồ thị phẳng, liên thông thìr = e – v + 2r: số miềne: số cạnhv: số đỉnh7ĐỒ THỊ PHẲNGCông thức EulerChứng minhXây dựng dãy đồ thị con của GG1  e1Gi = Gi-1  ei (i = 2,3, , e)G  GeQuy nạpĐịnh lý đúng với G1Giả sử Gn phẳng thỏa rn = en  vn + 2Xét đồ thị phẳng Gn+1 Gn+1 = Gn  (an+1, bn+1)8ĐỒ THỊ PHẲNGCông thức EulerChứng minhXét đồ thị phẳng Gn+1 Gn+1 = Gn  (an+1, bn+1)Nếu an+1, bn+1 đều thuộc Gnan+1, bn+1 nằm trên miền biên của miền chungrn+1 = rn + 1en+1 = en + 1vn+1 = vn rn+1 = en+1  vn+1 + 2. 9ĐỒ THỊ PHẲNGCông thức EulerChứng minhXét đồ thị phẳng Gn+1 Gn+1 = Gn  (an+1, bn+1)Nếu bn+1 (hoặc an+1) không thuộc GnChỉ có an+1 nằm trên miền biên của miền chungrn+1 = rnen+1 = en + 1vn+1 = vn + 1 rn+1 = en+1  vn+1 + 2. 10ĐỒ THỊ PHẲNGCông thức EulerVí dụTính số miền trong một đơn đồ thị phẳng liên thông có 8 đỉnh và mỗi đỉnh đều có bậc 311ĐỒ THỊ PHẲNGCông thức EulerHệ quả 1Cho G là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh; v  3. Khi đó: e  3v  6. Chứng minh:Trong một đồ thị phẳngMỗi miền được bao ít nhất 3 cạnhMỗi cạnh nằm trên nhiều nhất 2 miền 3r  2e (*)Theo định lý Euler: r = e – v + 2Thay vào (*) ta có: e  3v  6 (đpcm)12ĐỒ THỊ PHẲNGCông thức EulerHệ quả 2Cho G là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh; v  3 và không có chu trình độ dài 3. Khi đó: e  2v  4. Chứng minh:Trong một đồ thị phẳng không có chu trình độ dài 3Mỗi miền được bao ít nhất 4 cạnhMỗi cạnh nằm trên nhiều nhất 2 miền 4r  2e (*)Theo định lý Euler: r = e – v + 2Thay vào (*) ta có: e  2v  4 (đpcm)13ĐỒ THỊ PHẲNGCông thức EulerHệ quả 2Ví dụ: Chứng minh K3,3 không phẳng.14ĐỒ THỊ PHẲNGCông thức EulerHệ quả 3Cho G là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh. Khi đó V có ít nhất đỉnh w thỏa d(w)  5Định lý 2Cho G là một đơn đồ thị phẳng với e cạnh, v đỉnh và có k thành phần liên thông. Gọi r là số miền (regions) trong biểu diễn phẳng của G. Khi đó: v  e + r = k + 1.15ĐỒ THỊ PHẲNGĐịnh lý KuratowskiĐồ thị G là không phẳng khi và chỉ khi G chứa một đồ thị con đồng phôi với K3,3 hoặc K5.Ví dụ:Chứng minh các đồ thị sau không phẳng.16Tô màu đồ thịBài toánTô màu một bản đồ2 miền có chung biên giới được tô bằng 2 màu tùy ý, miễn là khác nhauXác định số màu tối thiểu cần có để tô màu một bản đồ sao cho hai miền kề nhau có màu khác nhau.17Tô màu đồ thịBài toánTô màu một bản đồMô hình hóa bài toánĐỉnh: các miền có trên bản đồCạnh: nối hai đỉnh nếu các miền được biểu diễn bằng hai đỉnh này có biên giới chung. Yêu cầu: Gắn các màu cho các đỉnh của đồ thị sao cho không tồn tại 2 đỉnh kề nhau có cùng một màu.18Tô màu đồ thịĐịnh nghĩaTô màu một đơn đồ thị là việc gán màu cho các đỉnh của nó sao cho hai đỉnh liền kề có màu khác nhau.Sắc số (Chromatic number)Số màu tối thiểu cần thiết để tô màu G.Ký hiệu: (G).19Tô màu đồ thịĐịnh nghĩaVí dụTìm sắc số của đồ thị sau:Số màu cần tô: 4v1v3v6v4 đôi một kề nhau(G) = 420Tô màu đồ thịĐịnh lýMọi đơn đồ thị đầy đủ đều có: (Kn) = n.Chứng minhQuy nạp theo nn = 1: ThỏaGiả sử (Kn) = nXét Kn+1 = (V, E)V’ = V \ {vn+1}, E’  EG (V’, E’)  Knvn+1vi  E  (Kn+1) = n + 121Tô màu đồ thịMột số định lý về tô màu đồ thịĐịnh lý 1Mọi chu trình độ dài lẻ đều có sắc số là 3Chứng minhQuy nạp22Tô màu đồ thịMột số định lý về tô màu đồ thịĐịnh lý 2 Nếu G có chứa một đồ thị con đẳng cấu với Kn thì (G)  nVí dụ: Tìm sắc số của đồ thị sauChú ýNếu G’  G thì (G)  (G’) 23Tô màu đồ thịMột số định lý về tô màu đồ thịĐịnh lý 3 Một đơn đồ thị G = (V, E) có thể tô bằng 2 màu khi và chỉ khi nó không có chu trình độ dài lẻChứng minhNhận xét(Cn) = 2 nếu n chẵn (n 3)(Cn) = 3 nếu n lẻ (n 3)24Tô màu đồ thịMột số định lý về tô màu đồ thịĐịnh lý 4 (Định lý 4 màu) Mọi đồ thị phẳng đều có sắc số không lớn hơn 4Định lý được chứng minh bởi Appel và Haken Đây là định lý đầu tiên được chứng minh với sự trợ giúp của máy tínhTa có thể chứng minh định lý yếu hơn:Mọi đồ thị phẳng đều có sắc số không lớn hơn 525Tô màu đồ thịThuật toán Welch PowellSắp xếp các đỉnh G theo bậc giảm dần.Dùng một màu để tô đỉnh đầu tiên và cũng dùng màu này để tô màu các đỉnh liên tiếp trong danh sách mà không kề với đỉnh đầu tiên.Bắt đầu trở lại đầu danh sách, tô màu thứ hai cho đỉnh chưa được tô và lập lại quá trình trên cho đến khi tất cả các đỉnh đều được tô màu26Tô màu đồ thịThuật toán Welch PowellChú ýKết quả của thuật toán có thể không là sắc sốThuật toán chỉ cho ta kết quả chấp nhận đượcBài toán tìm sắc số là một bài toán khó!27Tô màu đồ thịThuật toán Welch PowellVí dụ 1: Tô màu cho đồ thị sau với số màu ít nhất có thể được28Tô màu đồ thịThuật toán Welch PowellVí dụ 2: Tô màu cho đồ thị sau với số màu ít nhất có thể được29Tô màu đồ thịỨng dụngHãy lập lịch thi cho các sinh viên trong một trường đại học sao cho không có sinh viên nào phải thi 02 môn trong cùng một buổi thi. Cho biết các môn thi có chung sinh viên dự thi đối với từng môn thi.30