图论及其应用总结归纳第三章答案(电子科大) 下载本文

精心整理

习题三:

?证明:是连通图G的割边当且仅当V(G)可划分为两个子集V1和V2,使对任意

中的路

必含.

至少含有两个连通分支,设

及, G

证明:充分性: 是的割边,故是其中一个连通分支的顶点

集,是其余分支的顶点集,对?u?V1,?v?V2,因为中的以在每一条

路上,中的

必含。

不连通,而在中与连通,所必要性:取u?V1,v?V2,由假设中所有这表明不连通,所以e是割边。

路均含有边,从而在中不存在从与到的路,

?3.设G是阶大于2的连通图,证明下列命题等价: (1) G是块 (2) G无环且任意一个点和任意一条边都位于同一个圈上; (3) G无环且任意三个不同点都位于同一条路上。 : 是块,任取的一点,一边,在边插入一点,使得成为两条边,由此得到新图的是阶数大于3的块,由定理,中的u,v位于同一个圈上,于是圈上。

: 无环,且任意一点和任意一条边都位于同一个圈上,任取的点u,边e,若在上,则三个不同点位于同一个闭路,即位于同一条路,如不在上,由定理,的两点在同一个闭路上,在边插入一个点v,由此得到新图同一条路上。

连通,若不是块,则中存在着割点,划分为不同的子集块点在每一条

的路上,则与已知矛盾,是块。

,,,

无环,x?v1,y?v2,

,显然

的是阶数大于3的块,则两条边的三个不同点在

,显然

中u与边都位于同一个

2019年-9月

精心整理

?7.证明:若v是简单图G的一个割点,则v不是补图的割点。

证明:是单图的割点,则同一分支中,令是与同一分支中,则它们在

有两个连通分支。现任取

, 如果

的补图中连通。若

不在在

的的

处于不同分支的点,那么,与在

的补图中邻接。所以,若是的割点,则不是补图的割点。

?12.对图3——20给出的图G1和G2,求其连通度和边连通度,给出相应的最小点割和最小边割。 解:??G1??2 最小点割 {6,8}

?(G1)?2 最小边割{(6,5),(8,5)}

??G2??5 最小点割{6,7,8,9,10}

?(G2)?5 最小边割{(2,7)…(1,6)}

?13.设H是连通图G的子图,举例说明:有可能k(H)> k(G). 解: 通常

.

e H 整个图为,割点左边的图为的的子图,

,则

.

2019年-9月