Cây có hướng

• 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:

1. G không có chu trình,
2. G có gốc.

• Lưu ý:

1. Chu trình có thể không quan tâm đến hướng của các cạnh.
2. Cây có hướng cũng là cây.
3. 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.

1. G là một cây có hướng.
2. ∃r ∈ X thỏa ∀v ∈ X, có một đường đi duy nhất từ r đến v.
3. G tựa liên thông mạnh tối tiểu.
4. G liên thông và có đỉnh r sao cho: d^-(r)=0 và d^-(i)=1, ∀i ∈ X\{r}.
5. G không có chu trình và có đỉnh r sao cho: d^-(r)=0 và d^-(i)=1, ∀i ∈ X\{r}.
6. G tựa liên thông mạnh và không có chu trình.
7. G tựa liên thông mạnh và có N-1 cạnh.

• Lưu ý:

1. 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.
2. 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.
3. 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.

1. 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.
2. 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ử đó.

${\begin{aligned}\operatorname {Det} k(1,1)&=(-1)^{4+1}\times 0\times {\begin{vmatrix}-1&-1&0\\1&-1&0\\3&0&-1\end{vmatrix}}+(-1)^{4+2}\times 0\times {\begin{vmatrix}2&-1&0\\0&-1&0\\-1&0&-1\end{vmatrix}}+(-1)^{4+3}\times 0\times {\begin{vmatrix}2&-1&0\\0&1&0\\-1&3&-1\end{vmatrix}}+(-1)^{4+4}\times 1\times {\begin{vmatrix}2&-1&-1\\0&1&-1\\-1&3&0\end{vmatrix}}\\&=(-1)\times 0\times (-3)+1\times 0\times 2+(-2)\times (-1)\times 0+4\times 1\times 1\\&=\color {Red}4\end{aligned}}$

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

Liên kết ngoài

• Sách trực tuyến về Lý thuyết đồ thị
• Hướng dẫn về lý thuyết đồ thị Lưu trữ 2012-01-16 tại Wayback Machine
• Bài giảng của một môn học về các thuật toán đồ thị Lưu trữ 2005-08-31 tại Wayback Machine
• Minh họa hoạt hình về các thuật toán đồ thị
  • Lần bước thuật toán để tìm hiểu.
• Tóm tắt các trang minh họa thuật toán Lưu trữ 2008-06-01 tại Wayback Machine
• Dữ liệu test chuẩn cho các bài toán đồ thị con đầy đủ lớn nhất (Maximum Clique), tập con độc lập lớn nhất (Maximum Independent Set), phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô màu đỉnh (Vertex Coloring) Lưu trữ 2013-05-29 tại Wayback Machine
• Sưu tập ảnh số 1: một số mạng lưới thực
• Sưu tập ảnh số 1: một số mạng lưới thực Lưu trữ 2012-02-23 tại Wayback Machine
• Sưu tập các liên kết về đồ thị
• Các tạp chí lý thuyết đồ thị Lưu trữ 2013-07-04 tại Wayback Machine
• Sách về lý thuyết đồ thị Lưu trữ 2012-09-11 tại Wayback Machine