图论-三四章习题

1证明方法与p.47定理3类似

3.设无环图G是阶数大于2的连通图，则下列命题等价（1）G是块，即G是2-连通的；（2）G的任意两个顶点在某个圈上；（3）G的任一个顶点和任一条边在某个圈上；（4）G的任意两边在某个圈上；（5）G的任意两个顶点u，v及任一边e，总存在连接u，v且过e的路；（6）G的任意三个顶点，总存在连接其中任意两个顶点，并且通过第三个顶点的路（7）G的任意三个顶点，总存在连接其中任意两个顶点，并且不过第三个顶点的路证明：12：p.48定理423：令u是任一顶点，vw是任一边，由（2），存在2包含u,v的圈C。若w属于C，则结论已成立。若w不属于C，v不是G的割点。故存在不过v点的（u,w）路P，设x是由w出发、沿P前进，与C相交的第一个顶点，则C中含u的(v，x)-段+P中的(w，x)-段+vw构成的圈C’即为所求。34：类似2345：易得43，令u，v是任意两个顶点，e是任一边。由（3）存在C1，C2分别包含u，e及v，e。如果u在C2上或v在C1上，则结论已成立。若不然，从u出发，沿C1前进，到达C1与C2的第一个交点，然后沿C2含e的部分到达v，即为所求之路。56：设u，v是任意两个顶点，w是任意第三个顶点，而是w关联的变，由（5）存在过e的（u，v）路，此路必过w。67：设u，v，w是任三点，存在过v的（u，w）路P，则P中（u，v）段，即为过u，v而不过w的路。71：对G中任意两顶点u，v及任意第三点w，在G-w中存在（u，v）路，即G-w连通。从而G是2连通的。3

7、证明若v是单图G的割点，则它不是G的补图的割点。证明：v是单图G的割点，则G-v至少两个连通分支。现任取,如果x,y在G-v的同一分支中，令u是与x,y处于不同分支的点，那么，通过u，可说明，x与y在G-v的补图中连通。若x,y在G-v的不同分支中，则它们在G-v的补图中邻接。所以，若v是G的割点，则v不是其补图的割点。证明：设T是G的一棵生成树。由于G有n-2个割点，所以，T有n-2个割点，即T只有两片树叶，所以T是一条路。这说明，G的任意生成树为路。

5.求证：恰有两个非割点的简单连通图是一条路。一个单图的任意生成树为路，则该图为圈或路，若为圈，则G没有割点，矛盾，所以，G为路。4.参见习题2，p.43第11题432.（1）证明：考虑G=Cn˅H的最小点割V。根据联图的定义，则必有V包含Cn

或者H，否则G-V后一定连通。如果Cn∈V，则由H是K连通的可知|V|=n+k。若H∈V，则V中至少还需要包含Cn中两个不相邻的顶点，也可得|V|=n+k。故G是n+k连通的。（2）在Cn

上任取相邻的两点x,y，设这两个点在Cn上的两条路分别为P1和P2。考虑宽为n+k的x-y容器，因为H仅包含n+k-2个点，经过H中的点，且独立的（x，y）路最多有n+k-2个，且每条路的长度都为2。因此在每个容器中必包含P1和P2。故dn+k(x,y)=n-1。习题44.参见p.86，推论7.证明：将G中孤立点除去后的图记为G1，则G1无奇点，且每个点度数至少为2。则从某点出发可以找到G1的一个圈C1。令G2=G1-C1，除去孤立点后，显然G2无奇点，且每个点度数至少为2。重复以上过程，直到Gm-Cm全为孤立点为止，则得到结论。5

9.设G是非平凡的欧拉图，且v∈V(G)。证明：G的每条具有起点v的迹都能扩展成G的欧拉环游当且仅当G-v是森林。证明：必要性若不然，则G-v有圈C。考虑G1=G-E(C)的含有顶点v的分支H。由于G是非平凡欧拉图，所以G1的每个顶点度数为偶数，从而，H是欧拉图。H是欧拉图，所以存在欧拉环游T.对于T，把它看成v为起点和终点的一条欧拉迹，显然不能扩充为G的欧拉环游。这与条件矛盾！

充分性:若不然，设Q=(v,w)是G的一条不能扩充为G的欧拉环游的最长迹，显然v=w,且Q包含了与v关联的所有边。即Q是一条闭迹。

于是，G-v包含G-Q且G-Q的每个顶点度数为偶数.于是，G-Q的非平凡分支是欧拉图，说明有圈，即G-v有圈，这与条件矛盾.610.证明（1）若G不是二连通的，则G不连通或存在割点v，有w（G-v）≥2，故G不是H图。（2）设G是2部图，不妨假设|X|<|Y|,则有w（G-X）=|Y|>|X|,故G不是H图。11.证明：设C是G中的一条H路，于是有w(G-S)≤w(C-S)≤|S|+112.课上例题

证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1GG1vG1的度序列为：(d1+1,d2+1,…,dn+1,n)

由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且d(n+1)-m<(n+1)-m。于是由度序列判定定理知：G1是H图，得G有H路。713.证明：若G不是H图，则G度弱于某个

，

且有则所以矛盾，故假设不成立，G是H图817、证明：设T是G的一颗最优生成树，将T的每条边加倍得到图T’,则T’的每个顶点度数均为偶数，所以T’有一个欧拉环游Q中某些顶点可能重复，且W(Q)=2W(T)。在Q中，从v3开始，凡前面出现过的顶点全部删去，得到G的n个顶点的一个排列π。由于G是完全图，所以该排列可以看成是G