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

Chia sẻ: Cuchoami2510 | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

40
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

TOÁ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ải 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. 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} sao cho 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ị 13
Chươ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
Example Toá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
Example Toá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