Chương 5: Cây
2
Chương 5 - Cây
Nội dung
Cây khung của đồ thị
Định nghĩa
I.
II.
Tập các chu trình cơ bản
III.
Cây khung nhỏnhất
IV.
Cây có gốc
V.
Lý thuyết đồ thị
2
3
Chương 5 - Cây
I. Định nghĩa
Cây là đồ thị vô hướng
Liên thông
Không có chu trình
Rừng là đồ thị vô hướng
Không có chu trình
4
Chương 5 - Cây
I. Định nghĩa
Định lý nhận biết cây
Cho T =(V, E) là đồ thị vô hướng n đỉnh. Các mệnh đề sau
đây là tương đương:
MĐ1: T là cây ( T liên thông và không chứa chu trình ).
MĐ2: T không chứa chu trình và có n-1 cạnh.
MĐ3: T liên thông và có n-1 cạnh.
MĐ4: T liên thông và mỗi cạnh của nó đều là cầu.
MĐ5: Hai đỉnh bất kỳcủa T được nối với nhau bởi đúng 1
đường đi đơn.
MĐ6: T không chứa chu trình nhưng hễcứthêm vào nó
một cạnh ta thu được đúng 1 chu trình.
5
Chương 5 - Cây
I. Định nghĩa
Định lý nhận biết cây
Chứng minh:
Ta sẽchứng minh định lý trên theo sơ đồ sau:
MĐ1 ⇒ MĐ2 ⇒ MĐ3 ⇒ MĐ4 ⇒ MĐ5 ⇒ MĐ6 ⇒ MĐ1