Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị

Mời các bạn cùng tham khảoBài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị sau đây để hiểu rõ hơn về khái niệm đồ thị, biểu diễn đồ thị,một số đồ thị đặc biệt, đồ thị có hướng,... Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị TOÁN RỜI RẠCỨNG DỤNG TRONG TIN HỌC  Giảng viên:  Cao Thanh Tình (Email: tinhct@uit.edu.vn)  Bộ môn Toán Lý – ĐHCNTT – ĐHQGTPHCM 1 Nội dung môn học  Phần 1: Lý thuyết đồ thị  Đại cương về đồ thị  Các bài toán về đường đi  Đồ thị phẳng và bài toán tô màu đồ thị  Cây  Phần 2: Đại số Boole  Đại số Boole  Cổng logic  Cực tiểu hóa hàm BooleChương 1. Đại cương về đồ thị 2 Các khái niệm cơ bản  Đồ thị (Graph)  G = (V, E) với V≠∅  V: tập các đỉnh  E: tập các cạnh  Cạnh e∈E  ứng với 2 đỉnh u, v∈V  v, w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và w  Ký hiệu: e = vw (…)  u ≡ v: e được gọi là vòng (khuyên) tại uChương 1. Đại cương về đồ thị 3 Các khái niệm cơ bản  Đồ thị (Graph)  Cạnh bội (song song)  Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh B x  Đơn đồ thị A C  Đồ thị không có vòng và y z cạnh song song D  Đa đồ thị  Các đồ thị không phải là đơn đồ thịChương 1. Đại cương về đồ thị 4 Các khái niệm cơ bản  Đồ thị (Graph)  Đồ thị đầy đủ  Đồ thị mà mọi cặp đỉnh đều kề nhau  K : đơn đồ thị đầy đủ n  Đồ thị con  Đồ thị G’ = (V’, E’)  V’ ⊆ V, E’ ⊆ E  Đồ thị hữu hạn  E và V hữu hạn  Đồ thị vô hạnChương 1. Đại cương về đồ thị 5 Biểu diễn đồ thị  Biểu diễn hình học  Mỗi đỉnh ≡ một điểm  Mỗi cạnh ≡ một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nó  Biểu diễn bằng ma trận  Thường được dùng để biểu diễn trên máy tính  2 cách biểu diễn thường dùng  Ma trận kề  Ma trận liên thuộcChương 1. Đại cương về đồ thị 6 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ma trận vuông cấp n (số đỉnh của đồ thị)  Các phần tử aij được xác định bởi  aij = 1: Nếu vivj là một cạnh của G  aij = 0: Nếu vivj không là một cạnh của G  Tính chất  Phụ thuộc vào thứ tự liệt kê của các đỉnh  Ma trận là đối xứng  Một vòng được tính là một cạnh (akk = 1)Chương 1. Đại cương về đồ thị 7 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 1Chương 1. Đại cương về đồ thị 8 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 2 B D A B C D E A 0 1 1 0 0 B 1 0 1 1 1 A C D 1 1 0 1 2 0 1 1 1 2 C E E 0 1 2 2 0Chương 1. Đại cương về đồ thị 9 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận liên thuộc  Ma trận M = (mij)nxm  Các phần tử mij được xác định bởi  mij = 1: Nếu cạnh ej liên thuộc với vi của G  mij = 0: Nếu cạnh ej không liên thuộc với vi của G  Tính chất  Các cột tương ứng với các cạnh bội là giống nhau trong ma trân liên thuộc  Các vòng ứng với một cột có đúng một phần tử bằng 1 ứng với đỉnh nối với nó.Chương 1. Đại cương về đồ thị 10 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma liên thuộc  Ví dụChương 1. Đại cương về đồ thị 11 Biểu diễn đồ thị  Biểu diễn bằng bảng (danh sách liền kề)  Lưu trữ các đỉnh liền kề với một đỉnh Đỉn Đỉnh liền kề  Ví dụ h b c a b, c, e a b a c a, c, d, e e d d c, e e a, c, dChương 1. Đại cương về đồ thị 12 Các khái niệm cơ bản  Bậc của đỉnh  Đỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác. g f e  Ký hiệu: deg(v) hay d(v)  ...