Bài giảng Toán rời rạc: Chương 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! | 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 .
