tailieunhanh - Giáo trình lý thuyết đồ thị - Bài 7

Sắc số của đồ thị Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau: Hãy tô màu các đỉnh của một đồ thị đã cho, sao cho hai đỉnh kề nhau phải được tô bằng hai màu khác nhau. Ta nói rằng, đồ thị G tô được bằng k màu nếu tồn tại hàm: m : V → {0, 1, 2, . , k-1} sao cho, nếu hai đỉnh x và y kề nhau thì m(x) ≠ m(y). Dễ thấy rằng, đồ thị G tô màu được khi và chỉ khi nó. | BÀI 07 . Sắc số của đồ thị Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau Hãy tô màu các đỉnh của một đồ thị đã cho sao cho hai đỉnh kề nhau phải được tô bằng hai màu khác nhau. Ta nói rằng đồ thị G tô được bằng k màu nếu tồn tại hàm m V 0 1 2 . k-1 sao cho nếu hai đỉnh x và y kề nhau thì m x m y . Dễ thấy rằng đồ thị G tô màu được khi và chỉ khi nó không có đỉnh nút. Định nghĩa Sắc số của một đồ thị chính là số màu ít nhất dùng để tô các đỉnh của đồ thị đó. Ta ký hiệu số s là sắc số của đồ thị G. Hiển nhiên s n số màu không vượt quá số đỉnh của đồ thị. Ví dụ Hãy tô màu đồ thị sau đây. Hình . Tô màu các đỉnh đồ thị Đồ thị trên có sắc số bằng 3. Nhận xét Mỗi cách tô màu m cho đồ thị G sẽ ứng với một cách phân hoạch tập đỉnh V thành các tập ổn định trong không giao nhau mỗi tập ứng với một màu. Ngược lại mỗi cách phân hoạch tập đỉnh V thành các tập ổn định trong không giao nhau sẽ cho ta một cách tô màu. Định lý Mọi chu trình độ dài lẻ luôn có sắc số bằng 3. Chứng minh Giả sử chu trình có độ dài là 2n 1. Ta chứng minh bằng quy nạp theo số n. n 1 Chu trình gồm 3 đỉnh mà hai đỉnh bất kỳ đều kề nhau. Vậy ta phải dùng đúng 3 màu để tô các đỉnh. n n 1 Giả sử a là một chu trình có độ dài 2 n 1 1 2n 3 với dãy các đỉnh là X1 X2 . X2n 1 X2n 2 X2n s . Nối X1 với x2n 1 ta được một chu trình a có độ dài 2n 1. Theo giả thiết quy nạp chu trình a có sắc số bằng 3. Lấy màu của X1 tô cho x2n 2 còn màu của x2n 1 tô cho x2n 3. Chu trình a đã được tô màu mà không phải thêm màu mới. Vậy chu trình a có sắc số bằng 3. Định lý Đồ thị đầy đủ n đỉnh Kn có sắc số bằng n. Dưới đây là một tiêu chuẩn đơn giản để kiểm tra xem một đồ thị có hai sắc sắc số bằng 2 hay không. Định lý Konig Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G là hai sắc khi và chỉ khi G không có chu trình đơn vô hướng độ dài lẻ. Chứng minh Giả sử G là đồ thị hai sắc. Theo Định lý thì G không thể có chu trình đơn vô hưóng độ dài lẻ. Ngược lại giả sử G không có chu trình đơn vô hướng