›
›

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

Download
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
Cấu trúc dữ liệu và giải thuật  
Nguyễn Khánh Phương  
Computer Science department  
School of Information and Communication technology  
E-mail: [email protected].vn  
Course outline  
Chương 1. Các kiến thức cơ bản  
Chương 2. Thuật toán đệ quy  
Chương 3. Các cấu trúc dữ liệu cơ bản  
Chương 4. Cây  
Chương 5. Sắp xếp  
Chương 6. Tìm kiếm  
Chương 7. Cấu trúc dữ liệu đồ thị  
2
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
Chương 7. Cấu trúc dữ liệu đồ thị  
Nguyễn Khánh Phương  
Computer Science department  
School of Information and Communication technology  
E-mail: [email protected].vn  
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  
– Mạng giao thông  
– Mạng điện  
– Mạng cung cấp nước  
– Lập lịch  
– Tối ưu hóa luồng, thiết kế mạch  
– Phân tích gen DNA  
– Trò chơi máy tính  
– Thiết kế hướng đối tượng  
– ….  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
N i dung  
1. Một số khái niệm cơ bản của đồ thị  
2. Biểu diễn đồ thị  
3. Các thuật toán duyệt đồ thị  
4. Một số ứng dụng của tìm kiếm trên đồ thị  
5
N i dung  
1. Một số khái niệm cơ bản của đồ thị  
2. Biểu diễn đồ thị  
3. Các thuật toán duyệt đồ thị  
4. Một số ứng dụng của tìm kiếm trên đồ thị  
6
1. Một số khái niệm cơ bản của đồ thị  
1.1. Đồ thị vô hướng và có hướng  
1.2. Một số khái niệm cơ bản trên đồ thị  
1.3. Một số dạng đồ thị đặc biệt  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Đồ 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  
• Tập cạnh E là tập (họ) các bộ không có thứ tự dạng  
(u, v), với u, v V, u≠v  
(u, v)  
u
v
Đa đồ thị vô hướng  
Đơn đồ thị vô hướng  
(w, v)  
w
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Đơn đồ thị vô hướng (Simple Graph)  
• Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó  
V1={a, b, c, d, e, f, g, h},  
E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}.  
a
f
b
h
e
g
c
d
Đồ thị G1  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Đa đồ thị vô hướng (Multi Graphs)  
• Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó  
V2={a, b, c, d, e, f, g, h},  
E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e), (a,e), (a,e),  
(a, e), (d,b), (f,g)}.  
a
b
f
h
e
Cạnh lặp  
c
g
d
Đồ thị G2  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Đồ 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  
• Tập cung E là tập (họ) các bộ có thứ tự dạng  
(u, v), với u, v V, u≠v  
(v, u)  
(u, v)  
u
v
Đa đồ thị có hướng  
Đơn đồ thị có hướng  
(w, v)  
w
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Đơ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},  
E3={(a,b), (b,c), (c,b), (d,c), (a,d), (b, d), (a,e), (d,e), (e,a),  
(f,g), (g,f)}  
a
f
b
h
g
c
d
Đồ thị G3  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Đ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},  
E4={(a,b), (b,c), (c,b), (d,c), (a,d), (b, d), (a,e), (a,e),  
(d,e), (e,a), (f,g), (g,f)}  
a
b
f
h
e
c
g
d
Đồ thị G4  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Các loại đồ thị: Tóm tắt  
Loại  
Kiểu cạnh  
Có cạnh lặp?  
Đơn đồ thị vô hướng Vô hướng  
Đa đồ thị vô hướng Vô hướng  
Không  
Có  
Đơn đồ thị có hướng Có hướng  
Đa đồ thị có hướng Có hướng  
Không  
Có  
• Chú ý:  
Khuyên (loop)  
– Một dạng đồ thị ít sử dụng hơn, đó là giả đồ thị.  
Giả đồ thị là đa đồ thị mà trong đó có các  
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  
1. Một số khái niệm cơ bản trên đồ thị  
1.1. Đồ thị vô hướng và có hướng  
1.2. Một số khái niệm cơ bản trên đồ thị  
1.3. Một số dạng đồ thị đặc biệt  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
1.2. Một số khái niệm cơ bản trên đồ thị  
1.2.1. Kề  
1.2.2. Bậc của đỉnh  
1.2.3. Loại bỏ đỉnh  
1.2.4. Hợp của hai đồ thị  
1.2.5. Đồ thị con  
1.2.6. Đồ thị con bao trùm  
1.2.7. Đường đi và chu trình  
1.2.8. Tính liên thông  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
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:  
• u, v là kề nhau/lân cận/nối với nhau (adjacent / neighbors / connected).  
u
• Cạnh e là liên thuộc với hai đỉnh u và v.  
• Cạnh e nối (connect) u và v.  
e
• Các đỉnh u và v là các đầu mút (endpoints) của cạnh e.  
v
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.  
Ta nói:  
• u và v là kề nhau, u là kề tới v, v là kề từ u  
• e đi ra khỏi u, e đi vào v.  
e
• e nối u với v, e đi từ u tới 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  
1.2.2. Bậc của đỉnh (Degree of a Vertex)  
Giả sử G là đồ thị vô hướng, vV 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ó.  
• Đỉnh bậc 0 được gọi là đỉnh cô lập (isolated).  
• Đỉnh bậc 1 được gọi là đỉnh treo (pendant).  
• Các ký hiệu thường dùng: (G) = min {deg(v): v V},  
(G) = max {deg(v): v V}.  
deg(b) = 2  
b
deg(c) = 3  
c
deg(a) = 2  
a
deg(f) = 0  
f là đỉnh cô lập  
f
d
deg(e) = 3  
e
deg(d) = 3  
deg(g) = 1  
g là đỉnh treo  
g
(G) = min {deg(v): v V} = 0,  
(G) = max {deg(v): v V}= 3.  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
Định lý về các cái bắt tay (Handshaking Theorem)  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
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.  
• Bán bậc ra (out-degree) của v, deg(v), là số cạnh đi ra khỏi v.  
• 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  
của v.  
deg-(b) = 1  
deg+(b)= 1  
deg-(c) = 1  
deg+(c)= 2  
c
b
a
deg-(f) = 0  
deg+(f)= 0  
f
deg-(a) = 0  
deg+(a)= 2  
a- đỉnh nguồn  
d
e
deg-(d) = 2  
deg+(d)= 1  
deg-(e) = 2  
deg+(e)= 0  
NGUYỄN KHÁNH PHƯƠNG  
Bộ môn KHMT – ĐHBK HN  
e – đỉnh đích (target)  
Tải về để xem bản đầy đủ
pdf 214 trang yennguyen 19040 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 7: Cấu trúc dữ liệu đồ thị - Nguyễn Khánh Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_7_cau_truc_d.pdf