一道关于图论的问题(连通图,桥)Hi,there~我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.求证:如果一个图的所有节点(Vertex)
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/29 10:37:03
![一道关于图论的问题(连通图,桥)Hi,there~我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.求证:如果一个图的所有节点(Vertex)](/uploads/image/z/8551900-28-0.jpg?t=%E4%B8%80%E9%81%93%E5%85%B3%E4%BA%8E%E5%9B%BE%E8%AE%BA%E7%9A%84%E9%97%AE%E9%A2%98%28%E8%BF%9E%E9%80%9A%E5%9B%BE%2C%E6%A1%A5%29Hi%2Cthere%7E%E6%88%91%E5%88%9A%E5%88%9A%E5%AD%A6%E5%9B%BE%E8%AE%BA%2C%E9%81%87%E5%88%B0%E4%B8%80%E9%81%93%E9%A2%98%E4%B8%8D%E5%A4%AA%E6%87%82%2CTutor%E7%BB%99%E4%BA%86%E7%AD%94%E6%A1%88%2C%E4%BD%86%E6%98%AF%E7%AD%94%E6%A1%88%E6%88%91%E4%B9%9F%E4%B8%8D%E6%98%AF%E5%BE%88%E6%98%8E%E7%99%BD%2C%E8%AF%B7%E5%A4%A7%E5%AE%B6%E5%B8%AE%E5%B8%AE%E6%88%91.%E6%9C%80%E5%A5%BD%E8%83%BD%E7%94%A8%E7%AE%80%E5%8D%95%E7%9A%84%E8%AF%AD%E8%A8%80%2C%E8%B0%A2%E8%B0%A2%E4%BA%86.%E6%B1%82%E8%AF%81%3A%E5%A6%82%E6%9E%9C%E4%B8%80%E4%B8%AA%E5%9B%BE%E7%9A%84%E6%89%80%E6%9C%89%E8%8A%82%E7%82%B9%28Vertex%29)
一道关于图论的问题(连通图,桥)Hi,there~我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.求证:如果一个图的所有节点(Vertex)
一道关于图论的问题(连通图,桥)
Hi,there~
我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.
求证:如果一个图的所有节点(Vertex)的度(Grad)都是偶数,那么这个图就不包含桥.
Tutor给的答案是:假设有桥,然后她画了一个两个分图,左面图中有一点A,右边图中有一点B,AB间用一桥连着. 她写的是:"观察A,发现A的度是奇数,与题设矛盾,所以没有桥".
我不明白的,她怎么观察出A的度是奇数的. 我们因为语言不通,她解释不明白,我也听不懂.请帮帮我谢谢拉
不好意思啊...我才发现..Tutor写的是:A和B是两个分图,中间用桥连着. 观察分图A,发现A图中所有节点的度之和为奇数,与题设矛盾. 看了这个后我更糊涂了....
一道关于图论的问题(连通图,桥)Hi,there~我刚刚学图论,遇到一道题不太懂,Tutor给了答案,但是答案我也不是很明白,请大家帮帮我.最好能用简单的语言,谢谢了.求证:如果一个图的所有节点(Vertex)
是这样的.
图G-AB 分为图GA和图GB.
那么GA=G-GB
由于每减去一个点,度之和的奇偶性不变.
注:减去一个点,其度为N,那么度之和减少2N.因为与之相邻的点的度都减1.
那么GA的度的和应该还是偶数.可是明显的图GA中除A外的点的度是偶数.A的度是奇数.
那么GA 的度的和是奇数.故矛盾.
从而得证.