Cây

Định nghĩa 33 (Cây)

Cây (hay tree, hay дерево) là đồ thị vô hướng, liên thông, và không có chu trình đơn.

../../_images/tree.jpg

Hình 14 Ví dụ về cây

Định nghĩa 34 (Cây khung)

Xét đồ thị \(G = (V, E)\) và \(T = (V', E')\) là đồ thị con của \(G\). Nếu \(T\) là cây thì ta gọi \(T\) là cây khung hoặc cây bao trùm (hay spanning tree) của đồ thị \(G\).

Điều kiện cần và đủ để một đồ thị vô hướng có cây khung là đồ thị đó phải liên thông.

Một đồ thị có thể có nhiều cây khung. Ở hình 15 ta xóa đi cạnh \(e_{23}\) và \(e_{46}\) (hai cạnh màu đỏ) thì thu được một cây khung. Tương tự, ở hình 16 ta xóa đi hai cạnh màu đỏ là \(e_{13}\) và \(e_{23}\) thì cũng thu được một cây khung khác.

../../_images/spanning-tree-1.jpg

Hình 15 Cây khung thứ nhất

../../_images/spanning-tree-2.jpg

Hình 16 Cây khung thứ hai

Định lý 13 (Daisy Chain Theorem)

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

  1. \(T\) là cây.

  2. \(T\) không chứa chu trình đơn và có \(n - 1\) cạnh.

  3. \(T\) liên thông và mỗi cạnh của nó đều là cầu.

  4. Giữa hai đỉnh bất kì của \(G'\) đều tồn tại đúng một đường đi đơn.

  5. \(T\) không chứa chu trình đơn nhưng nếu ta thêm vào một cạnh thì ta thu được chu trình đơn.

  6. \(T\) liên thông và có \(n - 1\) cạnh.

Các mệnh đề trên có thể xem như các định nghĩa tương đương của cây. Trong nhiều trường hợp thì tính chất của cây có thể thu được từ các định nghĩa này nên mình sẽ chứng minh chuỗi mệnh đề này.

Chứng minh 1 \(\Rightarrow\) 2

Từ \(T\) là cây, theo định nghĩa thì \(T\) không chứa chu trình đơn. Ta chứng minh cây \(T\) có \(n\) đỉnh thì sẽ có \(n - 1\) cạnh bằng quy nạp.

Với \(n = 1\) thì cây chỉ có thể có \(0\) cạnh (không nối đi đâu cả).

Giả thiết quy nạp: với \(n \geqslant 1\) thì cây \(T\) với \(n\) đỉnh có \(n - 1\) cạnh. Đặt các đỉnh là \(v_1\), \(v_2\), ..., \(v_n\).

Bây giờ ta thêm đỉnh \(v_{n+1}\) vào cây \(T\) để được cây mới \(T'\). Ta cần chứng minh cây mới có \(n\) cạnh.

Do \(T\) liên thông nên giữa mọi cặp đỉnh \(u\) và \(v\) của \(T\) đều có đường đi, giả sử là

\[u = v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} = v.\]

Khi đó, nếu cả hai đỉnh \(u\) và \(v\) đều có cạnh nối với \(v_{n+1}\) thì ta thu được chu trình

\[v_{n+1} \to u = v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} = v \to v_{n+1},\]

như vậy sẽ không tạo thành cây. Nghĩa là từ \(v_{n+1}\) chỉ có thể nối với một trong các đỉnh \(v_1\), ..., \(v_n\) nên số cạnh chỉ có thể tăng lên \(1\) để có được cây mới. Khi đó, với \(n + 1\) đỉnh ta có \(n\) cạnh, theo quy nạp ta có điều phải chứng minh.

Chứng minh 2 \(\Rightarrow\) 3

Giả sử \(T\) có \(k\) thành phần liên thông \(T_1\), \(T_2\), ..., \(T_k\). Vì \(T\) không chứa chu trình đơn nên các thành phần liên thông của \(T\) cũng không chứa chu trình đơn, tức là \(T_1\), \(T_2\), ..., \(T_k\) đều là cây.

Gọi \(n_1\), \(n_2\), ..., \(n_k\) lần lượt là số đỉnh của \(T_1\), \(T_2\), ..., \(T_k\) thì

  • \(n_1 + \cdots + n_k = n\);

  • cây \(T_1\) có \(n_1 - 1\) cạnh (từ chứng minh 1 \(\Rightarrow\) 2), tương tự cây \(T_2\) có \(n_2 - 1\) cạnh, ..., \(T_k\) có \(n_k - 1\) cạnh.

Cộng số lượng cạnh của \(k\) cây lại ta có tổng số cạnh của cây \(T\), kết hợp giả thiết ban đầu ta có

\[n_1 + n_2 + \cdots + n_k - k = n -k = n - 1.\]

Như vậy \(k = 1\), nghĩa là \(T\) liên thông. Từ đây, do \(T\) không có chu trình nên nếu bỏ một cạnh bất kì thì đồ thị mới cũng không có chu trình. Đồ thị mới không thể liên thông vì nếu giả sử ngược lại (phản chứng) đồ thị mới liên thông thì nó sẽ phải là cây có \(n\) đỉnh. Nhưng hiện tại đồ thị chỉ có \(n - 2\) cạnh vì đã bỏ đi một cạnh, không phải \(n - 1\). Do đó cạnh bỏ đi là cầu.

Chứng minh 3 \(\Rightarrow\) 4

Gọi \(u\) và \(v\) là hai đỉnh bất kì trong \(T\). Vì \(T\) liên thông nên sẽ có một đường đi đơn từ \(u\) tới \(v\) là

\[u = v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} = v.\]

Giả sử tồn tại một đường đi đơn khác từ \(u\) tới \(v\) là

\[u = v_{j_1} \to v_{j_2} \to \cdots \to v_{j_l} = v.\]

Khi đó nếu ta xóa đi một cạnh ở đường đi đơn đầu nhưng không nằm trên đường đi đơn thứ hai thì \(u\) vẫn tới được \(v\) nhờ vào đường đi đơn thứ hai. Nói cách khác \(u\) và \(v\) vẫn liên thông nên dữ kiện "mọi cạnh đều là cầu" mâu thuẫn.

Nói rõ hơn, không mất tính tổng quát, giả sử đường đi đơn thứ nhất và thứ hai có cạnh chung là \(v_{i_2} \to v_{i_3}\), nghĩa là \(v_{i_2} = v_{j_2}\) và \(v_{i_3} = v_{j_3}\). Khi đó nếu ta xóa cạnh \(v_{i_2} \to v_{i_3}\) thì \(u\) vẫn tới được \(v\) và số lượng thành phần liên thông không tăng.

Chứng minh 4 \(\Rightarrow\) 5

Cây \(T\) sẽ không chứa chu trình đơn vì khi đó sẽ có hai đường đi đơn từ hai điểm bất kì trên chu trình đó (chúng ta có thể tưởng tượng đi cùng chiều và ngược chiều kim đồng hồ đều có thể đi từ 1 tới 3).

Khi đó, hai đỉnh bất kì \(u\) và \(v\) luôn liên thông, nghĩa là tồn tại đường đi

\[u = v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} = v.\]

Nếu ta thêm bất kì bất kì cạnh nào nối giữa hai đỉnh trên đường đi, không mất tính tổng quát giả sử là \(v_{i_1}\) và \(v_{i_k}\), khi đó ta có chu trình vì

\[u = v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} = v \to v_{i_1}.\]

Như vậy cứ thêm vào một cạnh ta sẽ có chu trình.

Chứng minh 5 \(\Rightarrow\) 6

Giữa hai đỉnh bất kì \(u\) và \(v\) của \(T\) có hai trường hợp:

  • \(u\) và \(t\) được nối bởi một cạnh;

  • \(u\) và \(t\) không kề nhau (không có cạnh nối). Ở trường hợp này, nếu chúng ta vẽ cạnh nối \(u\) với \(v\) thì theo giả thiết sẽ tạo ra chu trình. Điều này chỉ xảy ra khi và chỉ khi có một đường đi đơn từ \(u\) tới \(v\).

Như vậy trong cả hai trường hợp thì luôn tồn tại đường đi từ \(u\) tới \(v\), nói cách khác là hai đỉnh liên thông. Điều này đúng với mọi đỉnh trong đồ thị nên \(T\) liên thông.

Do ta đã chứng minh được \(T\) liên thông, và giả thiết là \(T\) không chứa chu trình đơn, nên suy ra \(T\) là cây. Như vậy \(T\) có \(n - 1\) cạnh.

Chứng minh 6 \(\Rightarrow\) 1

Sử dụng phản chứng, giả sử \(T\) không là cây. Khi đó \(T\) không liên thông hoặc \(T\) có chu trình. Do giả thiết \(T\) liên thông nên ta chỉ xét trường hợp \(T\) có chu trình.

Nếu ta bỏ một cạnh trên chu trình này thì \(T\) vẫn liên thông. Nếu \(T\) vẫn còn chu trình thì ta lại bỏ đi một cạnh của chu trình đó. Tiếp tục cho đến khi \(T\) không còn chu trình nào. Lúc này \(T\) là cây nhưng lại có ít hơn \(n - 1\) cạnh do chúng ta đã bỏ ít nhất một cạnh. Điều này vô lí vì ở chứng minh trên (1 \(\Rightarrow\) 2), nếu \(T\) là cây thì \(T\) có \(n - 1\) cạnh. Như vậy theo phản chứng suy ra \(T\) là cây.

Định lý 14

Số cây khung của đồ thị đầy đủ \(K_n\) là \(n^{n-2}\).