Đang chuẩn bị liên kết để tải về tài liệu:
BÀI 17_Chương 10: Đồ thị phẳng

Bài toán ba biệt thự và ba nhà máy 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? Để giải quyết bài toán trên, ta sẽ sử dụng khái niệm đồ thị phẳng. . | BÀI 17 Chương 10 Đồ thị phẳng 10.1. Bài toán ba biệt thự và ba nhà máy 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 Hình 10.1. Ba biệt thự và ba nhà máy Để giải quyết bài toán trên ta sẽ sử dụng khái niệm đồ thị phẳng. 10.2. Đồ thị phẳng Định nghĩa 10.1 Đ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. Ví dụ từ một bản đồ địa lý thế giới ta xây dựng một đồ thị với mỗi nước là một đỉnh hai đỉnh được nối với nhau bằng một cạnh nếu hai nước tương ứng có chung đường biên giới. Đồ thị nhận được là một đồ thị phẳng. Giả sử G là một đồ thị phẳng được biểu diễn trên mặt phẳng. 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 gặp một cạnh nào ở bên trong. Đồ 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. Ký hiệu h là số diện hữu hạn của một đồ thị phẳng. Ta sẽ thấy rằng hệ chu trình đơn độc lập cực đại sẽ chia đồ thị phẳng thành các diện hữu hạn. Thật vậy Định lý 10.1 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. 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 chu số của G là 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 chu số của G. Hệ quả 10.2 Nếu đa đồ thị phẳng Gcó n đỉnh m