Chương 6
CÂY
2
12/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Định nghĩa1
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ọilàrừng.
Ví dụ1
Rừng gồm ba cây T1, T2, T3.
3
12/05/2011
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị
Ví dụ2
G1,G
2là cây.
G3không là cây do có chứa chu trình.
G4không là cây do không liên thông.
4
12/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ứachutrìnhvàcón–1cạnh;
3. T liên thông và có n–1cạnh;
4. T liên thông và mỗicạnh củaTđềulàcầu;
5. Hai đỉnh bấtkỳcủaTđượcnốivới nhau bằng đúng một
đường điđơn;
6. T không chứa chu trình nhưng nếuthêmmộtcạnh bấtkỳvào
T thì ta sẽđược thêm đúng 1 chu trình.
5
12/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)
•Tachỉcầnchứng minh T có n-1 cạnh.
•XétT
nlà cây có n đỉnh. Ta sẽchứng minh quy nạptheon
– n = 2, Cây có 2 đỉnhthìcó1cạnh. Đúng.
–Giảsửmọi cây có k đỉnh thì sẽcó k-1 cạnh
–XétT
k+1 làcâycók+1đỉnh. Dễthấyrằng trong cây Tk+1 luôn tồn
tạiítnhất1đỉnh treo.
–Loạiđỉnh treo này (cùng vớicạnh nối) ra khỏiT
k+1 ta đượcđồ thị
T’ có k đỉnh. DễthấyT’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ếtquynạp, T’ có k đỉnh thì sẽcó k-1
cạnh. Vậy cây Tk+1 cókcạnh. (đpcm)
6.1 Định nghĩa – Tính chất
Lý thuyết đồ thị