证明如果无向图G恰有俩个不同的奇度数的顶点a,b,那么a到b是可达的
时间: 2024-03-28 18:39:47 浏览: 35
首先,我们先证明一个引理:在一个无向图中,度数为奇数的顶点的个数一定是偶数。
证明:对于一个无向图G,设其顶点集为V,任取一条边AB,则A的度数加1,B的度数加1,因此G中所有点的度数之和等于2E(E为边数)。又因为每个点的度数是非负偶数或非负奇数,所以2E是偶数,因此度数为奇数的顶点的个数一定是偶数。
回到原命题,设a和b的奇度数分别为k和m,则k和m为奇数,因此k+m为偶数。由引理可知,G中奇度数顶点的个数为偶数,因此存在一条从a到b的路径,路径上经过的顶点的度数都是偶数,因此a和b的度数必定都是偶数。偶度数顶点有一个重要的性质,即任意一个偶度数顶点都可以通过一系列的边到达其他偶度数顶点。因此,a和b都可以通过一系列的边到达其他偶度数顶点,并最终到达彼此,即a到b是可达的。
相关问题
无向图G是欧拉图当且仅当G中无奇度定点正确吗
不完全正确。
充分性:如果无向图G中没有奇度顶点,则G的每个顶点的度数都是偶数。由于每条边都会贡献2个顶点的度数,因此G的边数也是偶数。由于欧拉图的定义是一个图中存在一条欧拉回路,当且仅当这个图的每个顶点的度数都是偶数,且这个图连通。因此,如果无向图G中没有奇度顶点,则G是欧拉图。
必要性:如果无向图G是欧拉图,则G的每个顶点的度数都是偶数。由于每条边都会贡献2个顶点的度数,因此G的边数也是偶数。现在假设G中存在奇度顶点,则这些奇度顶点的个数一定是偶数(因为每个顶点的度数都是偶数,所以只可能是0个,2个,4个……)。但是由于每条边都会贡献2个顶点的度数,因此G的边数应该是奇数,与G的边数为偶数矛盾。因此,如果无向图G是欧拉图,则G中不存在奇度顶点。
综上所述,无向图G中没有奇度顶点是G是欧拉图的充分条件,但不是必要条件。
一个无向图,确定它的的顶点数,边数,度数列,他是否是唯一的
对于这个问题,我可以回答。对于一个无向图,顶点数可以通过计算图中顶点的数量得出,边数可以通过计算图中边的数量得出。度数列是指每个顶点的度数,可以通过计算每个顶点相邻的边的数量得出。但是,无向图的顶点数、边数和度数列并不一定是唯一的,因为可以构造不同的无向图具有相同的顶点数、边数和度数列。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)