算法导论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)}$。
那么最终有：
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 v0,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 v0,v_1,v_2,\dots,v{\mathbf{i}} \rangle$
可以发现，这个新环的长度比原来缩短了$k-i$。
否则，如果$\exists i,j,0< i< j< k,v_i=v_j$成立，那么可以构造出一个新的环：
$\langle v0,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,v1,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$是一个二分图。