msww.net
当前位置:首页 >> 设G是无向简单图,有6个顶点,7条边,证明G的连通... >>

设G是无向简单图,有6个顶点,7条边,证明G的连通...

用反证法证明:假设有3个连通分支那么只能以下三种情况:1. 两个孤立结点,和4个结点7条边显然这不是简单图2. 一个孤立结点,和2结点和3结点的连通分支2结点的连通分支最多1条边3结点的连通分支最多3条边显然不满足条件3. 3个2结点图,最多只能有3条边综上,G的连通分支个数不超过2

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

设G为n阶无向简单图,若G不连通,证明G的补图G必连通. 悬赏: 0 答案豆 提问人: 匿名网友 您可能感兴趣的试题 6阶2-正则图有几种非同构的情况? 已知3-正则图G的阶数n与边数m满足m=2n-3,证

点+面-边=2边数=9

设图G是简单连通平面图,且其每个区域至少有4条边围成,证明图G中必存在一个顶点,其度数小于等于3. 悬赏: 0 答案豆 提问人: 匿名网友 您可能感兴趣的试题 画出两个具有6个顶点、11条边的非

设连通图G有(n+1)个顶点,若每个顶点连出至少两条边,那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立.否则,那么至少有一个顶点只连出一条边.不妨设为A,由于去掉这条边AB后不影响其他点的连通性,那么剩下的n个点之间有归纳假设至少有(n-1)条边,所以G至少有n条边.

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

可以证明 1:连通简单图的边数>=n-12:无圈图的边数<=n-1简单说一下思路:1,用第二数归很好说明2,因为无圈,所以每条边都是“桥”,每切一条边增加一个连通分支,至多有n个连通分支,而一开始至少有一个连通分支,所以至多有n-1条边如有不清楚的地方,欢迎追问

网站首页 | 网站地图
All rights reserved Powered by www.msww.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com