无向图G有23条边,度为4的顶点有5个,度为3的顶点有4个,其余都是度为2的顶点,则G有( )个顶点。
时间: 2024-04-01 22:36:34 浏览: 135
根据握手定理可得,23条边意味着所有顶点的度数之和为 $2 \times 23 = 46$。设度为 2 的顶点有 $x$ 个,则有:
$5\times 4 + 4\times 3 + 2x = 46$
化简可得 $x=6$,因此度为 2 的顶点有 6 个。那么,总顶点数为:
$5+4+6=15$
因此,G 有 15 个顶点。
相关问题
无向图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。
1.无向图G有24条边,4个5度顶点,3个4度顶点,2个3度顶点,其余顶点度数均小于3,问G的阶数n最小为几?
设G有n个顶点,则G中的边数为:$\frac{1}{2}\sum_{i=1}^{n}d_i$,其中$d_i$表示顶点i的度数。
根据题意,可列出方程:
$$\frac{1}{2}\sum_{i=1}^{n}d_i = 24$$
同时,根据握手定理,可得:
$$\sum_{i=1}^{n}d_i = 2\times24=48$$
又因为有4个5度顶点,3个4度顶点,2个3度顶点,其余顶点度数均小于3,所以可以列出不等式:
$$4\times5+3\times4+2\times3+(n-9)\times2 \leq 2\times48$$
化简得:
$$n \geq 22$$
因此,G的阶数n最小为22。