谁学过图论,帮我解释一个一点,谢谢-------
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/15 02:58:22
谁学过图论,帮我解释一个一点,谢谢-------
![](http://img.wesiedu.com/upload/e/b5/eb571fc3d662d7a473d7729bf769880d.jpg)
S1不是边割,为什么,(关于图论的)
![](http://img.wesiedu.com/upload/e/b5/eb571fc3d662d7a473d7729bf769880d.jpg)
S1不是边割,为什么,(关于图论的)
割集s指去掉s中所有的边后,g变成具有2个分支的分离图,去掉s中部分边,图仍然是连通的.很显然{c}是割集,s1虽然包含{c},但不是割集
再问: 连通分支图论上怎莫解释的?谢谢
再答: 图g任意的两点都有1条道路,那么这个图是连通的。
连通分支:把顶点v分成非空子集v1,v2,-----vk,当且仅当其中2个顶点a,b同属于1个子集是才是连通的,那么子图g(v1),g(v2)---g(vk)称为g的连通分支
分支大于1的图为分离图
再问:![](http://img.wesiedu.com/upload/7/64/76430a78e7f443d69f5a44d4b246bda1.jpg)
请问 {f,b,e}不懂它为嘛是基本分割?
再答: 原来这两题都是你问的,我解释一下,基本割集首先必须是割集。
割集s指去掉s中所有的边后,g变成具有2个分支的分离图,去掉s中部分边,图仍然是连通的
{f,b,e}他是割集,又包含了T生成树的边b,所以是基本割集
割集有两个要点,1 割集s指去掉s中所有的边后,g变成具有2个分支的分离图(必须是去掉s集合的所有边,而且是2个分支,分成3个以上分支不算) 2,去掉s中部分边,图仍然是连通的(意思是加上割集s中任意一条边图g都是连通的)
再问:
大神!那这个定义不是与你说的相违背了吗,例题中G的边割例如{a,b},按照定义说应该它的真子集{a}和{b}也应该是边割才对!请问这?
再答: 割集的真子集是不能为割集的,1里已经说的很清楚了
再问: 连通分支图论上怎莫解释的?谢谢
再答: 图g任意的两点都有1条道路,那么这个图是连通的。
连通分支:把顶点v分成非空子集v1,v2,-----vk,当且仅当其中2个顶点a,b同属于1个子集是才是连通的,那么子图g(v1),g(v2)---g(vk)称为g的连通分支
分支大于1的图为分离图
再问:
![](http://img.wesiedu.com/upload/7/64/76430a78e7f443d69f5a44d4b246bda1.jpg)
![](http://img.wesiedu.com/upload/4/20/420449b7029256287a2d0339c59e4543.jpg)
再答: 原来这两题都是你问的,我解释一下,基本割集首先必须是割集。
割集s指去掉s中所有的边后,g变成具有2个分支的分离图,去掉s中部分边,图仍然是连通的
{f,b,e}他是割集,又包含了T生成树的边b,所以是基本割集
割集有两个要点,1 割集s指去掉s中所有的边后,g变成具有2个分支的分离图(必须是去掉s集合的所有边,而且是2个分支,分成3个以上分支不算) 2,去掉s中部分边,图仍然是连通的(意思是加上割集s中任意一条边图g都是连通的)
再问:
![](http://img.wesiedu.com/upload/2/87/2872cccd3cf0168ad7b59c9eaccecd3b.jpg)
再答: 割集的真子集是不能为割集的,1里已经说的很清楚了