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ị

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Ị ĐỒ THỊ PHẲNG Bài toán Tì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ước Cạnh: đường đi từ nhà đến các giếng Có thể vẽ đồ thị mà không có 2 cạnh nào cắt nhau? ĐỒ THỊ PHẲNG Đồ thị phẳng Mộ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ị. ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Đồ thị sau có phải là đồ thị phẳng không? ĐỒ THỊ PHẲNG Đồ thị phẳng Ví dụ Chứng minh K3,3 không phẳng. ĐỒ THỊ PHẲNG Đồ thị phẳng Công thức Euler Tất cả biểu diễn phẳng của cùng một đồ thị có số miền bằng nhau Định lý 1 Trong đơn đồ thị phẳng, liên thông thì r = e – v + 2 r: số miền e: số cạnh v: số đỉnh ĐỒ THỊ PHẲNG Công thức Euler Chứng minh Xây dựng dãy đồ thị con của G G1  e1 Gi = Gi-1  ei (i = 2,3, …, e) G  Ge Quy nạp Định lý đúng với G1 Giả sử Gn phẳng thỏa rn = en  vn + 2 Xét đồ thị phẳng Gn+1 Gn+1 = Gn  (an+1, bn+1) ĐỒ THỊ PHẲNG Công thức Euler Chứng minh Xét đồ thị phẳng Gn+1 Gn+1 = Gn  (an+1, bn+1) Nếu an+1, bn+1 đều thuộc Gn an+1, bn+1 nằm trên miền biên của miền chung rn+1 = rn + 1 en+1 = en + 1 vn+1 = vn  rn+1 = en+1  vn+1 + 2. ĐỒ THỊ PHẲNG Công thức Euler Chứng minh Xé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 Gn Chỉ có an+1 nằm trên miền biên của miền chung rn+1 = rn en+1 = en + 1 vn+1 = vn + 1  rn+1 = en+1  vn+1 + 2. ĐỒ THỊ PHẲNG Công thức Euler Ví 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 3 ĐỒ THỊ PHẲNG Công thức Euler Hệ quả 1 Cho 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ẳng Mỗi miền được bao ít nhất 3 cạnh Mỗi cạnh nằm trên nhiều nhất 2 miền  3r  2e (*) Theo định lý Euler: r = e – v + 2 Thay vào (*) ta có: e  3v  6 (đpcm) ĐỒ THỊ PHẲNG Công thức Euler Hệ quả 2 Cho 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 3 Mỗi miền được bao ít nhất 4 cạnh Mỗi cạnh nằm trên nhiều nhất 2 miền  4r  2e (*) Theo định lý Euler: r = e – v + 2 Thay vào (*) ta có: e  2v  4 (đpcm) ĐỒ THỊ PHẲNG Công thức Euler Hệ quả 2 Ví dụ: Chứng minh K3,3 không phẳng. ĐỒ THỊ PHẲNG Công thức Euler Hệ quả 3 Cho 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ý 2 Cho 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. ĐỒ 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. Tô màu đồ thị Bài toán Tô 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 nhau Xá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. Tô màu đồ thị Bài toán Tô 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. Tô màu đồ thị Định nghĩa Tô 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). Tô màu đồ thị Định nghĩa Ví dụ Tìm sắc số của đồ thị sau: Số màu cần tô: 4 v1v3v6v4 đôi một kề nhau (G) = 4 Tô màu đồ thị Định lý Mọi đơn đồ thị đầy đủ đều có: (Kn) = n. Chứng minh Quy nạp theo n n = 1: Thỏa Giả sử (Kn) = n Xét Kn+1 = (V, E) V’ = V \ {vn+1}, E’  E G (V’, E’)  Kn vn+1vi  E  (Kn+1) = n + 1 Tô màu đồ thị Một số định lý về tô màu đồ thị Định lý 1 Mọi chu trình độ dài lẻ đều có sắc số là 3 Chứng minh Quy nạp Tô 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)  n Ví dụ: Tìm sắc số của đồ thị sau Chú ý Nếu G’  G thì (G)  (G’) Tô 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 minh Nhận xét (Cn) = 2 nếu n chẵn (n 3) (Cn) = 3 nếu n lẻ (n 3) Tô 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ính Ta 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 5 Tô màu đồ thị Thuật toán Welch Powell Sắ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àu Tô màu đồ thị Thuật toán Welch Powell Chú ý 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 được Bài toán tìm sắc số là một bài toán khó! Tô màu đồ thị Thuật toán Welch Powell Ví dụ 1: Tô màu cho đồ thị sau với số màu ít nhất có thể được Tô màu đồ thị Thuật toán Welch Powell Ví dụ 2: Tô màu cho đồ thị sau với số màu ít nhất có thể được Tô màu đồ thị Ứng dụng Hã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.