tailieunhanh - 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 .