Xem mẫu
- 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, 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ó.
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
nguon tai.lieu . vn
