tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 10 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 10 Đồ thị phẳng, cung cấp cho người đọc những kiến thức như: Bài toán ba biệt thự và ba nhà máy; Đồ thị phẳng; Các điều kiện cho tính phẳng của đồ thị; Sắc số của đồ thị phẳng. Mời các bạn cùng tham khảo! | CHƯƠNG 10 ĐỒ THỊ PHẲNG 1 24 NỘI DUNG Bài toán ba biệt thự và ba nhà máy Đồ thị phẳng Các điều kiện cho tính phẳng của đồ thị Sắc số của đồ thị phẳng 2 24 . BÀI TOÁN BA BIỆT THỰ VÀ BA NHÀ MÁY Bài toán Trong một thị trấn có ba biệt thự và ba nhà máy cung cấp điện nước và khí đốt. Mỗi biệt thự đều muốn mắc đường cáp điện ngầm đường ống cấp nước đường ống cấp khí đốt riêng từ nhà mình đến ba nhà máy mà không gặp đường ống của các biệt thự khác. Hỏi rằng có làm được những đường đi như thế hay không 3 24 . BÀI TOÁN BA BIỆT THỰ VÀ BA NHÀ MÁY tiếp 1 Điện 2 Nước 3 Gas A B C 4 24 . ĐỒ THỊ PHẲNG Định nghĩa Đa đồ thị vô hướng G được gọi là đồ thị phẳng nếu có thể biểu diễn nó trên mặt phẳng sao cho không có hai cạnh nào cắt nhau trừ tại đỉnh. - Diện hữu hạn của một đồ thị phẳng là một miền kín của mặt phẳng được giới hạn bằng các cạnh của đồ thị sao cho có thể nối hai điểm bất kỳ thuộc diện này bằng một nét liền mà không cắt một cạnh nào. - Đồ thị còn có một diện vô hạn đó là phần bù trên mặt phẳng của hợp các diện hữu hạn. 5 24 . ĐỒ THỊ PHẲNG tiếp Định lý Số diện hữu hạn của một đa đồ thị phẳng G bằng chu số của đồ thị này. Chứng minh Quy nạp theo số diện hữu hạn h của G. - h 1 chỉ có một chu trình đơn duy nhất đó chính là biên của diện này. Suy ra chu số bằng 1. - h-1 h Giả sử đồ thị phẳng G với n đỉnh m cạnh và p mảng liên thông có h diện. 6 24 . ĐỒ THỊ PHẲNG tiếp Chứng minh định lý Lập đồ thị G từ G bằng cách bớt đi cạnh e nào đó trên biên của một diện để số diện hữu hạn bớt đi 1. Khi đó G có h-1 diện. Theo giả thiết quy nạp c G h-1 m - 1 - n p p không đổi vì chỉ bớt đi một cạnh trên chu trình . Suy ra số diện hữu hạn của G là h m - n p c G . 7 24 . ĐỒ THỊ PHẲNG tiếp Hệ quả Nếu đa đồ thị phẳng G có n đỉnh m cạnh p mảng liên thông và h diện thì n - m h p 1 công thức Euler tổng quát Chứng minh Số diện của đồ thị phẳng bằng số diện hữu hạn cộng thêm 1 diện vô hạn bằng chu số cộng 1. Vậy thì h m - n p 1. Do đó n - m h p 1. 8 24 . ĐỒ