设n阶图G中有m 条边,每个结点的度数不是k的是k+1,若G中有小个k度顶点:Nk+1个k+1度顶点,则NK=
时间: 2024-05-28 15:13:23 浏览: 18
首先,根据握手定理,图G中所有顶点的度数和为2m。因为每个非k度顶点的度数都是k+1,所以有:
N(k+1)(k+1) + Nk(k) = 2m
又因为G中有Nk个k度顶点和N(k+1)个(k+1)度顶点,所以有:
Nk + N(k+1) = n
将上述两个式子代入握手定理得:
N(k+1)(k+1) + Nk(k) = 2m
Nk + N(k+1) = n
=> N(k+1)(k+1) + (n-Nk)(k+1-k) = 2m
=> N(k+1)(k+1) + (n-Nk) = 2m
=> N(k+1)(k+1) + n - Nk = 2m
=> N(k+1)(k+1) - Nk = 2m - n
由于每个顶点的度数都是非负整数,因此有:
Nk >= 0
N(k+1) >= 0
将上述不等式代入上面的式子得:
N(k+1)(k+1) - Nk = 2m - n
=> N(k+1)(k+1) >= 2m - n
=> Nk <= (n - 2m + n/(k+1)) / k
因为Nk是整数,所以有:
Nk <= floor((n - 2m + n/(k+1)) / k)
又因为NK = n - N(k+1),所以有:
NK = n - N(k+1) = n - (n-Nk) = Nk
综上所述:
NK = Nk <= floor((n - 2m + n/(k+1)) / k)
相关问题
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)。
假设有一颗三叉树有n个结点,它的最小高度为5,当三叉树有n+1个结点,它的最小高度为6,则有n个结点的二叉树最小高度为
3。
对于一颗三叉树,每个节点最多有三个子节点。当三叉树有n个节点时,最小高度为5,即从根节点到任意叶子节点的最短路径长度为5。当三叉树有n+1个节点时,最小高度为6,即从根节点到任意叶子节点的最短路径长度为6。
而对于二叉树,每个节点最多有两个子节点。由于每个节点的度数减少,相同数量的节点可以形成更深的树。所以,当二叉树有
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)