TAILIEUCHUNG - Bài giảng Toán rời rạc 2 - Biểu diễn đồ thị trên máy tính

Bài giảng "Toán rời rạc 2 - Biểu diễn đồ thị trên máy tính" cung cấp cho người học các kiến thức: Biểu diễn đồ thị bằng ma trận kề, biểu diễn đồ thị bằng ma trận liên thuộc, biểu diễn đồ thị bằng danh sách cạnh, biểu diễn đồ thị bằng danh sách kề. Mời các bạn cùng tham khảo. | Bài giảng Toán rời rạc 2 - Biểu diễn đồ thị trên máy tính BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH Toán rời rạc 2 Nội dung Biểu diễn đồ thị bằng ma trận kề Biểu diễn đồ thị bằng ma trận liên thuộc Biểu diễn đồ thị bằng danh sách cạnh Biểu diễn đồ thị bằng danh sách kề 2 Biểu diễn đồ thị bằng ma trận kề Ma trận kề của đồ thị vô hướng Xét đồ thị đơn vô hướng G với tập đỉnh V 1 2 . . . n tập cạnh E e1 e2 . em . Ta gọi ma trận kề của đồ thị G là ma trận có các phần tử hoặc bằng 0 hoặc bằng 1 theo qui định như sau 4 Tính chất ma trận kề đối với đồ thị vô hướng 5 Ma trận kề của đồ thị có hướng Định nghĩa hoàn toàn tương tự với đồ thị vô hướng Cần lưu ý tới hướng của cạnh Ma trận kề của đồ thị có hướng là không đối xứng 6 Tính chất của ma trận kề của đồ thị có hướng 7 Ma trận trọng số 8 Ưu amp nhược điểm của ma trận kề Ưu điểm Đơn giản dễ cài đặt trên máy tính Sử dụng một mảng hai chiều để biểu diễn ma trận kề Dễ dàng kiểm tra được hai đỉnh u v có kề với nhau hay không Đúng một phép so sánh a u v 0 Nhược điểm Lãng phí bộ nhớ bất kể số cạnh nhiều hay ít ta cần n2 đơn vị bộ nhớ để biểu diễn Không thể biểu diễn được với các đồ thị có số đỉnh lớn Để xem xét đỉnh đỉnh u có những đỉnh kề nào cần mất n phép so sánh kể cả đỉnh u là đỉnh cô lập hoặc đỉnh treo 9 Qui ước khuôn dạng lưu trữ ma trận kề Dòng đầu tiên ghi lại số đỉnh của đồ thị N dòng kế tiếp ghi lại ma trận kề của đồ thị. Hai phần tử khác nhau của ma trận kề được viết cách nhau một vài khoảng trống. 10 Biểu diễn đồ thị bằng ma trận liên thuộc Ma trận liên thuộc Đồ thị vô hướng 12 Ma trận liên thuộc Đồ thị có hướng 13 Biểu diễn đồ thị bằng danh sách cạnh Danh sách cạnh cung Trong trường hợp đồ thị thưa đồ thị có số cạnh m 6n người ta thường biểu diễn đồ thị dưới dạng danh sách cạnh. Ta lưu trữ danh sách tất cả các cạnh cung của đồ thị vô hướng có hướng . Mỗi cạnh cung e x y được tương ứng với hai biến dau e cuoi e . Như vậy để lưu trữ đồ thị ta cần 2m đơn vị bộ nhớ. Nhược điểm để nhận biết những cạnh nào kề với cạnh nào chúng .

• Toán học
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị trên máy tính
• Biểu diễn đồ thị
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• bài tập toán rời rạc
• lý thuyết toán rời rạc
• đề cương Toán rời rạc
• tìm hiểu Toán rời rạc
• Thuật toán Dijkstra
• Thuật toán Bellman Ford
• Bài toán tìm đường đi ngắn nhất
• Toán học rời rạc
• Cấu trúc rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Bài giảng Toán học rời rạc
• Tìm kiếm trên đồ thị
• Thuật toán tìm kiếm
• Ứng dụng của thuật toán tìm kiếm
• Công nghệ thông tin
• Giới thiệu môn học
• Trí tuệ nhân tạo
• Khái niệm về đồ thị
• Đđồ thị vô hướng
• Đồ thị có hướng
• Dạng đồ thị đặc biệt
• Đồ thị Euler
• Đồ thị Hamilton
• Chứng minh đồ thị là nửa Euler
• Toán rời rạc ứng dụng trong tin học
• Bài toán về đường đi
• Đường đi Euler
• Đường đi Hamilton
• Cây khung của đồ thị
• Hàm đơn ánh
• Độ tăng của hàm
• Thuật toán
• Thuật toán sắp xếp nổi bọt
• Hàm và thuật toán
• Độ phức tạp của thuật toán
• Nguyên lý bù trừ
• Hoán vị lặp
• Tổ hợp lặp
• Giải tích tổ hợp
• Hệ thức đệ qui
• Lý thuyết tập hợp
• Phép toán tập hợp
• Tích Descartes
• cơ sở dữ liệu
• hệ thống dữ liệu
• Bài giảng Hàm Bool
• Phép toán trên hàm Bool
• Dạng nối rời chính tắc của Hàm Bool
• Phương pháp biểu đồ Karnaugh
• Đồ thị vô hướng
• Biểu diễn đồ thị bằng ma trận kề
• Thuật toán tìm kiếm theo chiều sâu
• Bài giảng Quan hệ
• Quan hệ 2 ngôi
• Tính chất quan hệ 2 ngôi
• Tập hợp thương
• Bài giảng Toán rời rạc 1
• Toán rời rạc 1
• Bài toán liệt kê
• Thuật toán quay lui
• Thuật toán nhánh
• Nguyên lý Dirichlet
• Duyệt đồ thị
• Bài toán đường đi ngắn nhất
• Lý thuyết đồ thị
• Bài toán luồng cực đại