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

Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 3: Đồ thị phẳng và bài toán tô màu đồ thị trình bày khái niệm đồ thị phẳng, tô màu đồ thị,...Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 3: Đồ thị phẳng và bài toán 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Ị 1 ĐỒ 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?Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 2 ĐỒ 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ị.Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 3 ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị sau có phải là đồ thị phẳng không?Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 4 ĐỒ THỊ PHẲNG  Đồ thị phẳng  Ví dụ  Đồ thị sau có phải là đồ thị phẳng không?Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 5 ĐỒ THỊ PHẲNG  Đồ thị phẳng v1 v2 v3  Ví dụ  Chứng minh K3,3 không phẳng. v4 v5 v6 v1 v5 v1 v5 R21 R2 R1 v 3 R1 R22 v4 v2 v4 v2Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 6 ĐỒ 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ố đỉnhChương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 7 ĐỒ 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)Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 8 ĐỒ 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 an+1  en+1 = en + 1  vn+1 = vn ⇒ rn+1 = en+1 − vn+1 + 2. bn+1Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 9 ĐỒ 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 bn+1 ⇒ rn+1 = en+1 − vn+1 + 2. an+1Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 10 ĐỒ 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 3Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 11 ĐỒ 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)Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 12 ĐỒ 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)Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ...