无向图G中恰有两个奇度定点,证明两个奇度定点必然联通

斜月如钩2022-10-04 11:39:541条回答

已提交，审核后显示！提交回复

共1条回复

雷凡凡共回答了18个问题 | 采纳率88.9%: 首先,不管无向图有几条边,一条边总连着2个顶点,所以：
无向图所有顶点度数之和为偶数!
也得到,无向图的任一联通部分也是无向图且适用上述结论.
现有奇度顶点A,在它所在的联通部分,必存在另一点B是奇度顶点,使得该联通部分满足一开始我说的那个结论.
因为G中恰有2个奇度顶点,所以A所在联通部分就是无向图G!因为A、B联通,所以命题得证!; 1年前

相关推荐

设无向图G=(y,E),其中y={l,2,3,4,5},E= {(1,2,4),(2,5,5),(1,3,2),(2,4 设无向图G=(y,E),其中y={l,2,3,4,5},E= {(1,2,4),(2,5,5),(1,3,2),(2,4,4),(3,4,1),(4,5,3),(1,5,8)},每条边由一个三元组表示,三元组中前两个元素为与该边关联的顶点,第三个元素为该边的权.请写出图G中从顶点1到其余各点的最短路径的求解过程.要求列出最短路径上的各顶点,并计算路径长度 花开无人知1年前1: acoolpeng 共回答了17个问题 | 采纳率88.2%

最坏情况:初始状态反序,则需要进行n-1趟扫描,每趟扫描要进行n-i次关键字的比较,且每次需移动记录3次

1年前查看全部

设无向图G中有n个结点,n-1条边,用归纳法于n,证明G是连通图则G中无回路. 老圆1年前1: 旺曲卡共回答了29个问题 | 采纳率93.1%

假设这个无环图是不连通的,则设图G有k个连通分支G1,G2,…,Gk（k≥2）,设G1有x1个结点,G2有x2个结点,G3有x3个结点……Gk有xk个结点,则有x1+x2+x3+……+xk=n,又因为Gi有xi-1条边,所以图G有(x1-1)+(x2-1)+(x3-1)+……+(xk-1)=n-k条边,少于已知的n-1条边,所以假设不成立,该无环图一定是联通的.

1年前查看全部

无向图G中,有边21条,有3个4度顶点,4个3度顶点,其余顶点的度数是2.计算该图的顶点数 叮当3151年前1: lsq115 共回答了19个问题 | 采纳率84.2%

设顶点的度数是2的有x个
(3*4+4*3+x*2)/2=21 x=9
顶点=3+4+x=16

1年前查看全部

离散数学,无向图G中存在欧拉回路的充分必要条件是________________________. 微蓝的笑颜1年前2: 心愿1111 共回答了16个问题 | 采纳率87.5%

离散数学的教材上就可以查到：
无向图G中存在欧拉回路的充分必要条件是_G连通且无奇度数顶点_.

1年前查看全部

大家在问