• CÂY là đồ thị vô hướng liên thông và không có chu trình.
• RỪNG là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây.
• Lưu ý: cây không chứa khuyên và cạnh song song.

Định nghĩa

• Cho G=(X, E) là đồ thị có hướng liên thông. G được gọi là cây có hướng nếu:

  G không có chu trình,

  G có gốc.

• Lưu ý:

  Chu trình có thể không quan tâm đến hướng của các cạnh.

  Cây có hướng cũng là cây.

  Cần phân biệt cây trong LTĐT và cây trong các giáo trình khác

Các định nghĩa tương đương

• Cho đồ thị có hướng G=(X, E) gồm N đỉnh. Các điều sau đây tương đương với nhau.

  G là một cây có hướng.

  ∃r ∈ X thỏa ∀v ∈ X, có một đường đi duy nhất từ r đến v.

  G tựa liên thông mạnh tối tiểu.

  G liên thông và có đỉnh r sao cho: d^-(r)=0 và d^-(i)=1, ∀i ∈ X{r}.

  G không có chu trình và có đỉnh r sao cho: d^-(r)=0 và d^-(i)=1, ∀i ∈ X{r}.

  G tựa liên thông mạnh và không có chu trình.

  G tựa liên thông mạnh và có N-1 cạnh.

• Lưu ý:

  r trong các định nghĩa trên là duy nhất và được gọi là gốc của cây có hướng.

  Mỗi đỉnh i thuộc X có duy nhất một đỉnh j mà cạnh liên kết với (j, i) hướng vào i, đỉnh j được gọi đỉnh cha của I.

  Nếu đỉnh x thuộc X thỏa điều kiện d⁺(x)=0 thì x được gọi là lá của cây có hướng.

Định lý

• Cho G là đồ thị có hướng.

  Nếu G có chứa một đồ thị bộ phận là cây có hướng thì G tựa liên thông mạnh.

  Nếu G tựa liên thông mạnh thì G có chứa một đồ thị bộ phận là cây có hướng.

*Lưu ý: Nếu G tựa liên thông mạnh, T là một cây có hướng là đồ thị bộ phận G thì T cũng được gọi là cây có hướng tối đại của G.

Bài toán đếm số lượng cây con có hướng

*Cho đồ thị có hướng G (5 đỉnh): Hãy chọn một đỉnh gốc và xác định số lượng cây có hướng con của đồ thị G đó. Chọn đỉnh xuất phát là 1 Đồ thị G

*Bước 1: Viết ma trận kề cho đồ thị G Ma trận G

*Bước 2: Tạo K: Những giá trị nằm trên đường chéo chính thay bằng bậc của đỉnh đó đi ra khỏi các đỉnh khác. Còn tất cả các giá trị còn lại của nó thay bằng đối nghịch đảo của giá trị đó.

Đồ thị G

*Bước 3: Do đỉnh xuất phát của ta chọn là 1. Vậy ma trận mới từ K. Sau khi bỏ đi dòng 1 cột 1 => K(1, 1) Đồ thị G

*Bước 4: Tính det(K(1, 1))

• Chọn dòng hay cột có nhiều số 0 nhất (dòng số 4) từ ma trận K(1, 1)
• Nhân từng phần tử trong dòng đó với ma trận bỏ đi dòng và cột của phần tử đó.

Giải thích biểu thức: Ở biểu thức đầu tiên ở dòng 4 (dòng nhiều số 0 nhất - Ma trận K(1, 1)).

• Ta thấy giá trị tại dòng 4 và cột 1 = 0 như vậy ta sẽ tiến hành bỏ đi dòng 4 và cột 1 => Sinh ra một ma trận khác.
• Tính định thức của ma trận đó và nhân với 2 giá trị (-1)^{dòng đã xóa (4) + cột đã xóa (1)} và giá trị tại dòng cột đã bị xóa (0) *Kết luận: Vậy với việc chọn đỉnh gốc là 1 thì ta sẽ có 4 cây con'''