Bài giảng Toán rời rạc: Chương 6.2 - ThS. Trần Quang Khải

Bài giảng Toán rời rạc: Chương 6.2 cung cấp cho người học những kiến thức như: Sự đẳng cấu của đồ thị; Đồ thị liên thông; Chu trình và Đường đi Euler; Chu trình và đường đi Hamilton; Bài toán tô màu đồ thị. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 6.2 - ThS. Trần Quang KhảiTOÁN RỜI RẠC Chương 6: Đồ thị Giảng viên: ThS. Trần Quang Khải 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ị.Toán rời rạc: 2011-2012 Chương 6: Đồ thị 2 Chương 6 Sự đẳng cấu của đồ thị Đồ thị liên thông Giảng viên: ThS. Trần Quang KhảiToá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. Toán rời rạc: 2011-2012 Chương 6: Đồ thị 4 Sự đẳng cấu của đồ thị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 Chương 6: Đồ thị 5 Example f (u1 )  v1 f (u2 )  ? f (u3 )  v3 f (u4 )  ?Toán rời rạc: 2011-2012 Chương 6: Đồ thị 6 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. Toán rời rạc: 2011-2012 Chương 6: Đồ thị 7 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. Toán rời rạc: 2011-2012 Chương 6: Đồ thị 8 Example Xác định 2 đồ thị sau có đẳng cấu không? Toán rời rạc: 2011-2012 Chương 6: Đồ thị 9 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. Toán rời rạc: 2011-2012 Chương 6: Đồ thị 10 Đồ 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? Toán rời rạc: 2011-2012 Chương 6: Đồ thị 11 Khái niệm: Đường đi 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} saocho x0 = u và xn = v.Toán rời rạc: 2011-2012 Chương 6: Đồ thị 12 Đườ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. Toán rời rạc: 2011-2012 Chương 6: Đồ thị 13Chương 6: Đồ thị Đồ thị liên thông 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 Chương 6: Đồ thị 16 ExampleToán rời rạc: 2011-2012 Chương 6: Đồ thị 17 Đồ 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). Toán rời rạc: 2011-2012 Chương 6: Đồ thị 18 ExampleToán rời rạc: 2011-2012 Chương 6: Đồ thị 19 Đườ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). Toán rời rạc: 2011-2012 Chương 6: Đồ thị 20 ...