Giáo trình Toán rời rạc - Bài 6: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức
Tô màu đỉnh của đồ thị
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
1 / 44
Tài liệu tham khảo
▶
Norman L. Biggs, Discrete Mathematics, Oxford University
Press, 2002.
2 / 44
Nội dung
Định nghĩa và ví dụ
Thuật toán tham lam tô màu đỉnh
Đồ thị hai phần
Bài tập
Ví dụ
Trường BK muốn xếp giờ học cho sáu môn học v1, v2, v3, v4, v5, v6
biết rằng có một vài sinh viên học các môn :
v1 và v2, v1 và v4, v3 và v5, v2 và v6,
v4 và v5, v5 và v6, v1 và v6.
v1
v6
v5
v2
v3
v4
4 / 44
Xếp lịch học
v1
v6
v5
v2
v3
v4
Tiết 2
Tiết 1
Tiết 3 Tiết 4
v1 và v3 v2 và v4
v5
v6
5 / 44
Xếp lịch học
▶
▶
Ta tìm cách phân hoạch tập đỉnh thành 4 phần sao cho không
phần nào chứa cặp đỉnh kề nhau.
Một cách hình thức, đây là một hàm
c : {v1, v2, v3, v4, v5, v6} −→ {1, 2, 3, 4}
gán mỗi đỉnh với một giờ học.
▶
Không mất tổng quát ta dùng các số nguyên dương cho các
màu.
6 / 44
Định nghĩa
Một cách tô màu đỉnh của đồ thị G = (V, E) là một hàm
c : V −→ N
thỏa mãn tính chất : Nếu {x, y} ∈ E thì c(x) ̸= c(y).
v1
v6
v5
v2
v3
v4
7 / 44
Định nghĩa
Sắc số của đồ thị G, ký hiệu là χ(G), là số nguyên k nhỏ nhất
thỏa mãn có một cách tô màu G dùng k màu.
Nói cách khác, χ(G) = k nếu và chỉ nếu có một cách tô màu c từ
V tới tập {1, 2, . . . , k}, và k là số nguyên nhỏ nhất thỏa mãn tính
chất này.
Ví dụ
v1
v6
v5
v2
v3
Tìm sắc số của đồ thị
v4
8 / 44
Tìm số màu
Để chứng minh rằng sắc số của một đồ thị là k thì ta phải:
1. tìm một cách tô màu dùng k màu;
2. chứng minh rằng không có cách tô màu nào dùng ít hơn k
màu.
9 / 44
Bài tập
Tìm sắc số của các đồ thị sau:
(i) đồ thị đầy đủ Kn;
(ii) đồ thị vòng C2r;
(iii) đồ thị vòng C2r+1
;
10 / 44
Bài tập
Tìm sắc số của các đồ thị sau:
11 / 44
Bài tập
Hãy mô tả tất cả các đồ thị G có χ(G) = 1.
12 / 44
Nội dung
Định nghĩa và ví dụ
Thuật toán tham lam tô màu đỉnh
Đồ thị hai phần
Bài tập
Bài toán
Cho đồ thị G. Hãy tìm χ(G).
là bài toán khó. Người ta chưa biết thuật toán “nhanh” nào để
giải nó, và hầu hết mọi người đều tin rằng không có thuật toán
như vậy.
14 / 44
Thuật toán tham lam
1. Sắp thứ tự các đỉnh theo thứ tự nào đó: v1, v2, · · · , vn.
2. for i = 1, 2, . . . , n :
3.
Gán màu hợp lệ nhỏ nhất cho vi.
15 / 44
Bài tập
Dùng thuật toán tham lam để tô màu đồ thị sau:
v1
v6
v5
v2
v3
v4
16 / 44
Bài tập
Tìm một cách sắp thứ tự các đỉnh để thuật toán tham lam tô màu
đồ thị sau dùng ít màu nhất có thể.
17 / 44
Bài tập
Tìm một cách sắp thứ tự các đỉnh để thuật toán tham lam tô màu
đồ thị sau dùng ít màu nhất có thể.
18 / 44
Mệnh đề
Nếu mọi đỉnh trong G đều có bậc ≤ k, thì thuật toán tham lam
dùng nhiều nhất k + 1 màu.
Thử chứng minh bằng quy nạp theo k
Đặt P(k) = “nếu mọi đỉnh trong G đều có bậc ≤ k thì thuật toán
tham lam dùng nhiều nhất k + 1 màu”
Bước cơ sở : P(0) đúng. Tại sao?
Bước quy nạp : Giả sử P(k) đúng để chứng minh P(k + 1) !!!
19 / 44
Chứng minh bằng quy nạp theo số đỉnh
Đặt P(n) = “Đồ thị G với n đỉnh và bậc mọi đỉnh trong G đều
≤ k thì thuật toán tham lam dùng nhiều nhất k + 1 màu.”
Bước cơ sở : P(1) đúng vì G không có cạnh nào.
Bước quy nạp : Giả sử P(n) đúng để chứng minh P(n + 1).
▶
▶
▶
▶
▶
Xét G là đồ thị bất kỳ với n + 1 đỉnh và có bậc lớn nhất ≤ k.
Sắp xếp các đỉnh theo thứ tự nào đó: v1, v2, . . . , vn, vn+1
Xóa đỉnh vn+1 khỏi G ta thu được đồ thị G′.
Đồ thị G′ cũng có bậc lớn nhất ≤ k. Tại sao?
.
Theo quy nạp, thuật toán tham lam tô màu G′ dùng nhiều
nhất k + 1 màu.
20 / 44
Tải về để xem bản đầy đủ
44 trang
12380
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 6: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_6_to_mau_dinh_cua_do_thi_tran_vi.pdf
