图论及其应用第三章答案电子科大
- 格式：docx
- 大小：23.22 KB
- 文档页数：2
习题三：
证明：e是连通图G的割边当且仅当V(G)可划分为两个子
集V1和V2，使对任意u∈V1及v∈V2, G中的路（u，v）必含e.
证明：充分性: e是G的割边，故G−e至少含有两个连通分支，设V1是其中一个连通分支
的顶点集，V2是其余分支的顶点集，对12,uVvV，因为G中的u,v不连通，而在G中
u与v连通，所以e在每一条(u,v)路上，G中的(u,v)必含e。
必要性：取12,uVvV，由假设G中所有(u,v)路均含有边e，从而在G−e中不存在从u与
到v的路，这表明G不连通，所以e是割边。
3.设G是阶大于2的连通图，证明下列命题等价：
（1） G是块
（2） G无环且任意一个点和任意一条边都位于同一个圈上；
（3） G无环且任意三个不同点都位于同一条路上。
（1）→（2）：
G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G1，
显然G1的是阶数大于3的块，由定理，G中的u,v位于同一个圈上，于是G1中u与边e都
位于同一个圈上。
（2）→（3）：
G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u，边e，若u在e上，
则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同
一个闭路上，在e边插入一个点v，由此得到新图G1，显然G1的是阶数大于3的块，则
两条边的三个不同点在同一条路上。
（3）→（1）：
G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V
1, V2, V1, V2
无环，
12
,xvyv
，点u在每一条(x,y)的路上，则与已知矛盾，G是块。
7.证明：若v是简单图G的一个割点，则v不是补图G
̅
的
割点。
证明：v是单图G的割点，则G−v有两个连通分支。现任取x,y∈V(G−v), 如果x,y不
在G−v的同一分支中，令u是与x,y处于不同分支的点，那么，x,与y在G−v的补图中连
通。若x,y在G−v的同一分支中，则它们在G−v的补图中邻接。所以，若v是G的割点，
则v不是补图的割点。
12.对图3——20给出的图G1和G2，求其连通度和边连
通度，给出相应的最小点割和最小边割。
解：12G 最小点割 {6,8}
1
()2G
最小边割{（6,5），（8,5）}
2
5G
最小点割{6,7,8,9,10}
2
()5G
最小边割{（2,7）…（1,6）}
13.设H是连通图G的子图，举例说明：有可能k(H)> k(G).
解：
通常k(H)<𝑘(𝐺).
整个图为G，割点e左边的图H为G的的子图，k(H)=3 k(G)=1，则k(H)>𝑘(𝐺).
e
H
