CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
1.Cây và tính chất cơ bản của cây:
Ta gọi cây là đồ thị
vô hướng, liên thông và không có chu trình. Một đồ thị không có chu trình gọi là rừng. Như vậy thì rừng là đồ thị mà mỗi thành phần liên thông của nó là cây.
Code:
Định lí:
Giả sử G=(V,E) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương nhau:
a. G là cây.
b. G không chứa chu trình và có n-1 cạnh.
c.G liên thông và có n-1 cạnh.
d.G liên thông và mỗi cạnh của nó đều là cầu.
e.Hai đỉnh bất kì của đồ thị được nối với nhau duy nhất bởi một đường đi đơn.
f.G không chứa chu trình, nhưng hễ cứ thêm vào nó một cạnh thì thì ta thu được đúng một chu trình