intTypePromotion=1
ADSENSE
 » 
 » 

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ị

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:30

Thêm vào BST
Báo xấu
239
lượt xem 46
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

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

Lưu

Nội dung Text: 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ị

  1. 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
  2. ĐỒ 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
  3. ĐỒ 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
  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 ị 4
  5. ĐỒ 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
  6. ĐỒ 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 v2 Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 6
  7. ĐỒ 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 Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 7
  8. ĐỒ 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
  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 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+1 Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 9
  10. ĐỒ 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+1 Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 10
  11. ĐỒ 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 Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 11
  12. ĐỒ 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
  13. ĐỒ 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 ị 13
  14. ĐỒ THỊ PHẲNG  Công thức Euler  Hệ quả 2  Ví dụ: Chứng minh K3,3 không phẳng. Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 14
  15. ĐỒ 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. Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 15
  16. ĐỒ 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. a a b c b h d c g f e d f e Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 16
  17. 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. Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 17
  18. Tô màu đồ thị  Bài toán A B  Tô màu một bản đồ  Mô hình hóa bài toán D E  Đỉnh: các miền có trên C G bản đồ F  Cạnh: nối hai đỉnh nếu các miền được biểu diễn bằng hai đỉnh này có B biên giới chung.  Yêu cầu: Gắn các màu A E cho các đỉnh của đồ thị sao cho không tồn tại 2 D C G đỉnh kề nhau có cùng một màu. F Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 18
  19. 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). Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 19
  20. 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 v1 v2 ⇒χ(G) = 4 v3 v5 v4 v6 v7 Chương 2. Đồ thị phẳng và bài toán tô màu đồ th ị 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2