算法导论B.4 Exercises 答案
B.4-1
假设有函数\(f(u,v)\)如下：如果\(u\)和\(v\)握过手，那么\(f(u,v)=1\)，否则\(f(u,v)=0\)。
握手关系是对称的，不难发现\(f(u,v)=f(v,u)\)，因此\(f(u,v)+f(v,u)\in\{0,2\}\)。
因此有\(\displaystyle{\sum_{u=1}^n\sum_{v=1}^nf(u,v)=2|E|}\)。
根据度数的定义，有\(\displaystyle{\text{degree}(u)=\sum_{v=1}^n f(u,v)}\)。
那么最终有：
\[\sum_{u=1}^n \text{degree}(u)=\sum_{u=1}^n\sum_{v=1}^n f(u,v)=2|E|\]
B.4-2
假设顶点\(u,v\)之间存在路径\(\langle v_0,v_1,v_2,\dots,v_k \rangle\)，其中\(v_0=u,v_k=v\)，那么：
如果\(\exists i,j,0\le i< j\le k,v_i=v_j\)成立，那么可以通过一次操作构造出一条新的路径：
\(\langle v_0,v_1,v_2,\dots,v_{i-1},v_{\mathbf{i}},v_{\mathbf{j+1}},v_{j+2},\dots,,v_k \rangle\)
可以发现，这条新路径的长度比原来缩短了\(j-i\)。由于路径长度的长度总是有限的，因此经过有限次操作后，将有\(\nexists i,j,0\le i< j\le k,v_i=v_j\)。那么此时也就获得了一条顶点\(u,v\)之间的简单路径。
类似的，如果有向图中存在环\(\langle v_0,v_1,v_2,\dots,v_k \rangle\)，其中\(v_0=v_k\)，那么：
如果\(\exists i,0< i< k,v_i=v_0\)成立，那么可以构造出一个新的环：
\(\langle v_0,v_1,v_2,\dots,v_{\mathbf{i}} \rangle\)
可以发现，这个新环的长度比原来缩短了\(k-i\)。
否则，如果\(\exists i,j,0< i< j< k,v_i=v_j\)成立，那么可以构造出一个新的环：
\(\langle v_0,v_1,v_2,\dots,v_{i-1},v_{\mathbf{i}},v_{\mathbf{j+1}},v_{j+2},\dots,,v_k \rangle\)
可以发现，这个新环的长度比原来缩短了\(j-i\)。
同样，由于环的长度也是有限的，因此经过有限次操作后，以上的两个如果将不复存在，那么也就得到了一个简单环。
B.4-3
考虑使用数学归纳法证明。
假设\(|V|=n\)。
当\(n=1\)时，图中不需要任何边即为连通图，因此\(|E|\ge |V|-1\)成立。
当\(n>1\)时，假设此图\(G=(V,E)\)已经满足\(|E|\ge |V|-1\)，那么考虑新图\(G'=(V\cup \{v_{n+1}\},E)\)，那么发现\(G'\)并非是连通的。要使得\(G'\)联通，必须要在顶点集\(|V|\)中，指定至少一个顶点与\(v_{n+1}\)关联。因此有\(|E|+1\ge |V+\{v_{n+1}\}|-1\)成立，指定的定点数为新添加的边数。那么添加了新边后，边集\(E'\)有\(|E'|\ge |E|+1\)。
令\(V'=V\cup \{v_{n+1}\}\)，那么性质\(|E'|\ge |V'|-1\)仍然保持。
B.4-4
首先需要证明这种“可达”关系满足自反性，对称性和传递性。
自反性：对于任意一个节点，它肯定存在长度为\(0\)的路径（从自己走到自己）。因此满足自反性。
对称性：如果从\(u\)到\(v\)存在可达路径\(\langle u,v_1,v_2,\dots,v \rangle\)，那么从\(v\)到\(u\)也存在可达路径\(\langle v,v_k,v_{k-1},\dots,u \rangle\)。因此满足对称性。
传递性：如果从\(u\)到\(v\)存在可达路径\(\langle u,v_1,v_2,\dots,v \rangle\)，并且从\(v\)到\(w\)存在可达路径\(\langle v,v_1',v_2',\dots,w \rangle\)，那么从\(u\)到\(w\)也存在可达路径\(\langle u,v_1,v_2,\dots,v ,v_1',v_2',\dots,w\rangle\)。因此满足传递性。
因此，“可达”关系对于图中的顶点是等价关系。
自反性，对称性和传递性都需要满足。
B.4-5
B.4-6
假设超图的顶点集合为\(V\)，超边集合为\(E\)，考虑构造一个新图\(G=(V\cup E,E')\)。那么对于任何一条超边\(e\in E\)和任意一个节点\(v \in V,(v,e)\in E'\)当且仅当节点\(v\)被\(e\)所关联。
那么根据题目中对这个点和边关联的定义，\(\nexists v_1,v_2\in V,(v_1,v_2)\in E',\nexists e_1,e_2\in E,(e_1,e_2)\in E'\)。因此\(G\)中的所有节点可以划分成两部分：\(V\)和\(E\)。故\(G\)是一个二分图。