Bài tập 5, § 2

(a) Cho $n$ là một số tự nhiên $\geqslant 1$ và cho G là một đồ thị có tập hợp các đỉnh là tập hợp $\mathbf{Z}/n\mathbf{Z}$ và sao cho hai đỉnh $i$ và $j$ được nối bởi một cung khi và chỉ khi $i-j=\pm 1$ (mod$. n$). Hãy xác định tường minh tập hợp các rừng cực đại của G.

(b) Cho G là một đồ thị và cho S là tập hợp các đỉnh của nó. Giả sử rằng với mọi cặp $(x, y)$ các đỉnh của G, tập hợp các cung của G có gốc $x$ và số hạng $y$ có lực lượng 1 nếu $x=\not y$ và 0 trong trường hợp ngược lại ("đồ thị đầy đủ"). Tính lực lượng của tập hợp các rừng cực đại của G.

(c) Cho G là một đồ thị và cho S là tập hợp các đỉnh của nó. Cho $(S_1,S_2)$ là một phân hoạch của S; giả sử rằng với mọi cặp $(x, y)$ các đỉnh của G, tập hợp các cung của G có gốc $x$ và số hạng $y$ có lực lượng 1 nếu $(x, y)\in S_1\times S_2$ và 0 trong trường hợp ngược lại ("đồ thị hai phía đầy đủ"). Tính lực lượng của tập hợp các rừng cực đại của G.