CHƯƠNG 6
CÂY
Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM
Nội dung
Khái niệm Cây Các tính chất cơ bản của Cây
Cây khung của đồ thị Cây khung nhỏ nhất
Khái niệm cây
Định nghĩa Cây (Tree): Cây là
Đồ̀ thị vô hướng, liên thông và không có chu trình
B E B E F F
A A
C D C D
G2
G1
Khái niệm cây
Định nghĩa Rừng (Forest): Rừng là đồ thị không có chu trình
B G I L
J C A F K
• Nhận xét: Rừng là đồ thị mà mỗi thành phần
liên thông của nó là một cây.
D E H
Các tính chất cơ bản của Cây
Định lý: Cho đồ̀ thị vô hướng G=(V, E) có n đỉnh. Các mệnh đề̀ sau tương đương: (1) G là 1 cây (2) G không chứa chu trình và có n-1 cạnh (3) G liên thông và có n-1 cạnh (4) G liên thông và mỗi cạnh của nó điều là cầu (5) Giữa hai đỉnh bất kỳ của G được nối với nhau bởi đúng một đường đi duy nhất (6) G không chứa chu trình nhưng khi thêm vào một cạnh ta thu được đúng một chu trình
Các tính chất cơ bản của Cây
Sơ đồ chứng minh:
Chứng minh:
:
Các tính chất cơ bản của Cây
Chứng minh
Các tính chất cơ bản của Cây
Chứng minh
Các tính chất cơ bản của Cây
Chứng minh
Các tính chất cơ bản của Cây
Chứng minh
Các tính chất cơ bản của Cây
Chứng minh
Cây khung của đồ thị
D C
Định nghĩa Cây khung (spanning tree) của đồ̀ thị: Một cây T gọi là cây khung (cây bao trùm) của đồ thị G=(V, E) nếu
T = (V,E’) E’ E
F A
C D B E
C D
F A
F A
B E
B E
Cây khung của đồ thị
Định lý Cayley
Số cây khung của đồ thị (cid:3041) là (cid:3041)(cid:2879)(cid:2870)
a
n=4, số cây khung là: 4(cid:2872)(cid:2879)(cid:2870) (cid:3404) 16
f
b
d
c
Ví dụ: abc, bcd, cda, dab abf, acf, bdf, ...
e
n=5, Số cây khung là: 5(cid:2873)(cid:2879)(cid:2870) (cid:3404) 125
A
C B
E D
Cây khung của đồ thị
Bài toán: Cho G là đồ thị vô hướng, liên thông, hãy tìm 1 cây khung của đồ thị
Lời giải
Thuật toán tìm kiếm theo chiều sâu (DFS) Thuật toán tìm kiếm theo chiều rộng (BFS)
Cây khung của đồ thị
Tìm cây khung theo DFS
void SpanningTree_DFS(int u) {
1. Đánh dấu u đã viếng thăm 2. Xét mọi đỉnh v chưa được viếng thăm và kề u, với
từng đỉnh v đó
{
T = T {(u, v)} DFS(v);
}
}
Cây khung của đồ thị
Tìm cây khung theo BFS
void SpanningTree_BFS() {
<1. Khởi tạo>
- Đánh dấu mọi đỉnh chưa viếng thăm - Đánh dấu u=0 đã viếng thăm - q.Enqueue(u)
<2. Lặp> while (q!=) {
- u = q.Dequeue(); - Tìm tất cả đỉnh v chưa viếng thăm và kề u {
+ T = T {(u, v)} + Thăm đỉnh v + q.Enqueue(v)
}
}
}
Cây khung nhỏ nhất
Phát biểu bài toán Cây khung nhỏ nhất (Minimum Spanning Tree – MST):
, đạt giá trị nhỏ nhất
Cho G=(V, E) là đồ thị vô hướng, liên thông và có trọng số. Hãy tìm 1 cây khung T=(V, E’) của đồ thị G sao cho tổng trọng số các cạnh của T là nhỏ nhất. Hay nói cách khác: Tìm E’ sao cho độ dài của cây T,
𝑤 𝑇 (cid:3404) (cid:3533) 𝑤(cid:4666)𝑢, 𝑣(cid:4667) (cid:4666)(cid:3048),(cid:3049)(cid:4667)∈(cid:3006)
Cây khung nhỏ nhất
Thuật toán tìm cây khung nhỏ nhất
Có nhiều thuật toán xây dựng cây khung nhỏ nhất: • Thuật toán Boruvka • Thuật toán Kruskal • Thuật toán Jarnik – Prim • Phương pháp Dijkstra • Thuật toán Cheriton – Tarjan • Thuật toán Chazelle • …
Cây khung nhỏ nhất
Thuật toán tìm cây khung nhỏ nhất
Thuật toán Kruskal: Ý tưởng của thuật toán Kruskal: • Ban đầu cây T=(V, Ø) (Cây rỗng) • Lần lược chọn đủ (n‐1) cạnh có trọng số từ nhỏ đến lớn
vào cây T sao cho không được tạo thành chu trình
Thuật toán Jarnik – Prim: Ý tưởng của thuật toán Jarnik – Prim: • Ban đầu cây T chỉ có 1 đỉnh. • Lần lược chọn thêm (n‐1) đỉnh vào cây T sao cho đỉnh
được chọn vào cây có cạnh đến một trong các đỉnh của cây là là nhỏ nhất
Cây khung nhỏ nhất
Thuật toán Kruskal Input: G=(V, E) Output: Danh sách cạnh cay[]
Bước 1 (Sắp xếp) Sắp xếp các cạnh có trọng số tang dần
Bước 2 (Chọn n‐1 cạnh) Xét các cạnh theo thứ tự đã sắp xếp (cạnh nhỏ chọn trước). Chọn (n-1) cạnh theo quy tắc:
• Cạnh được chọn và cùng các cạnh đã chọn trước đó
không tạo thành chu trình
Cây khung nhỏ nhất
Ví dụ: Dùng thuật toán Kruskal để (cid:416)m cây khung nhỏ nhất của đồ thị sau:
7
H
C
6
6
G
2
6
9
3
B
8
6
2
F K D
1
5
4
3
9
A
5
J
6
5
7
E I
4
Cây khung nhỏ nhất
Cấu trúc dữ liệu
LinkedList> edgeList;
int m;
int n;
LinkedList> spanningTree;
bool[,] connected;
connected[u][v] cho biết đỉnh u có liên thông với v không: • connected[u][v] = true nếu u và v liên thông với nhau
v
u
Cây khung nhỏ nhất
Vấn đề: Chúng ta phải cập nhật bảng connected[][] này như thế nào?
v
u
y
x
Lúc u và v chưa nối thì {x} và {y} chưa liên thông. Nếu nối u với v thì phải cập nhật các đỉnh {x} liên thông với các đỉnh {y}
– Chúng ta dùng for toàn bộ bên x và bên y để cập nhật mảng
connected[][]
Cây khung nhỏ nhất
Thuật toán Kruskal tóm tắt
Bước 1 (Sắp xếp) Sắp xếp các cạnh theo thứ tự tăng dần về trọng số
Bước 2: Lặp (n‐1) lần Xét các cạnh theo thứ tự đã sắp xếp (cạnh nhỏ xét trước). • [Tìm cạnh]: Tìm cạnh (u, v) không liên thông đưa vào T • [Cập nhật]: Cập nhật 2 miền liên thông chứa đỉnh {u} và
{v} tương ứng thành 1 miền
Cây khung nhỏ nhất
void Kruskal() {
}
Cây khung nhỏ nhất
Một số cách kiểm tra 2 đỉnh có liên thông hay không:
Dùng mảng 2 chiều: int connected[][]; connected[i][j] = true nếu i liên thông j (=0 ngược lại)
Dùng mảng 1 chiều: int connected[]; connected[i] = connected[j] thì i liên thông j
Dùng Union‐Find set
Cây khung nhỏ nhất
Thuật toán Jarnik – Prim
Bước 1: Chọn đỉnh x0 bất kỳ và đánh dấu x0
Bước 2: Lặp (n-1) lần • Chọn cạnh (x, y) thỏa điều kiện:
– x đã đánh dấu – y chưa đánh dấu – Độ dài cạnh (x, y) ngắn nhất
• Đánh dấu y
Cây khung nhỏ nhất
Thuật toán Jarnik – Prim
Bước 1: Chọn đỉnh x0 bất kỳ và và đưa vào cây (đánh dấu x0)
Bước 2: Lần lượt nạp (n-1) đỉnh còn lại (tương ứng n‐1 cạnh ) vào cây bằng cách: • Chọn cạnh (x, y) thỏa điều kiện:
– x thuộc cây (x đã đánh dấu) – y chưa thuộc cây (y chưa đánh dấu) – Độ dài cạnh (x, y) nhỏ nhất
• Đánh dấu y
Cây khung nhỏ nhất
Ví dụ: Dùng thuật toán Prim để (cid:416)m cây khung nhỏ nhất của đồ thị sau:
7
H
C
6
6
G
2
6
9
3
B
8
6
2
F K D
1
5
4
3
9
A
5
J
6
5
7
E I
4
Cây khung nhỏ nhất
void Jarnik_Prim() {
}
Cây khung nhỏ nhất
Bài toán “Tìm cây khung lớn nhất”
Cách 1: • Đổi dấu các cạnh của đồ thị • Áp dụng thuật toán Kruskal hay Prim
Cách 2: Chỉnh sửa thuật toán Kruskal hay Prim bằng cách Chọn cạnh lớn trước, cạnh nhỏ sau
