Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 7 - Nguyễn Khánh Phương

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:214

Thêm vào BST

Báo xấu

62
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 7 - Đồ thị. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Một số khái niệm cơ bản của đồ thị, biểu diễn đồ thị, các thuật toán duyệt đồ thị, một số ứng dụng của tìm kiếm trên đồ thị. Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 7 - Nguyễn Khánh Phương

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và giải thuật an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Course outline Chương 1. Các kiến thức cơ bản om Chương 2. Thuật toán đệ quy .c Chương 3. Các cấu trúc dữ liệu cơ bản ng co Chương 4. Cây an Chương 5. Sắp xếp th ng Chương 6. Tìm kiếm o du Chương 7. Cấu trúc dữ liệu đồ thị u cu 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co an Chương 7. Cấu trúc dữ liệu đồ thị th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Các ứng dụng thực tế của đồ thị • Có tiềm năng ứng dụng trong nhiều lĩnh vực: – Mạng máy tính om – Mạng giao thông .c – Mạng điện ng – Mạng cung cấp nước co – Lập lịch an – Tối ưu hóa luồng, thiết kế mạch th ng – Phân tích gen DNA o – Trò chơi máy tính du – Thiết kế hướng đối tượng u cu – …. NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Một số khái niệm cơ bản của đồ thị om 2. Biểu diễn đồ thị .c 3. Các thuật toán duyệt đồ thị ng co 4. Một số ứng dụng của tìm kiếm trên đồ thị an th o ng du u cu 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Một số khái niệm cơ bản của đồ thị om 2. Biểu diễn đồ thị .c 3. Các thuật toán duyệt đồ thị ng co 4. Một số ứng dụng của tìm kiếm trên đồ thị an th o ng du u cu 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1. Một số khái niệm cơ bản của đồ thị 1.1. Đồ thị vô hướng và có hướng om 1.2. Một số khái niệm cơ bản trên đồ thị .c 1.3. Một số dạng đồ thị đặc biệt ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đồ thị vô hướng (Undirected Graphs) Định nghĩa. Đơn (đa) đồ thị vô hướng G = (V,E) là cặp gồm: • Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh om • Tập cạnh E là tập (họ) các bộ không có thứ tự dạng .c (u, v), với u, v  V, u≠v ng co an th ng (u, v) o u v Đa đồ thị vô hướng du u Đơn đồ thị vô hướng cu (w, v) w NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đơn đồ thị vô hướng (Simple Graph) • Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó V1={a, b, c, d, e, f, g, h}, om E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}. .c ng co a f an b th h e ng g o c du d u cu Đồ thị G1 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đa đồ thị vô hướng (Multi Graphs) • Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó V2={a, b, c, d, e, f, g, h}, om E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e), (a,e), (a,e), .c (a, e), (d,b), (f,g)}. ng co an a th ng b f o h du e Cạnh lặp c u g cu d Đồ thị G2 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đồ thị có hướng (Directed Graph) Định nghĩa. Đơn (đa) đồ thị có hướng G = (V,E) là cặp gồm: • Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh om • Tập cung E là tập (họ) các bộ có thứ tự dạng .c (u, v), với u, v  V, u≠v ng co an th (v, u) ng (u, v) o u v Đa đồ thị có hướng du u cu (w, v) Đơn đồ thị có hướng w NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đơn đồ thị có hướng (Simple digraph) • Ví dụ: Đơn đồ thị có hướng G3= (V3, E3), trong đó V3={a, b, c, d, e, f, g, h}, om E3={(a,b), (b,c), (c,b), (d,c), (a,d), (b, d), (a,e), (d,e), (e,a), .c (f,g), (g,f)} ng co an th a ng f b o h du e u g cu c d Đồ thị G3 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đa đồ thị có hướng (Multi Graphs) • Ví dụ: Đa đồ thị có hướng G4= (V4, E4), trong đó V4={a, b, c, d, e, f, g, h}, om E4={(a,b), (b,c), (c,b), (d,c), (a,d), (b, d), (a,e), (a,e), .c (d,e), (e,a), (f,g), (g,f)} ng co an a th b ng f o h du e c u g cu d Đồ thị G4 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Các loại đồ thị: Tóm tắt Loại Kiểu cạnh Có cạnh lặp? om Đơn đồ thị vô hướng Vô hướng Không .c Đa đồ thị vô hướng Vô hướng Có ng co Đơn đồ thị có hướng Có hướng Không an Đa đồ thị có hướng Có hướng Có th ng • Chú ý: o du Khuyên (loop) – Một dạng đồ thị ít sử dụng hơn, đó là giả đồ thị. u Giả đồ thị là đa đồ thị mà trong đó có các cu khuyên (cạnh nối 1 đỉnh với chính nó). NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
1. Một số khái niệm cơ bản trên đồ thị 1.1. Đồ thị vô hướng và có hướng om 1.2. Một số khái niệm cơ bản trên đồ thị .c 1.3. Một số dạng đồ thị đặc biệt ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
1.2. Một số khái niệm cơ bản trên đồ thị 1.2.1. Kề om 1.2.2. Bậc của đỉnh .c 1.2.3. Loại bỏ đỉnh ng co 1.2.4. Hợp của hai đồ thị an 1.2.5. Đồ thị con th ng 1.2.6. Đồ thị con bao trùm o du 1.2.7. Đường đi và chu trình u cu 1.2.8. Tính liên thông NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
1.2.1. Kề (Adjacency) Cho G là đồ thị vô hướng với tập cạnh E. Giả sử e=(u,v) là cạnh của G. Khi đó ta nói: om • u, v là kề nhau/lân cận/nối với nhau (adjacent / neighbors / connected). .c • Cạnh e là liên thuộc với hai đỉnh u và v. u e ng • Cạnh e nối (connect) u và v. co • Các đỉnh u và v là các đầu mút (endpoints) của cạnh e. v an th ng Cho G là đồ thị có hướng (có thể là đơn hoặc đa). Giả sử e = (u,v) là cạnh của G. o Ta nói: du • u và v là kề nhau, u là kề tới v, v là kề từ u u • e đi ra khỏi u, e đi vào v. u cu e • e nối u với v, e đi từ u tới v v • Đỉnh đầu (initial vertex) của e là u • Đỉnh cuối (terminal vertex) của e là v NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
1.2.2. Bậc của đỉnh (Degree of a Vertex) Giả sử G là đồ thị vô hướng, vV là một đỉnh nào đó của G: • Bậc của đỉnh v, deg(v), là số cạnh kề với nó. om • Đỉnh bậc 0 được gọi là đỉnh cô lập (isolated). .c • Đỉnh bậc 1 được gọi là đỉnh treo (pendant). ng • Các ký hiệu thường dùng: (G) = min {deg(v): v  V}, co (G) = max {deg(v): v  V}. an deg(b) = 2 b th ng c deg(c) = 3 deg(a) = 2 a o du deg(f) = 0 f f là đỉnh cô lập u d e cu deg(e) = 3 deg(d) = 3 deg(g) = 1 (G) = min {deg(v): v  V} = 0, g g là đỉnh treo NGUYỄN KHÁNH PHƯƠNG (G) = max {deg(v): v  V}= 3. Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Định lý về các cái bắt tay (Handshaking Theorem) om .c ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
Bậc của đỉnh của đồ thị có hướng Cho G là đồ thị có hướng, v là đỉnh của G: • Bán bậc vào (in-degree) của v, deg(v), là số cạnh đi vào v. om • Bán bậc ra (out-degree) của v, deg(v), là số cạnh đi ra khỏi v. .c • Bậc của v, deg(v)=deg(v)+deg(v), là tổng của bán bậc vào và bán bậc ra ng của v. co deg-(b) = 1 deg+(b)= 1 deg-(c) = 1 an b c deg+(c)= 2 th o ng du a deg-(f) = 0 f u deg-(a) =0 deg+(f)= 0 cu deg+(a)= 2 d e a- đỉnh nguồn deg-(d) = 2 deg-(e) = 2 deg+(d)= 1 deg+(e)= 0 NGUYỄN KHÁNH PHƯƠNG e – đỉnh đích (target) Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt