Xem mẫu
- 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
nguon tai.lieu . vn
