Các định nghĩa khác nhau của cây

[Wind]

Giả sử T=(V, E) là đồ thị vô hướng có n đỉnh. Chứng minh các mệnh đề sau đây là tương đương

1. T là 1 cây
2. T không chứa chu trình và có n-1 cạnh
3. T liên thông và có n-1 cạnh
4. T liên thông và mỗi cạnh của nó là 1 cầu
5. Hai đỉnh bất kỳ của T được nối với nhau bởi đúng 1 đường đi đơn
6. T không chứa chu trình, nhưng nếu thêm vào nó 1 cạnh bất kỳ, ta thu được đúng 1 chu trình.

[hungaya (Hung)]

Thêm định nghĩa của cây nhé bạn:

Cây là đồ thị vô hướng, liên thông, và không có chu trình đơn.

Phần chứng minh xem trong Tài liệu chuyên tin, quyển 1, trang 187.