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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị Chương 4 Đồ thị phẳng – Bài toán tô màu đồ thị Lý thuyết đồ thị 11/26/15 2 Đồ 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 Đồ 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 Đồ 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 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 Công thức Euler (tt)  Chứng minh công thức Euler: Lý thuyết đồ thị 11/26/15 7 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 Đị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 Tô màu đồ thị Lý thuyết đồ thị 11/26/15 10 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 Tô màu đồ thị (tt) Lý thuyết đồ thị 11/26/15 12 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 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 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 ...