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

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

离散数学一道证明题证明:一个联通无向图G中的结点v是割点的充分条件是存在两个结点u和w,使得结点u和w的每一条路都通过v
若结点v是连通图G=的一个割点,设删去v得到子图G',则G'至少包含2个连通分支.设其为G1=,G2=,任取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的割点.

http://zhidao.baidu.com/question/42970061.html

我是初中生

第一次听说离散数学，不过我对新东西很感兴趣。

高中的？

你要是两年前问这个问题我就能给你答案了。

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

这是大二的数学题吧，如果你十年前问我，我能回答你，现在。。。。。。忘了！

汗……我还没学

书上的定理! 见左孝凌《离散数学》P.284. 一模一样！
当然，是“连通无向图”，不是“联通”。

悄悄的我来了
正如我要悄悄的走
十分同意
" 你要是两年前问这个问题我就能给你答案了。
回答者：tunx03 - 经理 五级 1-2 22:16"
走了 带走你的2分

听都没听过，闪人。

没听说过!是大学的吗!?

证明:假设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不是割点...

全部展开

证明:假设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不是割点.

收起

证明：
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的割点。

证明:一个连通无向图G中的结点v是割点的充分条件是存在两个结点u和w，使得结点u和w的每一条路都通过v
u、w∈V(G)且结点u和w的每一条路都通过v
=>在G中u和w连通
有因为在G-v中u和w不连通,且v∈V(G)
=>ω(G-v)> ω(G)
=>v是G的割点
详细参考《离散数学》中的无向连通图...具体忘了.....

全部展开

证明:一个连通无向图G中的结点v是割点的充分条件是存在两个结点u和w，使得结点u和w的每一条路都通过v
u、w∈V(G)且结点u和w的每一条路都通过v
=>在G中u和w连通
有因为在G-v中u和w不连通,且v∈V(G)
=>ω(G-v)> ω(G)
=>v是G的割点
详细参考《离散数学》中的无向连通图...具体忘了..

收起

希望你看得懂：
若结点v是连通图G=的一个割点，设删去v得到子图G',则G'至少包含2个连通分支。设其为G1=，G2=，任取u∈V1，w∈V2，因为G是连通的，故在G中必有一条连接u和w的路C,但u和w在G'中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v
反之，若连接图G中某两个结点的每一条路都通...

全部展开

希望你看得懂：
若结点v是连通图G=的一个割点，设删去v得到子图G',则G'至少包含2个连通分支。设其为G1=，G2=，任取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》（上海科学技术文献出版社）

收起

问老师吧，太难了