习题81. 给定下面两个图的集合表示，画出他们的图形表示。
>=<111,E V G ,其中},,,,{543211v v v v v V =，)},(),,(),,(),,(),,{(43415351211v v v v v v v v v v E =>=<222,E V D ,其中},,,,{543221v v v v v V =，},,,,,,,,,{43412552212><><><><><=v v v v v v v v v v E 注：2D 改为2G 解：2. 先将下图中各图的顶点标定次序，然后写出各图的集合表示。
解：顶点标定如下：图G1图G2V5V5（1）（2）（3）(1) 其中},,,{43211v v v v V =，)},(),,(),,(),,(),,{(43324131211v v v v v v v v v v E = (2) 其中},,,,{543221v v v v v V =，)},(),,(),,(),,{(545452212v v v v v v v v E = (3) 其中},,,,{543231v v v v v V =，},,,,,,,,,,,{4534133251213><><><><><><=v v v v v v v v v v v v E3. 写处下图中各图的度数列，对有向图还要写出出度列和入度列。
解：（1）4,2,2,2 （2）度数列：1,4,1,5,1；出度列：1，2，0，3，0；入度列：0，2，1，2，14. 设无向图中有6条边，3度与5度顶点各1各，其余的都是2度顶点，问该图有几个顶点？ 注：“各1各”改为“各1个”。
解：设该图有x 个顶点，3×1+5×1+2×(x-1-1)=6×2，x=45. 画以（1，2，2，3）为度数列的简单图和非简单图各一个。
解：（1）（2）（3）V5（1）（2）3v 1v 23v6．证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。
证明：设有向完全图有n 个结点v 1, v 2,…, v n ， 结点v i 的入度为d -(v i )=n-1，出度为d +(v i )=n-1， 所有结点入度的平方之和为()()()21122i-1-n 1-n )(v d ∑∑====n i ni n ，所有结点出度的平方之和为()()()21122i 1-n 1-n )(v d∑∑==+==ni ni n ，故所有结点入度的平方之和等于所有结点的出度平方之和。
7．写出下图相对于完全图的补图。
解：8．证明下图中的两个图不同构。
证明：将图的顶点标定如下：如果这两个图同构，那么对应结点的度数应相同。
度数为3的两个结点v 1与v 1'相对应。
但与v 1邻接的三个结点中一个结点v 2度数为2，两个结点v 3 ,v 4度数为1，而与v 1'邻接的三个结点中有两个结点v 2',v 3'度数为2，一个结点v 4'度数为1，故他们不同构。
9．一个图如果同构于它的补图，则该图称为自补图。
1）试给出一个五个结点的自补图。
2）是否有三个结点或六个结点的自补图。
3）一个图是自补图，其对应的完全图的变数必为偶数。
注：3）中“变数”应为“边数”。
解： 1)v 3 v 4'1v'2v '3v2)没有。
由3），n(n-1)/2应为偶数，而n=3,6时，n(n-1)/2为奇数。
3）若n 阶图G 与其补图G 同构，G 与G 的边数应相同，因此G 与G 的总边数为偶数。
而G 与G 的总边数为对应的完全图的边数，即n(n-1)/2，故对应的完全图的边数为偶数。
10．证明简单图的最大度小于结点数。
证明：设简单图G 有n 个结点。
对任一结点u ，由于G 没有环和平行边，u 至多与其余n-1个结点中每一个有一条边相连接，即deg(u)≤n -1，因此，⊿(G)＝max deg(u)≤n -1。
11．在无向图G 中，从结点u 到结点v 有一条长度为偶数的通路，从结点u 到结点v 有一条长度为奇数的通路，则在G 中必有一条长度为奇数的回路。
证明：设从结点u 到结点v 长度为偶数的通路是ue 1u 1e 2u 2…e 2k v ，长度为奇数的通路是ue 11u 11e 12u 12…e12h-1v ，那么路ue 1u 1e 2u 2…e 2k ve 12h-1…u 12e 12u 11e 11u 就是一条回路，它的边数＝2k+(2h-1)＝2(h+k)-1，是奇数，故这条回路的长度是奇数。
12．若无向图G 中恰有两个奇数度的结点，则这两结点间必有一条路。
证明：反证法。
证明：设G 中的两个奇数度结点分别为u 和v 。
假设u 和v 不连通，即它们之间无任何通路，则G 至少有两个连通分支G 1，G 2，使得u 和v 分别属于G 1和G 2 (否则,它们之间必有通路)，于是G 1和G 2各含有一个奇数度结点。
这与握手定理的推论矛盾（教材P136定理8.1.2）。
因而u 和v 一定是连通的。
13．若图G 是不连通的，则G 的补图G 是连通的。
注：图G 是无向图。
证明：若图G ＝<V ，E>是不连通的，可设图G 的连通分支是G(V 1)，G(V 2)，…，G(V m )(m≥2)。
由于任意两个连通分支G(V i )与G(V j )(i≠j)之间不连通，因此两个结点子集V i 与V j 之间的所有连线都在图G 的补图G 中。
任取两个结点u 和v ，有两种情形：(1)u 和v 分别属于两个不同结点子集V i 与V j 。
由上可知G 包含边(u,v)，故u 和v 在G 中是连通的。
(2)u 和v 属于同一个结点子集V i 。
可在另一个结点子集V j 中取一个结点w ，由上可知边(u ,w)及边(v,w)均在G 中，故邻接边(u,w)和(v,w)组成的路连接结点u 和v ，即u 和v 在G 中也是连通的。
由此可知，当图G 不是连通图时，G 必是连通图。
14. 设G 是n 阶自补图，证明n=4k 或n=4k+1，其中k 为正整数。
证明：由第9题3)，n(n-1)/2须是偶数。
(1)当n=4k 时，n(n-1)/2=4k(4k-1)/2=2k(4k-1)为偶数； (2)当n=4k+1时，n(n-1)/2=(4k+1)4k/2=2k(4k+1)为偶数；(3)当n=4k+2时，n(n-1)/2=(4k+2)(4k+1)/2=(2k+1)(4k+1)为奇数； (3)当n=4k+3时，n(n-1)/2=(4k+3)(4k+2)/2=(4k+3)(2k+1)为奇数； 故n=4k 或n=4k+1。
15. 已知n 阶无向简单图G 有m 条边，试求G 的补图G 的边数m ’。
解：m n n m --='2)1(16．分析下图，求1）从A 到F 的所有通路。
2）从A 到F 的所有迹。
注：1）改为求从A 到F 的所有初级通路。
解：1）ABCF,ABCEF,ABEF,ABECF,ADEF,ADEBCF,ADECF2)ABCF,ABCEF,ABEF,ABECF,ADEF,ADECF,ADECBEF,ADEBCF,ADEBCEF17．一个图是单侧连通的，当且仅当它有一条经过每一结点的路。
注：单侧连通即单向连通证明：充分性。
如果图G 中有一条通路u 1u 2…u n ，它至少包含每个结点一次，则G 中任两个结点u i ,u j (i ＜j)，u i 可达u j ，故G 是单向连通的。
必要性。
如果G 单向连通，必可作一通路经过图中所有各点。
若不然，设有一通路u 1u 2…un不包含某一结点v ，下面分三种情况讨论。
(1)若v 可达u 1，则可作通路v …u 1u 2…u n ，包含v 。
(2)若u n 可达v ，则可作通路u 1u 2…u n …v ，包含v 。
(3)若v 不可达u 1，且u n 不可达v ，顺序查找u 1u 2…u n 中各结点，从中找出第一个v 可达的结点u i ，则u i －1可达v 。
故可作通路u 1u 2…u i －1…v …u i …u n ，包含v 。
因此，总可以在原有通路u 1u 2…u n 的基础上，构造新的通路，包含原通路未包含的结点，最终作出经过图中所有各点的通路。
18. 无向图G 如下图所示。
1) 求G 的全部点割集和边割集，并指出其中的割点和割边。
解：点割集：{C},{E},{B,D}，节点C 和节点E 都是割点。
虽然删除节点A 和C 图成为不连通的，但因{C}是{A,C}的真子集，所以{A,C}不是点割集。
边割集：{E5},{E6}，{E1，E2}, {E1，E3}, {E1，E4}, {E2，E3}, {E2，E4}, {E3，E4},E5和E6为割边。
2）求G 的点连通度)(G k 和边连通度)(G λ。
解：)(G k =1，)(G λ=1。
19．求出下图中有向图的邻接矩阵A 和可达性矩阵。
解：E 365v 34邻接矩阵： 可达性矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0000000100000010110100000⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡100000110100101011110000120．写出下图中图G 的完全关联矩阵。
无向图完全关联矩阵定义：设>=<E V G ,是一个无向图，,,{21v v V =…，n v }，},...,,{21m e e e E =，则矩阵)()(ij m G M =称为G 的完全关联矩阵(Complete Incidence Matrix)，其中10i jij i jv e m v e ⎧⎪=⎨⎪⎩ 若关联 若不关联解：各边标注如下：完全关联矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡000010110000100101110100000011010000101001000000001011。
