Exercise 1
设 $n=2^k$
当 $k = 1$或$2$ 时，比较显然
$k=3$时，有 $A = \{ 1,2,3,4 \}, B=\{ 5,6,7,8 \}, C=\{ 1,2,3,5,6 \}$这样一组构造
当 $k \geq 4$ 时，考虑如下构造：
集合 A,B 里各有 $2^{k-1}$ 个元素。
此时我构造集合 $S_{1}$，从 A 中选取 $2^{k-2} +1$ 个元素， B 中选取 $2^{k-2}$ 个元素
所以 $S_{1}$ 有 $2^{k-1} +1$ 个元素，由贪心性质，第一次一定选择它。
此时 A 中还有 $2^{k-2} -1$ 个未覆盖元素，B 中还有 $2^{k-2}$ 个未覆盖元素
再构造集合 $S_{2}$， 从A中选取 $2^{k-3}$ 个未覆盖元素，B中选取 $2^{k-3} +1$ 个未覆盖元素
所以 $S_{2}$ 有$2^{k-2} +1$ 个元素，由贪心性质，第二次一定选择它。
此时 A 中还有 $2^{k-3} -1$ 个未覆盖元素，B 中还有 $2^{k-3} -1$ 个未覆盖元素。
之后就从 A， B 中各选 $2^{i}(i=\lfloor \log|A| \rfloor)$个未覆盖元素构建新集合。由贪心性质知每次都会优先选我们构造出的集合，直至A, B 中都只剩1个元素。
考虑 A 的未覆盖点数量变化 ： $2^{k-1} \to 2^{k-2} -1 \to 2^{k-3}-1 \to \dots \to 2^{1} -1$，故一共会经历 $k-2 +2 = k$次集合的选取，即贪心至少要找到 $\log n$ 个集合。
Exercise 2
(a)
a forest $\implies$ a disjoint union of trees ：
是一个森林，则意味着这个图里没有环。由树的定义知，一个无环连通分量一定是一棵树。一个无环图包含多个无环连通分量，故一个森林是多棵树的无交并。
a disjoint union of trees $\implies$ a forest ：
已知一棵树是没有环的，那多棵树的不相交并肯定也是没有环的，所以是一个森林。
(b)
即说明无环图中至少含有一个度数 $\leq 1$ 的点。
反证法：若所有点的度数都 $\geq 2$，考虑其中一个连通分量。不妨设其有 k 个点
考虑其中任意一个点 u，由于度数 $\geq 2$ ，每个点都至少与两条边相连，所以该连通图至少有 $\frac{2 \cdot k}{2} =k$ 条边。由之前的 Lemma 知，该连通图含有 k-1 条边就是棵树。现至少有 k 条边，故一定会存在环，与假设矛盾。所以无环图中至少有一个点的度数 $\leq 1$。
(c)
可以。用数学归纳法。
对于任意树T，该贪心算法都能计算出T的最大独立集。
基例：
- 当T只有1个节点时，算法选择该节点，得到大小为1的独立集，显然是最大的。
- 当T有2个节点相连时，算法选择其中一个节点，得到大小为1的独立集，这也是最大的（两个节点相邻，不能同时选）。
归纳假设：
假设对于所有节点数小于n的树，该算法都能计算出最大独立集。
归纳步骤：
考虑节点数为n的树T。算法第一步选择一个度数≤1的节点t。
- 情况1：t是孤立节点（度数0）
算法将t加入独立集，然后移除t，得到节点数为n-1的树T'。根据归纳假设，算法在T'上得到的是T'的最大独立集。由于t与T'中所有节点都不相邻，将t加入后得到的独立集就是T的最大独立集。
- 情况2：t是叶子节点（度数1）
设t的唯一邻居为u。算法将t加入独立集，然后移除t和u，得到森林F。根据归纳假设，算法在F上得到的是F的最大独立集。
现在证明存在一个T的最大独立集包含t：
设M是T的任意一个最大独立集。
- 如果M包含t，那么M不能包含u，因此M\{t}是F的一个独立集，其大小不超过F的最大独立集的大小。
- 如果M不包含t，那么M必须包含u（否则可以将t加入M，得到一个更大的独立集，与M是最大的矛盾）。此时，我们可以构造一个新的独立集M'=(M\{u})∪{t}，显然|M'|=|M|，即M'也是T的最大独立集，且M'包含t。
因此，选择t不会错过最优解。算法在F上得到最大独立集后，加上t，就得到了T的最大独立集。
Exercise 3
(a)
记 $f[i]$ 为前 i 位的最长上升子序列长度，$d[i]$ 为前 i 位的最长上升子序列数量。
时间复杂度主要来自两层循环，故时间复杂度为 $O(n^2)$ 的。
(b)
$$ a[i]= \left\lfloor \frac{i}{2} \right\rfloor $$所以最后数列形如 $0011\dots \left( \frac{n}{2}-1 \right)\left( \frac{n}{2}-1 \right)$，此时从任意两个相同的数中选一个出来就得到一个最长上升子序列。所以共有 $2^{\frac{n}{2}}$ 种。
Exercise 4
最大流（最小割）为13，最小割具体为{S,C} 与 V\\{S,C} 边为：S->A,S->B,C->B,F->T
![[Pasted image 20260522195644.png]]
Exercise 5
(a)
由于 s 是 source， t 是sink，故 s 无入边， t 无出边。
所以有
$$ \sum_{u \in V \setminus \{ s, t \}}\sum_{(w,u) \in E} f_{wu} = \sum_{(u,v) \in E}f_{uv} - \sum_{(s,u) \in E}f_{su} $$和
$$ \sum_{u \in V \setminus \{ s, t \}}\sum_{(u,z) \in E} f_{uz} = \sum_{(u,v) \in E}f_{uv} - \sum_{(u,t) \in E}f_{ut} $$由于对所有 $u \in V \setminus \{ s,t \}$，有：
$$ \sum_{(w,u)\in E}f_{wu}=\sum_{(u,z) \in E}f_{u,z} $$所以有：
$$ \sum_{u \in V \setminus \{ s, t \}}\sum_{(w,u) \in E} f_{wu} = \sum_{u \in V \setminus \{ s, t \}}\sum_{(u,z) \in E} f_{uz} $$所以：
$$ \sum_{(s,u) \in E}f_{su} = \sum_{(u,t) \in E}f_{ut} $$(b)
由流定义知
$$ \text{size}(f) = \sum_{(s,u) \in E}f_{su} = \sum_{(u,t) \in E}f_{ut} $$对所有 $u \in L \setminus \{ s \}$，有：
$$ \sum_{(u,v) \in E}f_{uv} -\sum_{(v,u)\in E}f_{vu} =0 $$而由于 s 是 source，所以 s 没有入边，所以：
$$ \sum_{(s,v) \in E}f_{s,v} -\sum_{(v,s)\in E}f_{v,s} = \sum_{(s,v) \in E}f_{s,v}=\text{size}(f) $$所以
$$ \text{size}(f)=\sum_{u \in L}\left(\sum_{(u,v)\in E}f_{uv} - \sum_{(v,u)\in E}f_{vu}\right) $$考虑 u, v 的位置：
- 如果 u, v 都在L中，则前后可抵消
- 如果 u 在 L 中，v 在 R 中，只加不减
- 如果 u 在 R 中，v 在 L 中，只减不加
所以有：
$$ \text{size}(f) = \sum_{(u,v)\in E\cap(L \times R)}f_{uv}-\sum_{(u,v)\in E\cap(R\times L)f_{uv}}f_{uv} $$其中，
$$ \sum_{(u,v)\in E \cap(L \times R)}f_{uv} \leq \sum_{(u,v)\in E\cap(L\times R)}c_{uv} = \text{capacity}(L,R) $$同时又肯定有：
$$ \sum_{(u,v)\in E\cap(R\times L)f_{uv}}f_{uv} \geq0 $$所以最后有：
$$ \text{size}(f) = \sum_{(u,v)\in E\cap(L \times R)}f_{uv}-\sum_{(u,v)\in E\cap(R\times L)f_{uv}}f_{uv} \leq \text{capacity}(L,R) $$Exercise 6
同 Exercise 4