Bài giảng Lý thuyết đồ thị - Chương 6: Cây - Nguyễn Trần Phi Phượng

Chương 6
CÂY
212/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 1
Cây là đồ thị vô hướng, liên thông và không có chu
trình. Đồ thị không có chu trình gọi là rừng.
Ví dụ 1
Rừng gồm ba cây T1, T2, T3.
312/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Ví dụ 2
G1, G2 là cây.
G3 không là cây do có chứa chu trình.
G4 không là cây do không liên thông.
412/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định lý 1
Giả sử T=(V,E) là một đồ thị vô hướng n đỉnh. Khi đó, các
mệnh đề sau đây là tương đương:
1. T là cây;
2. T không chứa chu trình và có n – 1 cạnh;
3. T liên thông và có n – 1 cạnh;
4. T liên thông và mỗi cạnh của T đều là cầu;
5. Hai đỉnh bất kỳ của T được nối với nhau bằng đúng một
đường đi đơn;
6. T không chứa chu trình nhưng nếu thêm một cạnh bất kỳ vào
T thì ta sẽ được thêm đúng 1 chu trình.
512/05/2011
Chứng minh định lý
(1)⇒ (2): T là cây⇒ T không chứa chu trình và có n-1 cạnh.
• Hiển nhiên T không chứa chu trình (do T là cây)
• Ta chỉ cần chứng minh T có n-1 cạnh.
• Xét Tn là cây có n đỉnh. Ta sẽ chứng minh quy nạp theo n
– n = 2, Cây có 2 đỉnh thì có 1 cạnh. Đúng.
– Giả sử mọi cây có k đỉnh thì sẽ có k-1 cạnh
– Xét Tk+1 là cây có k + 1 đỉnh. Dễ thấy rằng trong cây Tk+1 luôn tồn
tại ít nhất 1 đỉnh treo.
– Loại đỉnh treo này (cùng với cạnh nối) ra khỏi Tk+1 ta được đồ thị
T’ có k đỉnh. Dễ thấy T’ vẫn liên thông và không có chu trình (do
Tk+1 không có chu trình)
– Suy ra T’ là cây. Theo giả thiết quy nạp, T’ có k đỉnh thì sẽ có k-1
cạnh. Vậy cây Tk+1 có k cạnh. (đpcm)
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
612/05/2011
Chứng minh định lý
(2)⇒ (3): T không chứa chu trình và có n-1 cạnh⇒ T liên thông và
có n-1 cạnh.
• Hiển nhiên T có n-1 cạnh (theo giả thiết)
• Ta chỉ cần chứng minh T liên thông.
• Giả sử T có k thành phần liên thông với số đỉnh lần lượt là n1,, nk.
• Khi đó mỗi thành phần liên thông của T sẽ là một cây và sẽ có số
cạnh lần lượt là n1-1, n2-1,, nk-1.
• Suy ra, số cạnh của T sẽ là n1-1 + n2-1 ++ nk-1 = n – k.
• Theo giả thiết, số cạnh của cây là n-1. Từ đó suy ra k = 1 hay T chỉ
có 1 thành phần liên thông. Suy ra T liên thông (đpcm).
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
712/05/2011
Chứng minh định lý
(3)⇒ (4): T liên thông và có n-1 cạnh⇒ T liên thông và mỗi cạnh
của T đều là cầu.
• Hiển nhiên T liên thông (theo giả thiết)
• Ta chỉ cần chứng minh mỗi cạnh của T đều là cầu.
• Xét (u,v) là cạnh bất kỳ của T. Nếu bỏ (u,v) ra khỏi T, ta sẽ được đồ
thị T’ có n đỉnh và n-2 cạnh.
• Ta đã chứng minh được đồ thị có n đỉnh và n-2 cạnh thì không thể
liên thông.
• Vậy nếu bỏ cạnh (u,v) ra thì sẽ làm mất tính liên thông của đồ thị.
Suy ra (u,v) là cầu. (đpcm).
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
812/05/2011
Chứng minh định lý
(4) ⇒ (5): T liên thông và mỗi cạnh của T đều là cầu ⇒ Giữa hai
đỉnh bất kỳ của T luôn tồn tại đúng 1 đường đi đơn.
• Xét u, v là hai đỉnh bất kỳ trong T.
• Do T liên thông nên luôn tồn tại đường đi giữa u và v. Ta sẽ chứng
minh đường đi này là duy nhất.
• Giả sử có hai đường đi đơn khác nhau giữa u và v. Khi đó hai
đường đi này sẽ tạo thành một chu trình.
• Suy ra, các cạnh trên chu trình này sẽ không thể là cầu được – Mâu
thuẫn.
• Vậy giữa u và v chỉ có thể tồn tại đúng 1 đường đi đơn. (đpcm)
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
912/05/2011
Chứng minh định lý
(5) ⇒ (6): Giữa hai đỉnh bất kỳ của T luôn tồn tại đúng 1 đường đi
đơn ⇒ T không chứa chu trình, nhưng nếu thêm vào 1 cạnh bất kỳ
thì sẽ phát sinh đúng 1 chu trình
• T không thể có chu trình, vì nếu có chu trình thì giữa hai đỉnh trên
chu trình này sẽ có 2 đường đi đơn khác nhau – mâu thuẫn với GT.
• Giả sử ta thêm vào T cạnh (u,v) bất kỳ (trước đó không có cạnh này
trong T).
• Khi đó cạnh này sẽ tạo với đường đi duy nhất giữa u và v trong T
tạo thành 1 chu trình duy nhất. (Vì nếu tạo thành 2 chu trình thì
chứng tỏ trước đó có 2 đường đi khác nhau giữa u và v – mâu thuẫn
với giả thiết)
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
1012/05/2011
Chứng minh định lý
(6) ⇒ (1): T không chứa chu trình, nhưng nếu thêm vào 1 cạnh bất
kỳ thì sẽ phát sinh đúng 1 chu trình⇒ T là cây
• Hiển nhiên T không chứa chu trình (theo giả thiết).
• Giả sử T không liên thông. Khi đó T sẽ có nhiều hơn 1 thành phần
liên thông
• Suy ra, nếu thêm vào một cạnh bất kỳ giữa hai đỉnh thuộc 2 thành
phần liên thông khác nhau sẽ không tạo thêm chu trình nào – mâu
thuẫn với giả thiết.
• Vậy, T phải liên thông. Suy ra T là cây. (đpcm)
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
1112/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 2
Cho T là một cây. Chọn một đỉnh r của cây gọi là gốc.
Vì có đường đi duy nhất từ gốc tới mỗi đỉnh của đồ thị nên
ta định hướng mỗi cạnh là hướng từ gốc đi ra. Cây cùng với
gốc sinh ra một đồ thị có hướng gọi là cây có gốc.
– Trong một cây có gốc r thì:
– deg-(r) = 0
– deg-(v) =1 với mọi đỉnh không phải là gốc.
1212/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 3
Cho cây có gốc r.
– Gốc r được gọi là đỉnh mức 0 (level 0).
– Các đỉnh kề với gốc r được xếp ở phía dưới gốc và gọi
là đỉnh mức 1 (level 1).
– Đỉnh sau của đỉnh mức 1 (xếp phía dưới đỉnh mức)gọi là
đỉnh mức 2.
– 
– Level (v) = k⇔ đường đi từ gốc r đến v qua k cung.
– Độ cao của cây là mức cao nhất của các đỉnh.
1312/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
-----------------------------------level 0
---------------------------------------level 1
--------------------------------------------level 2
-----------------------------------------------level 3
-------------------------------------------level 4
1412/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 4
Cho cây có gốc r.
a) Nếu uv là một cung của T thì u được gọi là cha của
v,còn v gọi là con của u.
b) Đỉnh không có con gọi là lá (hay đỉnh ngoài). Đỉnh
không phải là lá gọi là đỉnh trong.
c) Hai đỉnh có cùng cha gọi là anh em.
1512/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 5
Cho T là cây có gốc.
a) T được gọi là cây k-phân nếu mỗi đỉnh của T có nhiều
nhất là k con.
b) Cây 2-phân được gọi là cây nhị phân.
c) Cây k-phân đủ là cây mà mọi đỉnh trong có đúng k con.
d) Cây k-phân với độ cao h được gọi là cân đối nếu các
đỉnh đều ở mức h hoặc h – 1.
1612/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
2 3 4
105 6 7 8 9
11 12 13 14 15 16 17
1
1712/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 6
Cho T là cây nhị phân có gốc là r. Ta có thể biểu
diễn T như hình vẽ dưới với hai cây con tại r là TL và TR
,chúng lần lượt được gọi là cây con bên trái và cây con bên
phải của T.
r
TL TR
1812/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa 7
Độ dài đường đi trong và độ dài đường đi ngoài
Cho T là cây nhị phân đủ.
a) Độ dài đường đi trong là tổng tất cả các mức của các
đỉnh trong, ký hiệu IP(T).
b) Độ dài đường đi ngoài là tổng tất cả các mức của các lá,
ký hiệu EP(T).
1912/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
2 3
764 5
8 9
1
Ví dụ
Tính độ dài đường đi trong và độ dài đường đi ngoài của đồ
thị dưới đây:
2012/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
Định nghĩa 1
Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây
T=(V,F) với F⊆ E được gọi là cây khung (cây tối đại, cây
bao trùm) của đồ thị G.
Ví dụ
Đồ thị và các cây khung của nó
2112/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
Định nghĩa 2
Cho đồ thị có trọng số G. Cây khung nhỏ nhất của G (nếu
tồn tại) là cây khung có tổng trọng số nhỏ nhất trong số các
cây khung của G.
Thuật toán tìm cây khung nhỏ nhất
-Thuật toán Kruskal
-Thuật toán Prim
2212/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
Thuật toán Kruskal
Cho G là đồ thị liên thông, có trọng số, n đỉnh.
Bước 1. Trước hết chọn cạnh ngắn nhất e1 trong các
cạnh của G.
Bước 2. Khi đã chọn k cạnh e1,e2,ek thì chọn tiếp cạnh
ek+1 ngắn nhất trong các cạnh còn lại của G sao cho không
tạo thành chu trình với các cạnh đã chọn trước.
Bước 3. Chọn đủ n-1 cạnh thì dừng.
2312/05/2011
6 3
4
1 4
6
8
ua
6.2 Bài toán cây khung nhỏ nhất
Thuật toán Kruskal
Ví dụ
Lý thuyết đồ thị
d
b
c
2412/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
1
a
b
S1
Thuật toán Kruskal
Ví dụ
2512/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
1
a
b
S2
u d3
Thuật toán Kruskal
Ví dụ
2612/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
1
a
b
S3
u d3
4
Thuật toán Kruskal
Ví dụ
2712/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
1
a
b
S4
u d3
4
6
c
Thuật toán Kruskal
Ví dụ
2812/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
Trọng số Cạnh
1 (a,b)
3 (u,d)
4 (b,u)
4 (b,d)
6 (a,u)
6 (c,d)
8 (b,c)
Chọn
Chọn
Không chọn vì tạo chu trình: b u d b
Chọn
Chọn. Dừng vì đã đủ cạnh
Không chọn vì tạo chu trình: a b u a
6 3
41 4
6
8
ua d
b
c
Thuật toán Kruskal
Ví dụ
2912/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
Thuật toán Prim
Bước 1. Chọn một đỉnh bất kỳ v1 để có cây T1 chỉ gồm
một đỉnh.
Bước 2. Khi đã chọn cây Tk thì chọn tiếp cây Tk+1 =
Tk∪ ek+1. Trong đó ek+1 là cạnh ngắn nhất trong các cạnh có
một đầu mút thuộc Tk và đầu mút kia không thuộc Tk.
Bước 3. Chọn được cây Tn thì dừng.
3012/05/2011
6 3
4
1 4
6
8
ua
6.2 Bài toán cây khung nhỏ nhất
Thuật toán Prim
Ví dụ
Lý thuyết đồ thị
d
b
c
3112/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
T1
Thuật toán Prim
Ví dụ
c
3212/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
T2
Thuật toán Prim
Ví dụ
c
d
6
3312/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
T3
Thuật toán Prim
Ví dụ
c
d
6
3u
3412/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
T4
Thuật toán Prim
Ví dụ
c
d
6
3u
4
b
3512/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
6 3
41 4
6
8
ua d
b
c
T5
Thuật toán Prim
Ví dụ
c
d
6
3u
4
b
1
a
3612/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
Thuật toán Prim
Để biểu diễn lời giải, ta sẽ sử dụng 2 mảng:
– Mảng d: d[v] dùng để lưu độ dài cạnh ngắn nhất nối với v trong
số các cạnh chưa xét.
– Mảng near: near[v] dùng để lưu đỉnh còn lại (ngoài v) của cạnh
ngắn nhất nói ở trên. v d[v] near[v]
c 0 0
d 6 c
u 3 d
b 4 u
a 1 b
c
d
6
3u
4
b
1
a
3712/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
// Khởi tạo 
Chọn s là một đỉnh nào đó của đồ thị
VH = {s}; //Tập những đỉnh đã đưa vào cây 
T = ∅; //Tập cạnh của cây 
d[s] = 0; near[s] = s;
For v∈V\VH
{
d[v] = a[s,v];
near[v] = s;
}
//Bước lặp
Stop = False;
While (! Stop)
{
Tìm u∈V\VH thỏa mãn d[u] = min{d[v]: v∈V\VH};
VH = VH ∪ {u};
T = T∪ { (u, near[u]) };
If (|VH| = =n)
{
H = (VH, T) là cây khung của đồ thị;
Stop = True;
}
Else
For v ∈V\VH
If d[v] > a[u,v] then
{
d[v] = c[u,v];
near[v] = u;
}
}
3812/05/2011
6.2 Bài toán cây khung nhỏ nhất
Lý thuyết đồ thị
c
d
6
3u
4
b
1
a
Bước lặp Đỉnh c Đỉnh a Đỉnh b Đỉnh d Đỉnh u VH T
Khởi tạo [0,c] [∞,c] [8,c] [6,c]* [∞,c] a ∅
1 - [∞,c] [4,d] - [3,d]* c,d (d,c)
2 - [6,u] [4,d]* - - c,d,u (d,c),(u,d)
3 - [1,b]* - - - c,d,u,b (d,c),(u,d),(b,u)
4 - - - - - c,d,u,b,a (d,c),(u,d),(b,u), (a,b)
6 3
41 4
6
8
ua d
b
c