TAILIEUCHUNG - Giáo trình đồ thị - Sắc số của đồ thị

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). | 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

• Toán học
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• tài liệu về đồ thị
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• toán rời rạc
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng