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ương 4 Đồ thị phẳng – Bài toán tô màu đồ thị 5/14/2020 4:53:08 AM Lý thuyết đồ thị Đồ 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. 5/14/2020 4:53:08 AM Lý thuyết đồ thị A B C ? Đồ 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: 5/14/2020 4:53:08 AM Lý thuyết đồ thị Đồ thị phẳng Không là đồ thị phẳng Đồ thị phẳng (tt) Các đồ thị không phẳng nổi tiếng 5/14/2020 4:53:08 AM Lý thuyết đồ thị Đồ thị K5 – đồ thị đầy đủ Đồ thị K3x3 – đồ thị hai phía đầy đủ Công thức Euler Xét đồ thị sau: Đị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 5/14/2020 4:53:08 AM Lý thuyết đồ thị 1 4 3 2 5 6 Công thức Euler (tt) Chứng . | Chương 4 Đồ thị phẳng – Bài toán tô màu đồ thị 5/14/2020 4:54:39 AM Lý thuyết đồ thị Đồ 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. 5/14/2020 4:54:39 AM Lý thuyết đồ thị A B C ? Đồ 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: 5/14/2020 4:54:39 AM Lý thuyết đồ thị Đồ thị phẳng Không là đồ thị phẳng Đồ thị phẳng (tt) Các đồ thị không phẳng nổi tiếng 5/14/2020 4:54:39 AM Lý thuyết đồ thị Đồ thị K5 – đồ thị đầy đủ Đồ thị K3x3 – đồ thị hai phía đầy đủ Công thức Euler Xét đồ thị sau: Đị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 5/14/2020 4:54:39 AM Lý thuyết đồ thị 1 4 3 2 5 6 Công thức Euler (tt) Chứng minh công thức Euler: 5/14/2020 4:54:39 AM Lý thuyết đồ thị 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 Áp dụng công thức Euler suy ra điều phải chứng minh. 5/14/2020 4:54:39 AM Lý thuyết đồ thị Đị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 5/14/2020 4:54:39 AM Lý thuyết đồ thị Tô màu đồ thị 5/14/2020 4:54:39 AM Lý thuyết đồ thị Tô màu đồ thị (tt) 5/14/2020 4:54:39 AM Lý thuyết đồ thị Phải dùng 3 màu để tổ ? Phải dùng 4 màu để tổ Tô màu đồ thị (tt) 5/14/2020 4:54:39 AM Lý thuyết đồ thị Tô màu đồ thị (tt) 5/14/2020 4:54:39 AM Lý thuyết đồ thị 1 3 2 4 5 6
