Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Sau khi học xong chương 5 Đồ thị nằm trong bài giảng cấu trúc dữ liệu và giải thuật sinh viên có kiến thức về: những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị, đánh giá thuật toán và một số ứng dụng của đồ thị.

Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM) Chương 5: Đồ thị Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM Mục tiêu  Trình bày những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị  Đánh giá thuật toán  Một số ứng dụng của đồ thị Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 2 Định nghĩa Anchorage Boston Minneapolis Seattle Hartford SF Austin Atlanta Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 3 Định nghĩa  Đồ thị G = (V,E) V= tập hợp hữu hạn các phần tử (đỉnh hay nút) E  V × V, tập hữu hạn các cạnh (cung) a b Đỉnh c Cung d e Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 4 Các khái niệm  Nếu (x,y)  E  x gọi là đỉnh gốc, y là ngọn  Nếu x ≡ y, (x,y) gọi là khuyên  Một dãy u1, u2, …, un, ui  V (i=1,n) gọi là một đường, nếu (ui-1,ui)  E  Độ dài đường: length(u1,u2,…,un)=n  (u1,u2,…,un) đường đi đơn, nếu ui≠uj, 1Các khái niệm  Chu trình (cycle) = (u1,u2,…,un), u1≡ un  Đồ thị định hướng (directed graph)  (x,y)  E : (x,y) ≠ (y,x)  Đồ thị vô hướng  (x,y)  E : (y,x)  E  (x,y) ≡ (y,x) Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 6 Các khái niệm  CBDC là một chu trình B B C A C A Đường đi đơn D D Chu trình Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 7 Các khái niệm Đồ thị vô hướng Đồ thị định hướng Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 8 Các khái niệm  Tính liên thông (connectivity)  Trong đồ thị G, hai đỉnh x,y gọi là liên thông (connected), nếu có một đường từ x đến y  Đồ thị G liên thông, nếu (x,y)  E,  đường đi từ x đến y  Đồ thị G gọi là có trọng số, nếu mỗi cung được gán một giá trị số đặc trưng Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 9 Các khái niệm Đồ thị liên thông Đồ thị không liên thông Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 10 Các khái niệm  Đồ thị có trọng số 0 10 20 1 1 2 4 5 3 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 11 Biểu diễn đồ thị  Biểu diễn bằng ma trận kề  Adjacency matrice  Biểu diễn bằng danh sách kề  Adjacency list Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 12 Biểu diễn đồ thị bằng ma trận kề  Xét G=(V,E) với V={x1,…,xn}  Biểu diễn G bằng ma trận A = (aij), i,j = 1..n  aij = 1, nếu Ǝ (xi,xj)  E  aij = 0, nếu !Ǝ (xi,xj)  E Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 13 Biểu diễn đồ thị bằng ma trận kề A[i][j] 0 1 2 3 0 0 0 1 1 0 1 1 0 1 1 1 2 1 1 0 1 2 3 0 1 1 0 3 0 1 1 0 1 0 1 1 A= 1 1 0 1 0 1 1 0 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 14 Biểu diễn đồ thị bằng ma trận kề A[i][j] 0 1 2 3 0 0 ...