Bài giảng Toán rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (Phần 1) (ĐH Công nghệ Thông tin)

Bài giảng "Toán rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (Phần 1)" cung cấp cho người đọc các kiến thức: Các khái niệm cơ bản, biểu diễn đồ thị, một số đồ thị đặc biệt, sự đẳng cấu của các đồ thị, đồ thị có hướng, đường đi và chu trình, sự liên thông. Mời các bạn cùng tham khảo 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 - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (Phần 1) (ĐH Công nghệ Thông tin) CHƯƠNG 5: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊPHẦN 1:- Các khái niệm cơ bản- Biểu diễn đồ thị- Một số đồ thị đặc biệt- Sự đẳng cấu của các đồ thị- Đồ thị có hướng- Đường đi và chu trình- Sự liên thông 1 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 v, w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 (…)  v w : e được gọi là vòng (khuyên) tại vChương 1. Đại cương về đồ thị 2 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ị 3 Các khái niệm cơ bản  Đồ thị (Graph)  Đồ thị đầy đủ  Đồ thị mà mọi cặp đỉnh đều kề nhau  Kn: đơn đồ thị đầy đủ  Đồ 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ị 4 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ị 5 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ử a ij được xác định bởi  a ij  1 : Nếu v i v j là một cạnh của G  a ij  0: Nếu v i v j 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ị 6 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ị 7 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 1 1 0 1 2 D 0 1 1 1 2 C E E 0 1 2 2 0Chươ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 liên thuộc  Ma trận M = ( a ij )nxm  Các phần tử a ij được xác định bởi  a ij  1 : Nếu cạnh e j liên thuộc với vi của G  a: ij  0 : Nếu cạnh e j 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 vòng đó.Chương 1. Đại cương về đồ thị 9 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma liên thuộc  Ví dụ e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 0 0 0 0 v2 0 1 1 1 0 1 1 0 v3 0 0 0 1 1 0 0 0 v4 0 0 0 0 0 0 1 1 v5 0 0 0 0 1 1 0 0Chương 1. Đại cương về đồ thị 10 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 Đỉnh Đỉnh liền kề  Ví dụ a b, c, e b a c b a c a, c, d, e d c, e e d e a, c, dChương 1. Đại cương về đồ thị 11 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)  Mỗi vòng được kể là 2 cạnh tới một đỉnh  Đỉnh cô lập  deg(v)=0 a b c d  Đỉnh treo  deg(v)=1  Cạnh treo có đầu mút là một đỉnh treo  Đồ thị rỗng: deg(v)=0 vChương 1. Đại cương về đồ thị 12 Các khái niệm cơ bản  Bậc của đỉnh  Định lý 1.1  Trong mọi đồ thị G = (V, E), tổng số bậc của các đỉnh của G bằng 2 lần số cạnh của nó  Hệ quả  Trong mọi đồ thị G = (V, E) ta có  Số đỉnh bậc lẻ là một số chẵn  Tổng bậc của đỉnh bậc lẻ là một số chẵnChương 1. Đại cương về đồ thị 13 Các khái niệm cơ bản  Bậc của đỉnh  Định lý 1.2  Trong mọi đơn đồ thị G = (V, E), nếu số đỉnh nhiều hơn 1 thì tồn tại ít nhất hai đỉnh cùng bậc.  Định lý 1.3  Trong mọi đơn đồ thị G = (V, E), nếu số đỉnh nhiều hơn 2 và có đún ...