简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的

设n阶无向简单图G有m条边,已知m>=1/2(n-1)(n-2)+1,证明G必连通

rhj19861年前1

avril4ever 共回答了24个问题 | 采纳率87.5%

反之若不连通,设此图可以分成不连通的两部分,分别有a个和n-a个顶点,则这个图边数最多不会超过a(a-1)/2+(n-a)(n-a-1)/2条（也就是两部分都是完全图）.可以用不等式验证这个数小于等于1/2(n-1)(n-2),与已知m>=1/2(n-1)(n-2)+1矛盾.所以必连通

1年前查看全部

离散数学-图画出3个顶点的分别具有2条边,3条边与4条边的所有可能的有向简单图（假定同构的图是无区别的）.

superwei21年前2

breezeyi 共回答了19个问题 | 采纳率94.7%

gjgfjfg

1年前查看全部

图论割集问题图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~回复一楼：有割集的概

图论割集问题
图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~
回复一楼：有割集的概念，只不过讲的比较少而已。
回复二楼：割集就是边的集合，去掉所有这些边后原来的连通图变为两个分离的图，否则图还是连通的（只要该割集中有一条边未去除）。是做的一个小项目中要用到。
回复三楼：采用遍历算法是不是要求出所有可能的边的组合然后从图中去除这些边再对图进行遍历看是否得到两个分支？这样貌似效率不是很高啊！

chlovezl1年前1

生涯岂料 共回答了16个问题 | 采纳率93.8%

回答楼主,图论大多问题的解决,需要用到遍历算法,判断割集我想不会有其它算法,遍历的算法目前是图论中最基本最重要的算法,当然对一些特殊的图可能会有其它方法.遍历算法的计算复杂度不是很大的,是多项式算法,在计算机上可以实现.当然在选取边和点时应考虑技巧性,这恐怕是个难题,否则会出现组合爆炸,就象货郎担问题一样,比如选择点可以首先考虑选取度数最大的点,选取边一定要选不在回路上的边.这需要你的智慧.
割集分为点割集和边割集,对一个图G=(V,E)来说如果存在一个结点集V的子集,从G中删除这些结点后,它的连通分图的个数增多,则称该子集为点割集,对一个连通图来说,删除这些结点后,连通图变为不连通.点割集一般不是唯一的,含有最小结点个数的点割集称为最小点割集,类似可定义边割集和最小边割集,仅含1个点的点割集称为割点,仅含1个边的边割集称为割边,割边也称为桥.
求一个连通简单图的割集的算法,我想可用遍历的算法,目前常用的是深度优先搜索或者广度优先搜索算法来做,这是图论中最基本的算法,这种算法可求出图的连通分图的个数,以此来判断某子集是否是割集.

1年前查看全部

小明的墙上有6幅图画,每个都是有A.B.C.D四种简单图中的某两个组成的,前四幅是：AB BC CD BD组成,那后两幅

小明的墙上有6幅图画,每个都是有A.B.C.D四种简单图中的某两个组成的,前四幅是：AB BC CD BD组成,那后两幅是AD ( ) AC（ ）.

gasgsda1年前5

o指间花开o 共回答了19个问题 | 采纳率94.7%

问题好奇怪,我觉得答案就是AD、AC呀,因为在A、B、C、D四种简单图中选出其中两幅,可以有6种组合方式.AB、BC 、CD 、BD、AD、AC.

1年前查看全部

1.设简单图G是一个Euler图.证明:G中每一个顶点u,均有w(G–u)≤(1/2)d(u).

1.设简单图G是一个Euler图.证明:G中每一个顶点u,均有w(G–u)≤(1/2)d(u).
2.是否存在点数为偶数,边数为奇数的Euler简单图?没有给出理由,有给出实例.

二宝33661年前1

xuaner520 共回答了19个问题 | 采纳率84.2%

1、那个w()是什么意思,还望说明一下.
2、有.把一个四边形的框的一个顶点和一个三角形的框的一定顶点订在一起,那么形成一个有6个顶点、7条边的Euler简单图.

1年前查看全部

离散数学图论的一证明题：若n阶无向简单图是自补图,则n≡ 0(mod=4)或n≡ 1(mod4)

许可二号1年前1

bv456 共回答了16个问题 | 采纳率87.5%

n阶无向简单图有n(n-1)/2条边,它是自补图,则它与其补图的边数相同,所以n(n-1)/2是偶数,所以n(n-1)能够被4整除.
n除以4的余数只能是0,1,2,3.若余数为0,则n是4的倍数,n=4k,此时n(n-1)能够被4整除.若余数为1,则n=4k+1,n(n-1)也能被4整除.若余数为2,则n=4k+2,n(n-1)不能被4整除.若余数为3,则n=4k+3,n(n-1)也不能被4整除.
综上,n除以4的余数只能是0或1,即n≡ 0(mod=4)或n≡ 1(mod4).

1年前查看全部

3.设G是6阶无向简单图（6阶指顶点共6个）,证明G或它的补图 中存在3个顶点彼此相邻.

腊月梅花香1年前1

枉自称侠若许年 共回答了16个问题 | 采纳率87.5%

好专业

1年前查看全部

【离散数学】 下面四组数能构成无向简单图的度数序列有（）

【离散数学】 下面四组数能构成无向简单图的度数序列有（）
A、（2,2,2,2,2 ） B、（1,1,2,2,3） C、（1,1,2,2,2） D、（0,1,3,3,3）

我爱小仙女1年前1

clovegirl 共回答了19个问题 | 采纳率100%

C,首先度数总和应为偶数,所以B不对,然后是D不能构成图,也不能选,A构成的图是一个环,不是简单图,所以选C.

1年前查看全部

计算机基础-离散数学问题求证:简单图G和其补图至少有一个为连通图

zhengyi86031年前1

xmdax 共回答了11个问题 | 采纳率81.8%

如果G不连通,则其补图必连通,下面给出证明:
设u,v是G中任意两个点,(1)如果u,v在G中不连通,即边(u,v)不在G中,由补图定义可知,(u,v)必在G的补图中,即u,v在补图中连通.(2)如果u,v在G中连通,u,v必在G的同一个连通分图中,因为G不连通,故G至少有两个连通分图,在另一个连通分图中任取一点w,则(u,w),(w,v)均不在G中,由补图定义可知(u,w),(w,v)均在G的补图中,故u-w-v是连结u,w的一条路(在补图中),故u,v在补图中连通.

1年前查看全部

离散数学图论的一证明题：若n阶无向简单图是自补图,则n≡ 0(mod=4)或n≡ 1(mod4)

诗情话谊1年前1

阳光满屋 共回答了19个问题 | 采纳率94.7%

n阶无向简单图有n(n-1)/2条边,它是自补图,则它与其补图的边数相同,所以n(n-1)/2是偶数,所以n(n-1)能够被4整除.
n除以4的余数只能是0,1,2,3.若余数为0,则n是4的倍数,n=4k,此时n(n-1)能够被4整除.若余数为1,则n=4k+1,n(n-1)也能被4整除.若余数为2,则n=4k+2,n(n-1)不能被4整除.若余数为3,则n=4k+3,n(n-1)也不能被4整除.
综上,n除以4的余数只能是0或1,即n≡ 0(mod=4)或n≡ 1(mod4).

1年前查看全部

初一计算简单图 送分 6x=1000+y 40x=1000-y

xkmtz1年前1

limi58 共回答了11个问题 | 采纳率90.9%

第一式与第二式相加得：46x=2000 所以x=1000/23 将x代入得y=-17000/23

1年前查看全部

离散证明题：在一个连通简单图中,总存在度数相同的两个结点.求教大神如何证明

离散证明题：在一个连通简单图中,总存在度数相同的两个结点.求教大神如何证明

求教此题如何解答

daibinsz1年前1

生番的ET 共回答了17个问题 | 采纳率94.1%

设连通简单图的结点个数为n,故每个结点的度数为1,2,...,n-1共n-1种情形,但因为有n个结点,由抽屉原理,至少有两个结点度数相同.
那结论怎么不成立?
设x属于A∪C,那么x属于A或者C,x属于B或者D,故x属于B∪D
A∪C是B∪D的子集

1年前查看全部

设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?

设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?
这是刘任任老师离散书上的定理,不过看不懂“G的每个分支至少有|P/2|+1个顶点”这部分,

tayarcy1年前1

影子力 共回答了16个问题 | 采纳率81.3%

对于G的任何一个分支,从中任选一个点,然后把和它相连的点(δ(G)>=|p/2| => 至少|p/2|个和它相连的点)算在一块就有|P/2|+1个点了,所以这个分支里至少有|P/2|+1个顶点.
所以G的每个分支至少有|P/2|+1个顶点.

1年前查看全部

离散数学证明题设G是一个n阶无向简单图,n是大于等于3的奇数．证明图G与它的补图G`中的奇数度顶点个数相等．

四流bb1年前1

dongwan21 共回答了14个问题 | 采纳率92.9%

证：设G(V,E),G'(V,E')．则E'是由n阶无向完全图的边删去E所得到的．所以对于任意结点,u在G和中的度数之和等于u在中的度数．由于n是大于等于3的奇数,从而的每个结点都是偶数度的（度）,于是若在G中是奇数度结点,则它在中也是奇数度结点．故图G与它的补图中的奇数度结点个数相等．

1年前查看全部

图论证明,图G带v个顶点,e条边的连通平面图简单图,其中v大于等于3且圈的长度为L.

图论证明,图G带v个顶点,e条边的连通平面图简单图,其中v大于等于3且圈的长度为L.
证明（1）L大于等于3（2）e小于等于[L/(L-2)]*(v-2)

ID都有人取了1年前2

风流才子s 共回答了14个问题 | 采纳率92.9%

此题应该已经不需要解答了吧

1年前查看全部

2,2,2,2,2在离散数学中能不能构成无向简单图的度数列?

干qq拜仁曼联tt1年前1

tw00030408 共回答了24个问题 | 采纳率83.3%

能构成无向简单图
例如五个顶点组成的圈, 每个顶点度数皆为2

1年前查看全部

给定下列序列,什么是可以构成无向简单图的结点次数序列?

给定下列序列,什么是可以构成无向简单图的结点次数序列?
A.(1,1,2,2,3)
B.(1,1,2,2,2)
C.(0,1,3,3,3)
D.(1,3,4,4,5)
为什么选择B?什么是结点次数序列?

扬花飞雪_yy1年前1

7ddc1f 共回答了14个问题 | 采纳率85.7%

1.括号内,每个数字是结点的邻接点个数,显然不能是0,排除C
2.奇数邻接点个数必须是偶数个(因为每条边都要被计算两次),所以ABD中只有B符合条件
所以只有B可能组成无向简单图

1年前查看全部

设G是6阶无向简单图(6阶指顶点共6个),证明G或它的补图中存在3个顶点彼此相邻

yhlcf12281年前1

假如生命可以重来 共回答了23个问题 | 采纳率82.6%

从G中任取一点,若与它相邻的点不到3个
则补图中的同一点至少有3个相邻点
这3个点中如果有两个点相邻,则这两点与之前的点彼此相邻
若这3个点中没有相邻的点
则取补后(根据第一步情况,既可能是G也可能是补图)这3个点相邻

1年前查看全部

构成无向简单图的条件是什么

wxmn1年前1

shiqingshi 共回答了21个问题 | 采纳率85.7%

无向简单图就是指,没有自环、没有平行边的无向图.满足 |E|

1年前查看全部

离散数学中如何判断一个数列是不是无向简单图的度数列

片泥梅上凉1年前1

hainanlongmao 共回答了22个问题 | 采纳率86.4%

首先要求所有数(度)之和是偶数,其次判断是否为简单图,方法：依次删去度最大的点,递归下去,最后可确定是否是简单图.

1年前查看全部

如何证明N阶无向简单图与其补图奇度顶点个数相等

如何证明N阶无向简单图与其补图奇度顶点个数相等
如题

talkinfacts1年前1

zengwang512 共回答了16个问题 | 采纳率93.8%

这是个假命题,无法证明.
因为N为奇数时,“N阶无向简单图与其补图奇度顶点个数相等”成立.
但是N为偶数时不成立啊!
欢迎讨论
vanmon@163.com

1年前查看全部

已知简单图中各个顶点的度,判断能否画出图

已知简单图中各个顶点的度,判断能否画出图
例 若供选择答案中的数值表示一个简单图中各个顶点的度,能画出图的是( ).
(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5)x05 (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).

大家都想知道1年前1

中谷nn 共回答了21个问题 | 采纳率90.5%

选C,能判断.首先度之和是偶数,其次判断是否为简单图,方法：依次删去度最大的点,递归下去,最后可确定是否是简单图.

1年前查看全部