TÀI LIỆU THƯ VIỆN SỐ

Cây

Định nghĩa và tính chất
Định nghĩa Cây.
a) Cho G là đồ thị vô hướng. G được gọi là một cây nếu G liên thông và không có chu trình sơ cấp. b) Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.

Định nghĩa và tính chất
1 4 3 10 9 6 11 12 13 14 7 8 15 16 17

2 5

3

4

1

Định nghĩa và tính chất
Điều kiện cần và đủ.
Cho T là đồ thị vô hướng có n đỉnh. Các phát biểu sau đây là tương đương: i. T là cây. ii. T liên thông và có n-1 cạnh. iii. T không có chu trình sơ cấp và có n-1 cạnh . iv. T liên thông và mỗi cạnh là một cầu. v. Giữa hai đỉnh bất kỳ có đúng một đường đi sơ cấp nối chúng với nhau. vi. T không có chu trình sơ cấp và nếu thêm vào một

Từ khóa: cây, duyệt cây, định nghĩa cây, tính chất cây, đồ thị vô hướng, lý thuyết cây