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ọilà đẳng cấu (isomorphic)
nếucó mộtsong ánh giữa tậpđỉnh củahai đồ
thịđảm bảoquan hệliền kề.
Cho 2 đồ thị đơn G1=(V1, E1)và G2=(V2, E2).
G1 và G2là đẳng cấu nếu tồn tại song ánh fsao cho:
Hai đỉnh avà blà liên thông trong G1.
Hai đỉnh f(a) và f(b) là liên thông trong G2.