TAILIEUCHUNG - 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

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton