Bài 8. Đồ thị dạng Cây

Tham khảo Video sau đây :

1.Định nghĩa

💡 GHI NHỚ

• Cây (tree) là một đồ thị vô hướng, liên thông và không có chu trình

• Rừng (forest) là một đồ thị mà mỗi thành phần liên thông của nó là một cây

==> Suy ra, đồ thị không có chu trình là một rừng

2.Tính chất của cây

💡 ĐỈNH LÝ VỀ ĐỈNH TREO

Nếu một cây T gồm n đỉnh với n ≥ 2 thì T chứa ít nhất 2 đỉnh treo

Đơn đồ thị T=(V, E) là một đồ thị vô hướng n đỉnh. Khi đó, các mệnh đề sau tương đương :

1. T là một cây liên thông và mỗi cạnh của nó đều là cạnh cầu

2. T không chứa chu trình (nhưng thêm vào 1 cạnh bất kỳ thì thu được 1 chu trình) và có n-1 cạnh

3. Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đơn

3.Bài tập