离散数学一道证明题证明:一个联通无向图G中的结点v是割点的充分条件是存在两个结点u和w,使得结点u和w的每一条路都通过v
来源:学生作业帮助网 编辑:作业帮 时间:2024/05/13 13:53:21
离散数学一道证明题证明:一个联通无向图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=
反之,若连接图G中某两个结点的每一条路都通...
全部展开
希望你看得懂:
若结点v是连通图G=
反之,若连接图G中某两个结点的每一条路都通过v,删去v得到子图G',在G'中这两个结点必然不连通,故v是图G的割点。
参考资料:《离散数学P284》(上海科学技术文献出版社)
收起
问老师吧,太难了