一道关于图论的问题(连通图,桥)
来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/10/03 00:23:49
一道关于图论的问题(连通图,桥)
Hi,there~
我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.
求证:如果一个图的所有节点(Vertex)的度(Grad)都是偶数,那么这个图就不包含桥.
Tutor给的答案是:假设有桥,然后她画了一个两个分图,左面图中有一点A,右边图中有一点B,AB间用一桥连着. 她写的是:"观察A,发现A的度是奇数,与题设矛盾,所以没有桥".
我不明白的,她怎么观察出A的度是奇数的. 我们因为语言不通,她解释不明白,我也听不懂.请帮帮我谢谢拉
不好意思啊...我才发现..Tutor写的是:A和B是两个分图,中间用桥连着. 观察分图A,发现A图中所有节点的度之和为奇数,与题设矛盾. 看了这个后我更糊涂了....
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 的度的和是奇数.故矛盾.
从而得证.
图G-AB 分为图GA和图GB.
那么GA=G-GB
由于每减去一个点,度之和的奇偶性不变.
注:减去一个点,其度为N,那么度之和减少2N.因为与之相邻的点的度都减1.
那么GA的度的和应该还是偶数.可是明显的图GA中除A外的点的度是偶数.A的度是奇数.
那么GA 的度的和是奇数.故矛盾.
从而得证.
无向连通图的连通分量!
强连通图的强连通分量(连通图的连通分量)是不是就它本身
关于欧拉一笔画问题欧拉说要能一笔画完,必须是全是偶点的连通图或者只有2个奇点的连通图但是下面这个图形有4个几点,为什么也
电气连线符号:如图,请说明数字间的电流连通问题
有向图G的强连通分量是指-----,一个连通图的---是一个极小连通子图
离散数学问题:证明连通图中至少有一颗生成树
有关证明连通图是树的问题.
离散数学中有关图论中的极大连通子图的概念理解
关于《过秦论》的一道问题
关于一道概率的问题,画表格或者树状图、
非平凡连通图的定义是什么啊?还有欧拉图
高数区域问题为什么下图的D不是连通的啊?不好意思,手机上提的问题,图上来了