Bài giảng Tô màu đỉnh của đồ thị - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

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. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

11 6 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Toán rời rạc (BKHN)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

44 trang 2 tháng trước

Tác giả:

Profile Lân Nguyễn
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 v
1
, v
2
, v
3
, v
4
, v
5
, v
6
biết rằng có một vài sinh viên học các môn :
v
1
và v
2
, v
1
và v
4
, v
3
và v
5
, v
2
và v
6
,
v
4
và v
5
, v
5
và v
6
, v
1
và v
6
.
v
1
v
2
v
3
v
4
v
5
v
6
4 / 44
Xếp lịch học
v
1
v
2
v
3
v
4
v
5
v
6
Tiết 1 Tiết 2 Tiết 3 Tiết 4
v
1
và v
3
v
2
và v
4
v
5
v
6
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 : {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
} −→ {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).
v
1
v
2
v
3
v
4
v
5
v
6
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ụ
Tìm sắc số của đồ thị
v
1
v
2
v
3
v
4
v
5
v
6
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 đủ K
n
;
(ii) đồ thị vòng C
2r
;
(iii) đồ thị vòng C
2r+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 đó: v
1
, v
2
, · · · , v
n
.
2. for i = 1, 2, . . . , n :
3. Gán màu hợp lệ nhỏ nhất cho v
i
.
15 / 44
Bài tập
Dùng thuật toán tham lam để tô màu đồ thị sau:
v
1
v
2
v
3
v
4
v
5
v
6
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 đó: v
1
, v
2
, . . . , v
n
, v
n+1
.
▶
Xóa đỉnh v
n+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
| 1/44
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

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 v2 v5 v3 v4 4 / 44 Xếp lịch học v1 v6 v2 v5 v3 v4 Tiết 1 Tiết 2 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 v2 v5 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 v2
Tìm sắc số của đồ thị v5 v3 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 v2 v5 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