Định nghĩa
Ta nói rằng đồ thị T là một cây nếu nó có hai tính chất:
(T1) T liên thông;
(T2) T không có chu trình.
Các cây với 1; 2 hoặc 3 đỉnh
Có hai cây với 4 đỉnh
Có ba cây với 5 đỉnh
Mệnh đề
Nếu T = (V; E) là một cây với ít nhất hai đỉnh, thì với mỗi cặp
đỉnh x; y có duy nhất một đường đi từ x tới y.
Chứng minh.
Vì T liên thông nên có đường đi từ x tới y. Nếu có đường đi khác
từ x tới y, vậy thì ta có chu trình
46 trang |
Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 717 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Bài 5: Cây - Trần Vĩnh Đức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Cây
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
1 / 46
Tài liệu tham khảo
▶ Norman L. Biggs, Discrete Mathematics, Oxford University
Press, 2002.
▶ L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics:
Elementary and Beyond, Springer-Verlag New York, 2003.
▶ K. H. Rosen, Toán học rời rạc ứng dụng trong tin học.
2 / 46
Nội dung
Một số tính chất của cây
Đếm cây gán nhãn
Định nghĩa
Ta nói rằng đồ thị T là một cây nếu nó có hai tính chất:
(T1) T liên thông;
(T2) T không có chu trình.
Ví dụ
4 / 46
Các cây với 1, 2 hoặc 3 đỉnh
5 / 46
Có hai cây với 4 đỉnh
6 / 46
Có ba cây với 5 đỉnh
7 / 46
Bài tập
Ta biết rằng có sáu cây (đôi một không đẳng cấu) với sáu đỉnh;
hãy vẽ chúng.
8 / 46
Mệnh đề
Nếu T = (V,E) là một cây với ít nhất hai đỉnh, thì với mỗi cặp
đỉnh x, y có duy nhất một đường đi từ x tới y.
Chứng minh.
Vì T liên thông nên có đường đi từ x tới y. Nếu có đường đi khác
từ x tới y, vậy thì ta có chu trình
x
y
Mâu thuẫn với định nghĩa của cây.
9 / 46
Bài tập
Hãy chứng minh rằng tính chất:
(T3) với mỗi cặp đỉnh x, y có duy nhất một đường đi từ x tới y;
kéo theo cả hai tính chất:
(T1) T liên thông; và
(T2) T không có chu trình.
10 / 46
Mệnh đề
Nếu T = (V,E) là một cây với ít nhất hai đỉnh, thì đồ thị thu
được từ T bằng cách xóa đi một cạnh bất kỳ sẽ có hai thành phần
liên thông, mỗi thành phần là một cây.
11 / 46
Mệnh đề
Nếu T = (V,E) là một cây thì |E| = |V| − 1.
1
2 3 4
5 6 7 8
9
12 / 46
Chứng minh bằng quy nạp mạnh
Đặt P(n) = “Cây với n đỉnh có n− 1 cạnh”
Bước cơ sở: P(1) đúng. Tại sao?
Bước quy nạp: Giả sử P(1), · · · ,P(k) đều đúng để chứng minh
P(k+ 1).
▶ Xét T là cây với |V| = k+ 1 và xét uv là một cạnh của T.
▶ Xóa cạnh uv khỏi T ta được hai cây T1 = (V1,E1) và
T2 = (V2,E2), ta có
|V1|+ |V2| = |V|, |E1|+ |E2| = |E| − 1.
▶ Áp dụng giả thiết quy nạp ta được
|E| = |E1|+ |E2|+ 1
= (|V1| − 1) + (|V2| − 1) + 1
= |V| − 1.
13 / 46
Định lý
Nếu T = (V,E) là một cây với ít nhất hai đỉnh, vậy thì:
(T3) với mỗi cặp đỉnh x, y có duy nhất một đường đi từ x tới y;
(T4) đồ thị thu được từ T bằng cách xóa đi một cạnh bất kỳ sẽ có
hai thành phần liên thông, mỗi thành phần là một cây;
(T5) |E| = |V| − 1.
14 / 46
Bài tập
Xét cây T = (V,E) với |V| ≥ 2. Hãy chứng minh rằng T có ít nhất
hai đỉnh bậc 1.
15 / 46
Bài tập
Xét T = (V,E) là cây với |V| ≥ 2. Hãy dùng tính chất
(T5) |E| = |V| − 1;
để chứng minh rằng T có ít nhất hai đỉnh bậc 1.
16 / 46
Bài tập
Ta nói rằng đồ thị F là một rừng nếu nó có tính chất:
(T2) F không có chu trình.
Hãy chứng minh rằng nếu F = (V,E) là một rừng với c thành
phần liên thông thì
|E| = |V| − c.
17 / 46
Định lý
Xét đồ thị T = (V,E). Các khẳng định sau đây là tương đương
nhau:
1. T là cây;
2. T không chứa chu trình và |E| = |V| − 1;
3. T liên thông và |E| = |V| − 1;
4. T là đồ thị liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì
đồ thị thu được là không liên thông;
5. Hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng
một đường;
6. T không chứa chu trình, nhưng nếu ta thêm một cạnh nối hai
đỉnh không kề nhau trong T thì đồ thị nhận được có đúng
một chu trình.
18 / 46
Bài tập
Hãy chứng minh định lý trước.
19 / 46
Nội dung
Một số tính chất của cây
Đếm cây gán nhãn
Câu hỏi
Có bao nhiêu cây với n đỉnh?
21 / 46
Câu hỏi
Hai cây này có trùng nhau?
22 / 46
Cây gán nhãn
▶ Ta cố định các đỉnh của cây, mỗi đỉnh được gán một nhãn.
▶ Hai cây là giống nhau nếu và chỉ nếu chúng có cùng tập cạnh.
23 / 46
Ví dụ
Hoán đổi nhãn 2 và 4 của cây gán nhãn dưới đây cho ta một cây
gán nhãn khác.
24 / 46
Bài tập
Tìm số cây gán nhãn với 2, 3, 4, và 5 đỉnh?
25 / 46
Định lý (Cayley)
Số cây gán nhãn với n đỉnh là nn−2.
Trong phần còn lại của mục này, ta sẽ đi chứng minh định lý
Cayley.
26 / 46
Lưu trữ cây: dùng ma trận kề
0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
1 0 0 0 1 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 1 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0
27 / 46
Mệnh đề
Số lượng cây gán nhãn với n đỉnh phải không nhiều hơn 2(n2−n)/2.
Tại sao?
28 / 46
Lưu trữ cây: dùng danh sách cạnh
7 8 9 6 3 0 2 6 6
9 9 2 2 0 2 4 1 5
29 / 46
Mệnh đề
Số lượng cây gán nhãn với n đỉnh phải ít hơn 22n log2 n.
Tại sao?
30 / 46
Lưu trữ cây: dùng Father code
▶ Cố định một đỉnh làm gốc (ví dụ đỉnh có nhãn nhỏ nhất).
▶ Liệt kê các cạnh giống như lưu trữ dùng danh sách cạnh (theo
hai dòng); tuy nhiên
▶ với mỗi cạnh, đỉnh ở dòng dưới luôn là đỉnh gần gốc hơn (hay
còn gọi là cha của) đỉnh ở dòng trên, và
▶ các đỉnh ở trên được sắp thứ tự.
31 / 46
Father code: Ví dụ
1 2 3 4 5 6 7 8 9
6 0 0 2 6 2 9 9 2
Câu hỏi
Tại sao dòng đầu tiên lại là các
số 1, 2, 3, 4, 5, 6, 7, 8, 9?
32 / 46
Father code
▶ Nếu cây có n đỉnh thì dòng đầu tiên luôn là 1, 2, . . . ,n− 1.
▶ Tại sao số 0 không xuất hiện ở dòng đầu tiên?
▶ Vậy ta có thể xóa dòng đầu tiên.
▶ Father code là dòng thứ 2.
33 / 46
Bài tập
Xét các ”mã” sau:
1. (0, 1, 2, 3, 4, 5, 6, 7);
2. (7, 6, 5, 4, 3, 2, 1, 0);
3. (0, 0, 0, 0, 0, 0, 0, 0);
4. (2, 3, 1, 2, 3, 1, 2, 3).
Những mã nào ở trên có thể là ”father codes” của cây?
34 / 46
Mệnh đề
Số lượng cây gán nhãn với n đỉnh phải không nhiều hơn nn−1.
35 / 46
Lưu trữ cây: dùng Prüfer code mở rộng
Thuật toán tính Prüfer code mở rộng từ cây
1. Nếu cây không có cạnh nào thì thuật
toán dừng.
2. Tìm đỉnh u có bậc 1 và có nhãn nhỏ nhất
khác 0.
3. Gọi cạnh có đầu mút u là {u, v}. Ghi ra uv .
4. Xóa đỉnh u và cạnh {u, v} khỏi cây.
5. Quay lại bước 1.
8.4 How to Store Trees 151
0
15 2
6 3
7
4
FIGURE 8.5. A tree reconstructed from its Pru¨fer code
How does the first row start? Remember that this is the node that we
delete in the first step; by the rule of constructing the Pru¨fer code, this is
the node with degree 1 with smallest label. Could this node be node 1? No,
because then we would have to delete it in the first step, and it could no
longer occur, but it does. By the same token, no number occurring in the
second row could be a leaf of the tree at the beginning. This rules out 2, 3,
and 4.
What about 5? It does not occur in the second row; does this mean that
it is a leaf of the original tree? The answer is yes; otherwise, 5 would have
been the father of some other node, and it would have been written in
the second row when this other node was deleted. Thus 5 was a leaf with
smallest label, and the first row of the extended Pru¨fer code must start
with 5.
Let’s try to figure out the next entry in the first row, which is, as we
know, the leaf with smallest label of the tree after 5 was deleted. The node
1 is still ruled out, since it occurs later in the second row ; but 2 does not
occur again, which means (by the same argument as before) that 2 was the
leaf with smallest label after 5 was deleted. Thus the second entry in the
first row is 2.
Similarly, the third entry must be 4, since all the smaller numbers either
occur later or have been used already. Continuing in a similar fashion, we
get that the full array must have been
5 2 4 6 7 3 1
2 4 0 3 3 1 0
This corresponds to the tree in Figure 8.5
Proof. [of Lemma 8.4.1] The considerations above are completely general,
and can be summed up as follows:
Each entry in the first row of the extended Pru¨fer code is the
smallest integer that does not occur in the first row before it,
nor in the second row below or after it.
36 / 46
Prüfer code mở rộng
1 3 4 5 6 7 8 9 2
6 0 2 6 2 9 9 2 0
Câu hỏi
Tại sao vị trí cuối ở hàng dưới
luôn là 0?
37 / 46
Bổ đề
Hàng đầu tiên của một Prüfer code mở rộng có thể tính được từ
hàng thứ hai.
38 / 46
Ví dụ
Giả sử ta có một Prüfer code mở rộng còn thiếu hàng trên như sau:
x1
2 4 0 3 3 1 0
Đỉnh x1 phải thỏa mãn ba điều kiện:
1. x1 ∈ {0, 1, . . . , 7}. Tại sao?
2. x1 là đỉnh bậc 1, có nhãn nhỏ nhất khác 0.
3. khi xây dựng dãy từ cây, x1 bị xóa khỏi cây ở bước đầu tiên.
Điều kiện 3 chỉ ra rằng x1 sẽ không xuất hiện trong hàng 2. Tại
sao? Từ điều kiện 2, ta được x1 = 5. Tại sao?
39 / 46
Ví dụ
Tiếp tục ví dụ trước, bây giờ ta có:
5 x2
2 4 0 3 3 1 0
Đỉnh x2 phải thỏa mãn ba điều kiện:
1. x2 ∈ {0, 1, . . . , 7}. Tại sao?
2. x2 là đỉnh bậc 1, có nhãn nhỏ nhất khác 0 và 5.
3. khi xây dựng dãy từ cây, x2 bị xóa khỏi cây ở bước thứ hai.
Vậy x2 = 2.
40 / 46
Bài tập
Hãy hoàn thành nốt hàng trên của Prüfer code mở rộng sau
5 2
2 4 0 3 3 1 0
41 / 46
Khẳng định
Mỗi phần tử ở hàng đầu tiên của Prüfer code mở rộng là số
nguyên nhỏ nhất thỏa mãn:
▶ ở hàng đầu tiên, số này không xuất hiện trước nó;
▶ ở hàng thứ hai, số này không xuất hiện ở dưới nó hoặc phía
sau nó.
Ví dụ
/1 /3 /4 ?
6 0 2 /6 /2 /9 /9 /2 /0
42 / 46
Prüfer code
▶ Ta không cần lưu trữ toàn bộ Prüfer code mở rộng, mà
▶ ta chỉ cần lưu tữ dãy gồm n− 2 phần tử của hàng thứ hai.
▶ Dãy này gọi là Prüfer code của cây.
▶ Vậy thì, Prüfer code là một dãy số độ dài n− 2, với mỗi phần
tử của nó là một số nguyên từ 0 đến n− 1.
43 / 46
Bổ đề
Mọi dãy có độ dài n− 2 gồm các số nguyên giữa 0 và n− 1 đều là
Prüfer code của một cây n đỉnh nào đó.
Ta đã hoàn thành chứng minh định lý sau chưa?
Định lý (Cayley)
Số cây gán nhãn với n đỉnh là nn−2.
44 / 46
Bài tập (Lập trình)
Viết chương trình nhập vào một dãy là mã Prüfer của một cây và
in ra cây đó. Bạn có thể hiện cây ở dạng danh sách cạnh, hoặc sử
dụng công cụ Graphviz để vẽ tự động.
45 / 46
Cài đặt Prufer Code
1. Version 1
2. Version 2
3. Version 3
46 / 46