tailieunhanh - 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! | 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 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 . Biểu diễn đồ thị bằng ma trận kề . 3 . Đọ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 . Các chỉ số và tính chất cơ bản về đỉnh và cạnh loại đồ thị . 4 . 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 . Giới thiệu gói networkx . 5 . 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. . 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