Question

离散数学一道证明题

证明:一个联通无向图G中的结点v是割点的充分条件是存在两个结点u和w，使得结点u和w的每一条路都通过v

Answer 1

若结点v是连通图G=<V,E>的一个割点，设删去v得到子图G',则G'至少包含2个连通分支。设其为G1=<V1,E1>，G2=<V2,E2>，任取u∈V1，w∈V2，因为G是连通的，故在G中必有一条连接u和w的路C,但u和w在G'中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v
反之，若连接图G中某两个结点的每一条路都通过v，删去v得到子图G'，在G'中这两个结点必然不连通，故v是图G的割点。
祝你成功！！！！！！！！！！！！！！！！！

Answer 2

希望你看得懂：
若结点v是连通图G=<V,E>的一个割点，设删去v得到子图G',则G'至少包含2个连通分支。设其为G1=<V1,E1>，G2=<V2,E2>，任取u∈V1，w∈V2，因为G是连通的，故在G中必有一条连接u和w的路C,但u和w在G'中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v
反之，若连接图G中某两个结点的每一条路都通过v，删去v得到子图G'，在G'中这两个结点必然不连通，故v是图G的割点。
参考资料：《离散数学P284》（上海科学技术文献出版社）

Answer 3

证明:假设v是图G的一个割点,则G-v是至少有两个分支的分离图.令U表示由其中一个分支的顶点构成的集合,W表示由其余顶点构成的集合,从而(u,w)构成V(G)-v的一个划分.于是任何两个顶点u属于U和w属于W各在G-v的不同分支中.因此,G中的每一条(u,w)道路都含有v.
反之,若v在G的每一条联结u和w的道路上,则在G-v中不能有一条联结u和w的道路,从而G-v是不连通的,即v不是割点.

Answer 4

那么对于结点u和w ，由于结点u和w的每一条路都通过v，那么去掉点v和点v的所有相关的边之后，u和w将没有通路相连，所以这个图将不再是连通图。根据割点的定义可知，点v是割点。

Answer 5

证明：
v、u、w∈V(G)，用ω(G)表示无向图G的连通分支，则v是G的割点可定义为ω(G-v)> ω(G)。

因为结点u和w的每一条路都通过v，即在G中u和w连通。又考虑在G-v中u和w不连通。故有连通分支增加，即ω(G-v)> ω(G)。

所以v是G的割点。