tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 6 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 6 Bài toán tô màu đồ thị, được biên soạn gồm các nội dung chính sau: Định nghĩa; Định lý 4 màu; Nhận biết đồ thị 2-màu; Thuật toán SequentialColor; Một số bài toán ứng dụng. Mời các bạn cùng tham khảo! | Chương 6 Bài toán tô màu đồ thị Nội dung I. Định nghĩa II. Định lý 4 màu III. Nhận biết đồ thị 2-màu IV. Thuật toán SequentialColor V. Một số bài toán ứng dụng Chương 6 Bài toán tô màu đồ thị 2 Lý thuyết đồ thị I. Định nghĩa Cần phải tô màu một bản đồ với điều kiện Hai miền chung biên giới được tô hai màu khác nhau Số màu cần dùng là tối thiểu Hãy xác định số màu tối thiểu cho mọi bản đồ Bản đồ này cần dùng 4 màu để tô Chương 6 Bài toán tô màu đồ thị 3 I. Định nghĩa a d c b e Bài toán tô màu bản đồ quy về bài toán tô màu các Đỉnh của đồ thị Định nghĩa 1 Tô màu một đơn đồ thị là sự gán màu cho các đỉnh của nó sao cho hai đỉnh liền kề nhau được gán màu khác nhau. Định nghĩa 2 Số màu của một đồ thị là số tối thiểu các màu cần thiết để tô màu đồ thị này. Chương 6 Bài toán tô màu đồ thị 4 II. Định lý 4 màu Định lý Số màu của một đồ thị phẳng là không lớn hơn 4 Định lý này được phát biểu lần đầu tiên năm 1850 và được 2 nhà toán học Mỹ Appel và Haken chứng minh năm 1976 bằng phản chứng. Đối với các đồ thị không phẳng số màu có thể tuỳ ý lớn Để chứng minh đồ thị G là n-màu ta phải Chỉ ra 1 cách tô màu G với n màu CMR không thể tô màu G với ít hơn n màu Chương 6 Bài toán tô màu đồ thị 5 II. Định lý 4 màu Các bài toán tô màu đồ thị 1. Cho đồ thị G và số nguyên k. Xây dựng một thuật toán để kiểm tra xem có thể tô màu G bằng k màu nếu được thì thực hiện việc đó. 2. Cho đồ thị G hãy xác định số màu k của đồ thị và hãy tô màu G bằng k màu đó Chương 6 Bài toán tô màu đồ thị 6 II. Nhận biết đồ thị 2-màu Định lý Một đồ thị G là 2-màu khi và chỉ khi G không chứa một chu trình lẻ nào. Chứng minh 1. Giả sử G là đồ thị 2-màu ta phải CMR G không chứa chu trình lẻ. Thật vậy nếu G có chu trình lẻ C v1 v2 v2n 1 v1 Do C chỉ được tô bởi 2 màu các đỉnh lẻ sẽ được tô bằng 1 màu. Nhưng lúc đó v1 và v2n 1 là 2 đỉnh kề nhau có cùng màu vô lý ĐPCM Chương 6 Bài toán tô màu đồ thị 7 II. Nhận biết đồ thị 2-màu Chứng minh 2. Giả sử G không chứa chu trình sẽ CMR G là đồ thị 2-màu. Chọn 1 đỉnh r