tailieunhanh - Bài giảng ĐỒ THỊ PHẲNG VÀ BÀI TOÁN TÔ MÀU ĐỒ THỊ

Để nghiên cứu về đồ thị phẳng, ta bắt đầu bằng việc xét bài toán "Ba nhà ba giếng" như sau: Có ba nhà ở gần ba cái giếng, từ mỗi nhà có đường đi thẳng đến từng 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 hòa với nhau, họ tìm cách làm các đường khác đến giếng | CHƯƠNG III ĐỒ THỊ PHẲNG VÀ BÀI TOÁN TÔ MÀU ĐỒ THỊ I. Đồ thị phẳng 1. Bài toán mở đầu 2. Đồ thị phẳng 3. Công thức Euler 4. Định lý Kuratowski II. Bài toán tô màu đồ thị 1. Bài toán mở đầu 2. Tô màu đồ thị 3. Môt số định lý về tô màu đồ thị 4. Thuât toán Welch-Powell về tô màu đồ thị 5. Ứng dụng của bài toán tô màu I. Đồ thị phẳng 1. Bài toán mở đầu Để nghiên cứu về đồ thị phẳng ta bắt đầu bằng việc xét bài toán Ba nhà ba giếng như sau Có ba nhà ở gần ba cái giếng từ mỗi nhà có đường đi thẳng đến từng 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 hòa 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 Ta xây dựng đồ thị G V E mô tả đầy đủ các thông tin của bài toán Đỉnh Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các gia đình và các giếng nước. Đối tượng của bài toán ở đây được chia làm hai loại là gia đình và giếng nước. Vậy mỗi đỉnh biểu diễn cho một gia đình hoặc một giếng nước. Cạnh Trong đồ thị G các đỉnh và được nối với nhau bằng một cạnh nếu có đường nối thẳng trực tiếp từ một gia đình đến một giếng nước. Vậy mối quan hệ giữa 02 đối tượng ở đây là mối quan hệ đường đi. Mỗi cạnh nối 2 đỉnh đại diện cho 01 gia đình và đại diện cho một giếng nước trong G nếu có đường đi trực tiếp từ gia đình đến giếng nước . Ta có đồ thị G như sau Khi giải quyết bài toán trên ta cần đến khái niệm đồ thị phẳng như sau 2. Đồ thị phẳng . Định nghĩa 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 ở điểm không phải là điểm mút của mỗi cạnh. Hình vẽ như vậy được gọi là một biểu diễn phẳng của đồ thị. . Các ví dụ Ví dụ 1 K4 là đồ thị phẳng vì có thể vẽ lại như sau Ví dụ 2 Q3 cũng là đồ thị phẳng vì Ví dụ 3 Ta sẽ xét xem đồ thị lưỡng phân K3 3 có là đồ thị phẳng không Ta còn lại đỉnh v6. Có 3 trường hợp đối với V6 Nếu v6 nằm trong R1 thì cạnh nối v3 với .