Bài giảng Toán rời rạc - Chương 6: Đồ thị - Phần 2

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 6: Đồ thị Toán rời rạc: 2011-2012 Nội dung (phần 2) 1. Sự đẳng cấu của đồ thị. 2. Đồ thị liên thông. 3. Chu trình và Đường đi Euler. 4. Chu trình và đường đi Hamilton. 5. Bài toán tô màu đồ thị. Chương 6: Đồ thị 2 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Sự đẳng cấu của đồ thị Đồ thị liên thông Chương 6 Toán rời rạc: 2011-2012 Sự đẳng cấu của đồ thị  Isomorphism: sự đẳng cấu, sự đồng hình. Có thể vẽ được 2 đồ thị theo cùng 1 cách? Example:  Trong hóa học: 2 hợp chất khác nhau có thể có cùng công thức phân tử, nhưng khác cấu trúc.  Thiết kế vi mạch: vẽ lại mạch để tối ưu hóa các đường nối. Chương 6: Đồ thị 4 Toán rời rạc: 2011-2012 Sự đẳng cấu của đồ thị Chương 6: Đồ thị 5 Hai đồ thị được gọi là đẳng cấu (isomorphic) nếu có một song ánh giữa tập đỉnh của hai đồ thị đảm bảo quan hệ liền kề. Cho 2 đồ thị đơn G1 = (V1, E1) và G2 = (V2, E2). G1 và G2 là đẳng cấu nếu tồn tại song ánh f sao cho:  Hai đỉnh a và b là liên thông trong G1.  Hai đỉnh f(a) và f(b) là liên thông trong G2. Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 6 ?)( ?)( )( )( 4 2 33 11     uf uf vuf vuf Toán rời rạc: 2011-2012 Chứng minh sự đẳng cấu Việc xác định 2 đồ thị đẳng cấu: Rất khó khăn. Có n! phép tương đương một-một giữa 2 tập đỉnh của 2 đồ thị có n đỉnh. Thông thường: chứng minh 2 đồ thị không đẳng cấu.  Chỉ ra chúng không có 1 tính chất chung. Chương 6: Đồ thị 7 Toán rời rạc: 2011-2012 Chứng minh sự không đẳng cấu Các tính chất chung (sự bất biến) của 2 đơn đồ thị đẳng cấu: Cùng số đỉnh. Cùng số cạnh. Bậc của các đỉnh tương ứng của các đơn đồ thị đẳng cấu phải giống nhau. Chương 6: Đồ thị 8 Toán rời rạc: 2011-2012 Example Xác định 2 đồ thị sau có đẳng cấu không? Chương 6: Đồ thị 9 Toán rời rạc: 2011-2012 Chứng minh đồ thị đẳng cấu Sử dụng ma trận kề: Hai ma trận liền kề phải giống nhau. Gán nhãn lại theo hàm f. Chương 6: Đồ thị 10 Toán rời rạc: 2011-2012 Đồ thị liên thông Câu hỏi: Có thể gửi thông điệp giữa 2 máy tính thông qua đường truyền trung gian? Có thể đi xe bus từ Barcelona sang Manchester? Chương 6: Đồ thị 11 Toán rời rạc: 2011-2012 Khái niệm: Đường đi Chương 6: Đồ thị 12 PATH: Cho G = (V, E) là đồ thị vô hướng hoặc có hướng. Đường đi độ dài n (nguyên dương) từ u tới v là một dãy các cạnh {x0, x1}, {x1, x2},,{xn-1, xn} sao cho x0 = u và xn = v. Toán rời rạc: 2011-2012 Đường đi  Đường đi trên đồ thị đơn:  Có thể k{ hiệu bằng dãy các đỉnh x0, x1,, xn.  Đường đi đơn (simple path): không chứa 1 cạnh quá 1 lần.  Đường đi là chu trình (circuit):  Bắt đầu tại u, kết thúc tại u (quay trở lại).  Chu trình đơn: không chứa 1 cạnh quá 1 lần.  Khi không quan tâm cạnh bội: có thể k{ hiệu bằng dãy các đỉnh x0, x1,, xn. Chương 6: Đồ thị 13 Chương 6: Đồ thị Toán rời rạc: 2011-2012 Đồ thị liên thông Chương 6: Đồ thị 16 Connected Graph: Một đồ thị vô hướng là liên thông nếu tồn tại đường đi giữa mọi cặp đỉnh của đồ thị.  Tính liên thông: Connectivity. Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 17 Toán rời rạc: 2011-2012 Đồ thị (có hướng) liên thông Tính liên thông mạnh (strong connectivity): Nếu tồn tại đường đi giữa mọi cặp đỉnh u, v (2 chiều). Tính liên thông yếu (weak connectivity): Nếu tồn tại đường đi giữa 2 đỉnh bất kz trên đồ thị vô hướng cơ sở (underlying undirected graph). Chương 6: Đồ thị 18 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 19 Toán rời rạc: 2011-2012 Đường đi và sự đẳng cấu Có thể xác định 2 đồ thị đẳng cấu bằng: Đường đi. Chu trình. Sử dụng các bất biến (invariant):  Chu trình đơn có độ dài đặc biệt k nào đó (k > 2). Chương 6: Đồ thị 20 Toán rời rạc: 2011-2012 Example H có chu trình đơn độ dài 3 (v1, v2, v3, v1). G có chu trình đơn độ dài 3? Chương 6: Đồ thị 21 G H Toán rời rạc: 2011-2012 Đồ thị phân đôi? Chương 6: Đồ thị 22 Toán rời rạc: 2011-2012 Đồ thị đẳng cấu? Chương 6: Đồ thị 23 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Đường đi Euler Đường đi Hamilton Chương 6 Toán rời rạc: 2011-2012 Bài toán Kӧnigsberg Chương 6: Đồ thị 25 Challenge: có thể đi qua 7 cây cầu và quay về chỗ cũ, mỗi cây cầu chỉ đi qua đúng một lần? Question: Có một chu trình đơn trên đa đồ thị sao cho nó chứa tất cả các cạnh đúng một lần? Toán rời rạc: 2011-2012 Bài toán Kӧnigsberg Chương 6: Đồ thị 26 Toán rời rạc: 2011-2012 Bài toán Kӧnigsberg Lời giải: Leonard Euler. Công bố: 1736. Có thể coi là ứng dụng đầu tiên của LTĐT. Chương 6: Đồ thị 27 Toán rời rạc: 2011-2012 Chu trình và Đường đi Euler Chương 6: Đồ thị 28 Euler circuit: chu trình đơn đi qua tất cả các cạnh của đồ thị G đúng một lần. Euler path: đường đi đơn đi qua tất cả các cạnh của đồ thị G đúng một lần. Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 29 Toán rời rạc: 2011-2012 Điều kiện cần và đủ Định l{ 1: Một đa đồ thị liên thông có chu trình Euler nếu và chỉ nếu mỗi đỉnh của nó đều có bậc chẵn. Định l{ 2: Một đa đồ thị liên thông có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu nó có đúng hai đỉnh bậc lẻ. Chương 6: Đồ thị 30 Toán rời rạc: 2011-2012 Quay lại bài toán Kӧnigsberg Chương 6: Đồ thị 31 Challenge: có thể đi qua 7 cây cầu và quay về chỗ cũ, mỗi cây cầu chỉ đi qua đúng một lần? Toán rời rạc: 2011-2012 Xây dựng chu trình Euler Input: G: đa đồ thị liên thông với tất cả các đỉnh bậc chẵn. Output: C: chu trình Euler. Khởi tạo: C là một chu trình nào đó trong G. Đồ thị H = G bỏ đi các cạnh thuộc C và các đỉnh cô lập. while (H vẫn còn cạnh) do C’ = một chu trình nào đó trong H mà đỉnh cuối thuộc C. H = H bỏ đi các cạnh thuộc C’ và các đỉnh cô lập. C = C ghép với C’ ở 1 đỉnh nào đó thích hợp. end Chương 6: Đồ thị 32 Toán rời rạc: 2011-2012 Thanh đao của Mohammed Có thể vẽ hình dưới chỉ bằng 1 nét bút? Không được nhấc bút lên. Mỗi cạnh chỉ được vẽ đúng 1 lần. Chương 6: Đồ thị 33 Toán rời rạc: 2011-2012 Thanh đao của Mohammed Chương 6: Đồ thị 34 a, b, d, c, b, e, i, f, e, a Toán rời rạc: 2011-2012 Thanh đao của Mohammed Chương 6: Đồ thị 35 d, g, h, j, i, h, k, g, f, d Toán rời rạc: 2011-2012 Thanh đao của Mohammed Chương 6: Đồ thị 36 Toán rời rạc: 2011-2012 Thanh đao của Mohammed Chương 6: Đồ thị 37 Toán rời rạc: 2011-2012 Chu trình và Đường đi Hamilton Euler: chu trình và đường đi qua mọi cạnh đúng một lần. Câu hỏi: có thể tạo chu trình và đường đi qua mọi đỉnh đúng một lần? Chương 6: Đồ thị 38 Toán rời rạc: 2011-2012 Chu trình và Đường đi Hamilton Chương 6: Đồ thị 39 Hamilton circuit: chu trình đơn đi qua tất cả các đỉnh của đồ thị G đúng một lần. Hamilton path: đường đi đơn đi qua tất cả các đỉnh của đồ thị G đúng một lần. Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 40 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 41 Toán rời rạc: 2011-2012 Chu trình và Đường đi Hamilton Chương 6: Đồ thị 42 Không có điều kiện cần và đủ để xác định sự tồn tại của đường đi hay chu trình Hamilton. Toán rời rạc: 2011-2012 Chu trình và Đường đi Hamilton Không có chu trình Hamilton nếu: ∃v∈V: deg(v) = 1 Định l{ DIRAC: Đồ thị đơn G với n đỉnh (n ≥3) có một chu trình Hamilton nếu deg(v) ≥ n/2, ∀v ∈ V Định l{ ORE: Đồ thị đơn G với n đỉnh (n ≥3) có một chu trình Hamilton nếu deg(u) + deg(v) ≥ n,∀u,v ∈ V và (u, v)  E Chương 6: Đồ thị 43 Toán rời rạc: 2011-2012 Example – Gray Code Được nêu ra bởi Frank Gray (1940s). Phát biểu: gán nhãn các cung trên đường tròn sao cho 2 cung cạnh nhau khác nhau đúng 1 bit. Chương 6: Đồ thị 44 Toán rời rạc: 2011-2012 Example – Gray Code Giải quyết: Mô hình bài toán thành đồ thị n-cube Qn.  Tìm chu trình Hamilton trong Qn. Q3. Chương 6: Đồ thị 45 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Bài toán tô màu đồ thị Chương 6 Toán rời rạc: 2011-2012 Khái niệm: Đồ thị phẳng Chương 6: Đồ thị 47 Planar graph Đồ thị có thể vẽ trên mặt phẳng sao cho không có 2 cạnh bất kỳ nào cắt nhau (không phải tại điểm đầu mút). Phép vẽ như vậy gọi là biểu diễn phẳng (planar representation) của đồ thị. Toán rời rạc: 2011-2012 Đồ thị phẳng Chương 6: Đồ thị 48 Toán rời rạc: 2011-2012 Tô màu bản đồ Vấn đề: Tô màu các quốc gia trên bản đồ sao cho 2 nước láng giềng bất kz luôn có màu khác nhau? Giải pháp: Mỗi nước tô 1 màu  Cần quá nhiều màu. Dùng ít màu hơn  Ít nhất là bao nhiêu? Biểu diễn bản đồ thành đồ thị  Áp dụng LTĐT. Chương 6: Đồ thị 49 Toán rời rạc: 2011-2012 Tô màu đồ thị Mô hình bản đồ thành đồ thị:  Các quốc gia  các đỉnh. Hai quốc gia kề nhau  cạnh nối 2 đỉnh tương ứng.  Lưu {: Hai quốc gia “chạm” nhau chỉ ở 1 điểm không được coi là kề nhau.  Đồ thị có được là đồ thị phẳng. Chương 6: Đồ thị 50 Toán rời rạc: 2011-2012 Tô màu đồ thị Chương 6: Đồ thị 51 Graph coloring Tô màu các đỉnh của đồ thị phẳng sao cho 2 đỉnh bất kỳ kề nhau luôn có màu khác nhau.  Số màu (sắc số: chromatic number) của một đồ thị là số màu ít nhất cần để tô màu đồ thị đó. Ký hiệu: )(G Toán rời rạc: 2011-2012 Tô màu đồ thị Chương 6: Đồ thị 52 Định lý bốn màu “Số màu của một đồ thị phẳng luôn nhỏ hơn hoặc bằng 4” (Kenneth Appel và Wolfgang Haken - 1976) Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 53 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 54 Toán rời rạc: 2011-2012 Tô màu đồ thị Lưu {: Định l{ bốn màu chỉ đúng với đồ thị phẳng. Đối với đồ thị không phẳng: có thể cần nhiều hơn 4 màu. Chương 6: Đồ thị 55 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 56 Toán rời rạc: 2011-2012 Example Chương 6: Đồ thị 57 Toán rời rạc: 2011-2012 Tô màu đồ thị - Ứng dụng Các bài toán xếp lịch:  Lịch thi.  Thời khóa biểu.  Lịch công tác. Các bài toán về phân công công việc. Lập chỉ mục thanh ghi (CPU). Chương 6: Đồ thị 58