›
›

Giáo trình Toán rời rạc - Bài 5: Cây - Trần Vĩnh Đức

Download
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  
y
x
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.  
9
5
2
6
7
8
4
3
1
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  
Tải về để xem bản đầy đủ
pdf 46 trang Thùy Anh 17140 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 5: Cây - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_toan_roi_rac_bai_5_cay_tran_vinh_duc.pdf