intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:21

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

Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị được biên soạn nhằm cung cấp cho các bạn những kiến thức về đồ thị phẳng; công thức Euler; định lý Kuratowski; tô màu đồ thị; bài toán tô màu đồ thị; ứng dụng của đồ thị phẳng.

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 Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị

  1. Chương 4 Đồ thị phẳng – Bài toán tô màu đồ thị
  2. Lý thuyết đồ thị 11/26/15 2
  3. Đồ thị phẳng  Bài toán mở đầu:  Có 3 gia đình, 3 nhà cung cấp điện, nước, gas.  Các gia đình đều cần điện, nước, gas và đều muốn đi dây riêng.  Cần nối dây từ các gia đình đến các nhà cung cấp sao cho không dây nào cắt dây nào. A B ? C Lý thuyết đồ thị 11/26/15 3
  4. Đồ thị phẳng  Định nghĩa: Đồ thị vô hướng G là đồ thị phẳng nếu ta có thể biểu diễn nó trên một mặt phẳng sao cho không có cạnh nào cắt nhau. VD: Đồ thị phẳng Không là đồ thị phẳng Lý thuyết đồ thị 11/26/15 4
  5. Đồ thị phẳng (tt)  Các đồ thị không phẳng nổi tiếng Đồ thị K5 – đồ thị Đồ thị K3x3 – đồ thị đầy đủ hai phía đầy đủ Lý thuyết đồ thị 11/26/15 5
  6. Công thức Euler  Xét đồ thị sau: 1 2 3 4 6 5  Định lý: Cho G là đồ thị phẳng, liên thông với n đỉnh và m cạnh. Gọi r là số miền trong biểu diễn phẳng của G. Khi đó, ta có: r=m-n+2 Lý thuyết đồ thị 11/26/15 6
  7. Công thức Euler (tt)  Chứng minh công thức Euler: Lý thuyết đồ thị 11/26/15 7
  8. Công thức Euler (tt)  Hệ quả. Nếu G là đơn đồ thị phẳng liên thông với e cạnh, v đỉnh, trong đó v 3. Khi đó ta có: e 3v – 6  Chứng minh:  Gọi r là số miền  Mỗi miền đều tương ứng với ít nhất 3 cạnh  Mỗi cạnh tướng ứng với đúng 2 miền  Gọi bậc của mỗi miền là số cạnh tương ứng với nó  Suy ra, tổng bậc của các miền ít nhất là bằng 2 lần số cạnh 2.e = deg( R) 3.r R  Áp dụng công thức Euler suy ra điều phải chứng minh. Lý thuyết đồ thị 11/26/15 8
  9. Định lý Kuratowski  Định lý: Đồ thị G là đồ thị phẳng nếu và chỉ nếu G không chứa đồ thị con đẳng cấu với K5 hoặc K3x3  VD: các đồ thị sau đây không là đồ thị phẳng Lý thuyết đồ thị 11/26/15 9
  10. Tô màu đồ thị Lý thuyết đồ thị 11/26/15 10
  11. Tô màu đồ thị (tt) Phải dùng 3 màu để tổ Phải dùng 4 màu để tổ ? Lý thuyết đồ thị 11/26/15 11
  12. Tô màu đồ thị (tt) Lý thuyết đồ thị 11/26/15 12
  13. Tô màu đồ thị (tt) 1 2 7 8 4 7 1 2 8 4 6 3 6 9 3 5 9 5 2 6 2 5 6 1 4 5 1 4 3 7 3 7 Lý thuyết đồ thị 11/26/15 13
  14. Bài toán tô màu đồ thị  Định nghĩa. Tô màu một đồ thị vô hướng là một sự gán màu cho các đỉnh sao cho hai đỉnh kề nhau phải khác màu nhau.  Định nghĩa. Số màu (sắc số) của một đồ thị là số màu tối thiểu cần thiết để tô màu đồ thị này. 1 2 7 8 2 6 1 4 5 4 3 6 9 3 7 5 Đồ thị có số màu là 3 Đồ thị có số màu là 4 Lý thuyết đồ thị 11/26/15 14
  15. Bài toán tô màu đồ thị (tt)  Định lý. (Định lý 4 màu) Số màu của một đồ thị phẳng là không lớn hơn 4.  Một số thông tin liên quan:  Bài toán được đưa ra năm 1850  Có rất nhiều chứng minh sai về bài toán này  Chứng minh sai nổi tiếng là của Alfred Kempe vào năm 1879  Percy Heawood phát hiện ra chứng minh sai ở trên vào năm 1890  Dựa vào đó, năm 1976 Appel và Haken đã chứng minh bằng cách sử dụng máy tính Lý thuyết đồ thị 11/26/15 15
  16. Bài toán tô màu đồ thị (tt)  Tìm số màu của các đồ thị sau: Lý thuyết đồ thị 11/26/15 16
  17. Ứng dụng  Bài toán lập lịch thi: Hãy lập lịch thi trong một trường đại học sao cho không có sinh viên nào thi hai môn cùng một lúc.  Giải pháp:  Biểu diễn bằng đồ thị:  Mỗi môn học là một đỉnh  Nếu 2 môn học nào được dự thi bởi cùng 1 sinh viên thì sẽ nối bằng 1 cạnh.  Cách lập lịch sẽ tương ứng với bài toán tô màu của đồ thị này. Lý thuyết đồ thị 11/26/15 17
  18. Ứng dụng (tt)  VD: Có 7 môn thi với thông tin như sau:  Môn 1: có các sinh viên A, B, C và D thi  Môn 2: có các sinh viên A, E, F, G và H thi  Môn 3: có các sinh viên B, E, I, J và K thi  Môn 4: có các sinh viên B, F, L và M thi  Môn 5: có các sinh viên G, L, N và O thi  Môn 6: có các sinh viên J, M, N và P thi  Môn 7: có các sinh viên D, H, K, O và P thi Hãy xếp lịch thi thành các đợt sao cho các sinh viên đều có thể dự thi tuần tự các môn mình đăng ký Lý thuyết đồ thị 11/26/15 18
  19. Ứng dụng (tt)  VD: Có 7 môn thi với thông tin như sau: 1  Môn 1: có các sinh viên A, B, C và D thi 7 2  Môn 2: có các sinh viên A, E, F, G và H thi  Môn 3: có các sinh viên B, E, I, J và K thi  Môn 4: có các sinh viên B, F, L và M thi 3  Môn 5: có các sinh viên G, L, N và O thi 6  Môn 6: có các sinh viên J, M, N và P thi  Môn 7: có các sinh viên D, H, K, O và P thi 5 4 Đợt thi Môn thi 1 1, 5 2 2, 6 3 3 4 4, 7 Lý thuyết đồ thị 11/26/15 19
  20. Ứng dụng (tt)  Bài toán phân chia tần số.  Các kênh truyền hình từ số 2 đến số 13 được phân chia cho các đài truyền hình sao cho không có 2 đài cách nhau không quá 150 dặm lại dùng chung một kênh  Hãy tìm cách phân sao cho số kênh dùng là ít nhất  Giải pháp:  Biểu diễn bằng đồ thị:  Mỗi đỉnh là một đài phát  Hai đỉnh được nối một cạnh nếu hai đài phát cách nhau ít hơn 150 dặm  Số màu của đồ thị chính là số kênh cần dùng. Lý thuyết đồ thị 11/26/15 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 © 2022-2032 TaiLieu.VN. All rights reserved.

 

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