tailieunhanh - CHƯƠNG 5 : ĐỒ THỊ PHẲNG

Bài toán cổ “Ba nhà, ba giếng”: Có ba nhà ở gần ba cái giếng, nhưng không có đường nối thẳng các nhà với nhau cũng như không có đường nối thẳng các giếng với nhau. Có lần bất hoà với nhau, họ tìm cách làm các đường khác đến giếng sao cho các đường này đôi một không giao nhau. Họ có thực hiện đư | CẤU TRÚC RỜI RẠC II CHƯƠNG 5 ĐỎ THỊ PHẲNG NHTINHQB@ . ĐỒ THỊ PHẲNG Bài toán Bài toán cổ Ba nhà ba giếng Có ba nhà ở gần ba cái giếng nhưng không có đường nối thang các nhà với nhau cũng như không có đường nối thẳng các giếng với nhau. Có lần bất hoà với nhau họ tìm cách làm các đường khác đến giếng sao cho các đường này đôi một không giao nhau. Họ có thực hiện được ý định đó không Bài toán này có thể được mô hình bằng đồ thị phân đôi đầy đủ K3 3. Câu hỏi ban đầu có thể diễn đạt như sau Có thể vẽ K3 3 trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau Trong chương này chúng ta sẽ nghiên cứu bài toán có thể vẽ một đồ thị trên một mặt phẳng không có các cạnh nào cắt nhau không Khi nào có thể tìm được ít nhất một cách biểu diễn đồ thị không có cạnh cắt nhau . ĐỒ THỊ PHẲNG Định nghĩa 1 Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau ở một điểm không phải là điểm mút của các cạnh . Ví dụ . . T T 1 1 J 1 Ấ 1 A V J 1 Ẳ 1 1 7 4- Ầ . 1 Hình vẽ như thế gọi là một biểu diễn phẳng của đồ .