平面图和其补图之间边数和点数的数量关系的关系
时间: 2024-05-31 11:14:37 浏览: 17
设平面图G的顶点数为V,边数为E,其补图为G',补图是由G中未出现的所有边构成的图。
由于G中的每条边在G'中都不存在,所以G'中的边数为:
E' = C(V, 2) - E
其中C(V, 2)表示从V个顶点中选出2个顶点的组合数,即V(V-1)/2。
因此,G'中的点数为:
V' = V
综上所述,平面图G和其补图G'之间的关系为:
- G'中的顶点数与G中的顶点数相同,即V' = V。
- G'中的边数为V(V-1)/2 - E,其中E为G中的边数。
相关问题
平面图和其补图之间的关系
平面图是指可以画在平面上且没有交叉边的图,而其补图则是将原图的所有边都删除,并将不存在于原图中的边加入其中所形成的图。因此,平面图和其补图之间有如下关系:
1. 平面图和其补图中的每个顶点都对应于另一个顶点。
2. 平面图和其补图中的每条边都对应于另一条边,且这两条边的端点是相同的。
3. 平面图和其补图中的每个面都对应于另一个面,且这两个面的边界是相同的。
因此,平面图和其补图具有一些相似的性质,例如它们的顶点数、边数和面数都相同。同时,它们也有一些不同的性质,例如平面图中存在一个外部面,而其补图中不存在。
G的度数和G的补图的度数之间的关系
设G为一个无向图,V为G的顶点集合,E为G的边集合。则G的补图为一个图G',其顶点集合与G相同,但两个顶点之间在G'中存在一条边,当且仅当在G中这两个顶点之间不存在边。
对于任意一个顶点v ∈ V,其在G中的度数为d(v),在G'中的度数为d'(v)。根据定义,G中没有连接v和u的边,当且仅当G'中连接v和u的边存在。因此,v在G中的度数加上v在G'中的度数等于G中所有顶点的度数之和,即:
d(v) + d'(v) = |V| - 1
其中,|V|表示G中顶点的数量。由于G'中每条边都对应G中没有的边,因此G'中的边数与G中的边数之和等于完全图的边数,即:
|E| + |E'| = |V|(|V| - 1)/2
将上面两个式子带入Euler公式:
|V| - |E| + |F| = 2
其中,|F|为G的面数。则有:
|V| - (|V|(|V| - 1)/2 - |E|) + |F| = 2
化简可得:
|E| + |F| = |V|(|V| - 1)/2 - 1
也就是说,G中边数和面数之和等于完全图边数减1。因此,G的度数和G的补图的度数之和等于完全图中每个顶点的度数,即:
d(v) + d'(v) = |V| - 1 = n - 1
其中,n为G中顶点的数量。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)