Thực hành Toán rời rạc - Chương 7: Đồ thị và các tính chất của đồ thị

Thực hành Toán rời rạc - Chương 7: Đồ thị và các tính chất của đồ thị. Chương này cung cấp cho học viên những nội dung về: biểu diễn đồ thị trong Python; một số đặc trưng và tính chất của đồ thị; sử dụng gói networkx để giải các bài toá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:
Thực hành Toán rời rạc - Chương 7: Đồ thị và các tính chất của đồ thị Bộ môn Khoa học Dữ liệu THỰC HÀNH TOÁN RỜI RẠC TÀI LIỆU PHỤC VỤ SINH VIÊN NGÀNH KHOA HỌC DỮ LIỆU Nhóm Giảng viên biên soạn: TS. Hoàng Lê Minh – Khưu Minh Cảnh – Hoàng Thị Kiều Anh – Lê Ngọc Thành – Phạm Trọng Nghĩa –Nguyễn Công Nhựt – Trần Ngọc Việt – Đỗ Đình Thủ – Nguyễn Hữu Trí Nhật – Lê Công Hiếu – Nguyễn Thị Thanh Bình – Nguyễn Thái Hải – Huỳnh Thái Học và các Giảng viên khác TP.HCM – Năm 2020 Thực hành Toán rời rạc Trang 1 Bộ môn Khoa học Dữ liệu MỤC LỤC CHƯƠNG 7: ĐỒ THỊ VÀ CÁC TÍNH CHẤT CỦA ĐỒ THỊ..................................................................... 3 1. Biểu diễn đồ thị trong Python ............................................................................................................... 3 1.1. Biểu diễn đồ thị bằng ma trận kề .................................................................................................. 3 1.2. [Đọc thêm] Sử dụng cấu trúc dữ liệu của Python ......................................................................... 3 2. Một số đặc trưng và tính chất của đồ thị ............................................................................................... 4 2.1. Các chỉ số và tính chất cơ bản về đỉnh và cạnh, loại đồ thị .......................................................... 4 2.2. Các thuộc tính của đồ thị............................................................................................................... 4 3. Sử dụng gói networkx để giải các bài toán đồ thị ................................................................................. 5 3.1. Giới thiệu gói networkx ................................................................................................................ 5 3.2. Tạo lập đồ thị vô hướng với networkx .......................................................................................... 6 BÀI TẬP CHƯƠNG 7 .................................................................................................................................. 8 Thực hành Toán rời rạc Trang 2 Bộ môn Khoa học Dữ liệu CHƯƠNG 7: ĐỒ THỊ VÀ CÁC TÍNH CHẤT CỦA ĐỒ THỊ Mục tiêu: - Khái niệm về biểu diễn đồ thị trong Python - Định nghĩa về sự liên thông của đồ thị. - Xử lý về đường đi, chu trình của đồ thị bằng Python. - Khai phá các tính chất của đồ thị thông qua gói networkx của Python Nội dung chính: 1. Biểu diễn đồ thị trong Python Hiện tại, một đồ thị được biểu diễn bằng nhiều dạng trong các ngôn ngữ lập trình. Dưới đây, hai dạng cơ bản trong ngôn ngữ Python được giới thiệu. 1.1. Biểu diễn đồ thị bằng ma trận kề Ma trận kề là hình thức biểu diễn đồ thị đơn giản nhất. Ma trận kề là ma trận vuông nxn với n là số đỉnh của đồ thị. Các quy tắc biểu diễn một ma trận kề = ,1 ≤ ≤ ,1 ≤ ≤  Ma trận gồm n dòng và n cột tương ứng với đồ thị n đỉnh.  Giá trị của thể hiện một hoặc nhiều dạng thông tin dưới đây: - Sự kết nối (đối với đồ thị chỉ quan tâm đến kết nối): giá trị khác 0 để cho biết có sự kết nối từ đỉnh đến đỉnh . - Chiều dài/giá trị/hàm phạt/khả năng tiếp cận từ đỉnh đến đỉnh (giá trị vô cùng xem như hai đỉnh không có sự kết nối trực tiếp; giá trị 0 cho thấy hai đỉnh trùng nhau; giá trị âm cho thấy đây là kết nối ngược chiều); - Dạng đồ thị: đồ thị có hướng thường các cạnh ngược hướng sẽ có giá trị âm (nghĩa là: = − ). Tuy nhiên, nhược điểm của phương pháp thể hiện này là: việc thể hiện đồ thị lớn và đặc biệt là thưa sẽ tốn rất nhiều tài nguyên. Do ma trận tăng mũ 2 theo kích thước của số đỉnh. 1.2. [Đọc thêm] Sử dụng cấu trúc dữ liệu của Python Sinh viên tham khảo thêm và thực hành trực tuyến tại đây với sự hỗ trợ của giảng viên: https://www.python-course.eu/graphs_python.php Thực hành Toán rời rạc Trang 3 Bộ môn Khoa học Dữ liệu 2. Một số đặc trưng và tính chất của đồ thị Dưới đây là một số chỉ số về đặc trưng cũng như các tính chất của một đồ thị/mạng. 2.1. Các chỉ số và tính chất cơ bản về đỉnh và cạnh, loại đồ thị Để đánh giá mức độ phức tạp và sự kết nối trong cục bộ của một đồ thị/mạng:  Chỉ số : là tỉ số giữa số liên kết thực sự và số liên kết có thể có trong mạng. Công thức: = = , : ố đỉ ℎ ℎ ặ! ú# !ủ %ạ ' 3( − 2) Nhận xét: - (ngưỡng ít liên kết) 0 ≤ ≤ 1 (ngưỡng nhiều liên kết)  Chỉ số ): là tỉ số giữa số lượng vòng thực sự và số lượng vòng cực đại trong mạng (Vòng liên kết giữa 3 đỉnh, không tính vòng bao trùm). ...