Bài giảng Toán rời rạc: Chương 7 - Dr. Ngô Hữu Phúc

Bài giảng Toán rời rạc: Chương 7 Đồ thị và cây, cung cấp cho người đọc những kiến thức như: giới thiệu chung; định nghĩa và khái niệm; một số dạng đồ thị đơn đặc biệt; biểu diễn đồ thị trên máy tính; các thuật toán tìm kiếm trên đồ thị;...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 7 - Dr. Ngô Hữu Phúc TOÁN RỜI RẠC @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University CHƯƠNG 7 ĐỒ THỊ VÀ CÂY Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 1 Mob: 098 5696 580 Email: ngohuuphuc76@mta.edu.vn NỘI DUNG @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2 7.1. GIỚI THIỆU CHUNG Nội dung chính của chương này đề cập đến những khái niệm cơ bản nhất của đồ thị, phương pháp biểu diễn đồ thị trên máy tính và một số khái niệm liên quan.  Các loại đồ thị vô hướng, đồ thị có hướng, đa đồ thị…  Khái niệm về bậc của đỉnh, đường đi, chu trình và tính liên thông của đồ thị.  Biểu diễn đồ thị bằng ma trận kề.  Biểu diễn đồ thị bằng danh sách kề.  Biểu diễn đồ thị bằng danh sách cạnh @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 3 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (1/17) 7.2.1. Mở đầu (1/2)  Lý thuyết đồ thị được đề xuất từ thế kỷ 18, bắt đầu từ bài báo của Euler công bố năm 1736 liên quan đến lời giải bài toán nổi tiếng về các cây cầu ở Konigsberg.  Cho tới nay, mối quan tâm đến lý thuyết đồ thị vẫn không hề suy giảm.  Lý do: phạm vi ứng dụng hết sức rộng rãi của đồ thị trong rất nhiều lĩnh vực khác nhau, bao gồm:  Trong tin học,  Hoá học,  Vận trù học,  Kỹ thuật điện,  Ngôn ngữ  Kinh tế… @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 4 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (2/17) 7.2.1. Mở đầu (2/2) Vậy đồ thị là gì? Có thể định nghĩa:  Đồ thị (Graph) là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. Chúng ta phân biệt đồ thị thông qua kiểu và số lượng cạnh nối giữa các cặp đỉnh của đồ thị. @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 5 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (3/17)  Định nghĩa 7.2.1.  Đồ thị vô hướng hoặc đồ thị G là một cặp có thứ tựG:=(V, E), trong đó:  V: tập các đỉnh hoặc nút,  E: tập các cặp không thứ tự chứa các đỉnh phân biệt, được gọi là cạnh. Hai đỉnh thuộc một cạnh được gọi là các đỉnh đầu cuối của cạnh đó. Chú ý: - V (và E) thường là các tập hữu hạn. - Phần lớn các kết quả nghiên cứu đã biết không đúng (hoặc khác) khi áp dụng cho đồ thị vô hạn (infinite graph) vì nhiều luận cứ Một đồ thị vô hướng với 6 đỉnh không dùng được trong trường hợp vô hạn. (nút) và 7 cạnh @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 6 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (4/17)  Định nghĩa 7.2.2.  Đồ thị có hướng G là một cặp có thứ tự G:=(V, A), trong đó  V: tập các đỉnh hoặc nút,  A: tập các cặp có thứ tự chứa các đỉnh, được gọi là các cạnh có hướng hoặc cung. Một cạnh e = (x, y) được coi là có hướng từ x tới y; x được gọi là điểm đầu/gốc và y được gọi là điểm cuối/ngọn của cạnh. Một đồ thị có hướng với 3 đỉnh (nút) và 3 cung @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 7 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (5/17)  Định nghĩa 7.2.3:  Đơn đồ thị vô hướng G =(V,E) là đồ thị vô hướng mà giữa hai đỉnh chỉ có tối đa một cạnh. Ví dụ về đơn đồ thị vô hướng - Mạng máy tính đơn kênh thoại @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 8 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (6/17)  Định nghĩa 7.2.4:  Đa đồ thị vô hướng G=(V,E) là đồ thị vô hướng mà giữa hai đỉnh có thể có nhiều hơn một cạnh. Ví dụ về đa đồ thị vô hướng - Mạng máy tính đa kênh thoại @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 9 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (7/17)  Định nghĩa 7.2.5:  Giả đồ thị vô hướng G=(V, E) là đồ thị vô hướng mà cạnh là cặp không có thứ tự gồm hai phần tử (hai phần tử không nhất thiết phải khác nhau) trong V.  Cạnh e được gọi là khuyên nếu có dạng e =(u, u), trong đó u là đỉnh nào đó thuộc V. Ví dụ về giả đồ thị vô hướng - Mạng máy tính đa kênh thoại có khuyên @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 10 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (8/17)  Định nghĩa 7.2.6:  Đơn đồ thị có hướng G = là đồ thị có hướng, trong đó, nếu v1 và v2 là hai đỉnh thì đồ thị chỉ được phép có tối đa một cung (v1, v2). Ví dụ về đơn đồ thị có hướng - Mạng máy tính có hướng @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 11 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (9/17)  Định nghĩa 7.2.7:  Đa đồ thị có hướng G = là đồ thị có hướng, trong đó nếu v1 và v2 là 2 đỉnh của đồ thị thì có thể có nhiều cung (v1,v2). Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp. Ví dụ về đa đồ thị có hướng - Mạng máy tính đa kênh có hướng @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 12 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (10/17) Bảng phân biệt các loại đồ thị @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 13 7.2. ĐỊNH NGHĨA VÀ KHÁI NIỆM (11/17)  Định nghĩa 7.2.8:  Hai đỉnh u và v của đồ thị vô hướng G = được gọi là kề nhau nếu (u,v) là cạnh thuộc đồ thị G.  Nếu e =(u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là ...