设G为9阶无向图,每个结点度数不是5就是6,则G中至少有 ( ) 个5 度结点。
时间: 2024-04-04 22:30:37 浏览: 46
设G中有n个5度结点,则有9-n个6度结点。因为每个结点的度数只能是5或6,所以G中总共有 $5n+6(9-n)=54-n$ 条边。根据握手定理,G中边数应该是所有结点的度数之和的一半,即 $\frac{1}{2}\sum_{v\in G} d(v)$。由于每个结点的度数都不是5就是6,所以 $\sum_{v\in G} d(v)$ 必定是偶数。因此,$5n+6(9-n)=54-n$ 必须是偶数,解得 $n\geq 3$。因此,G中至少有3个5度结点。
相关问题
无向图G有11条边,4个3度结点,其余结点均为5度结点,则G的结点数为
对于无向图 G,它所有边的数目等于每个顶点的度数之和的一半,即 $|E| = \frac{1}{2}\sum_{v\in V}deg(v)$。因此,有:
$11 = \frac{1}{2}\sum_{v\in V}deg(v)$
对于度数为 3 的结点数为 4,度数为 5 的结点数为 $|V|-4,代入上式得:
$11 = \frac{1}{2}[4\times3 + (|V|-4)\times 5]$
化简后得:
$|V| = 9$
因此,G 的结点数为 9。
2设口阶圈G中有m 条边,每个结点的度数不是k的是k+1,若G中有小个k度顶点:Nos 个k+1度顶点,则NK=
根据握手定理,对于一个无向图 G,其所有顶点的度数之和等于 2m,其中 m 为边数。设 G 中有 n 个顶点,则有以下方程成立:
n*k + Nos*(k-1) + NK*(k+1) = 2m
又因为 G 中有 NK 个 k 度顶点和 Nos 个 k+1 度顶点,所以 n = NK + Nos,代入上式得:
(NK + Nos)*k + Nos*(k-1) + NK*(k+1) = 2m
化简得:
NK = (2m - k*Nos)/(k+1)
因此,NK 的值为 (2m - k*Nos)/(k+1)。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)