一道关于图论的问题(连通图,桥)Hi,there~我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.求证:如果一个图的所有节点(Vertex)
来源:学生作业学帮网 编辑:学帮网 时间:2024/05/31 13:38:05
一道关于图论的问题(连通图,桥)
Hi,there~
我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.
求证:如果一个图的所有节点(Vertex)的度(Grad)都是偶数,那么这个图就不包含桥.
Tutor给的答案是:假设有桥,然后她画了一个两个分图,左面图中有一点A,右边图中有一点B,AB间用一桥连着. 她写的是:"观察A,发现A的度是奇数,与题设矛盾,所以没有桥".
我不明白的,她怎么观察出A的度是奇数的. 我们因为语言不通,她解释不明白,我也听不懂.请帮帮我谢谢拉
不好意思啊...我才发现..Tutor写的是:A和B是两个分图,中间用桥连着. 观察分图A,发现A图中所有节点的度之和为奇数,与题设矛盾. 看了这个后我更糊涂了....
是这样的.
图G-AB 分为图GA和图GB.
那么GA=G-GB
由于每减去一个点,度之和的奇偶性不变.
注:减去一个点,其度为N,那么度之和减少2N.因为与之相邻的点的度都减1.
那么GA的度的和应该还是偶数.可是明显的图GA中除A外的点的度是偶数.A的度是奇数.
那么GA 的度的和是奇数.故矛盾.
从而得证.
一道关于图论的问题(连通图,桥)Hi,there~我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.求证:如果一个图的所有节点(Vertex)
强连通图的强连通分量(连通图的连通分量)是不是就它本身
连通分支是不是连通图?
关于连通图与强连通图边数n个顶点的连通图最多多少边、最少多少条边,n个顶点的强连通图最多多少条边、最少多少条边求大仙指教
连通图的最小生成树是不是唯一的?如题!http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html帮我看看.谢谢了!
电气连线符号:如图,请说明数字间的电流连通问题
有向图G的强连通分量是指-----,一个连通图的---是一个极小连通子图
离散数学问题:证明连通图中至少有一颗生成树
什么叫连通图?还有一笔画问题解法
已知图G不是连通的,求证它的补图必为连通的谁会啊
对于数据结构中“连通分量”和“生成树”的定义问题对于数据结构中“连通分量”和“生成树”的,我理解其表示的是什么,但对于其定义“连通分量指的是无向图中的极大连通子图”和“
关于欧拉一笔画问题欧拉说要能一笔画完,必须是全是偶点的连通图或者只有2个奇点的连通图但是下面这个图形有4个几点,为什么也能一笔画完呢?图就是一个正方形,然后再连接4条边的中点,
离散数学弱连通图和单向连通图怎么区分
判断一个图是否为强连通图、单向连通图、弱连通图.输入为有向图的邻接矩阵.
离散数学中树的概念问题离散数学中图论那章里有树的定义,说连通的无回路的无向图就是树,我不解,既然是连通的,怎么可能无回路呢?万分感激!
N个顶点的连通图至少有几条边如题
非平凡连通图的定义是什么啊?还有欧拉图
7.6 n个顶点的连通图至少有几条边?强连通图呢?答: n个顶点的连通图至少有n-1条边,强连通图至少有2(n-1)条边.