图论1-4 顶点的度


图论1-4 顶点的度

$G$的顶点$v$的度$d_G(v)$定义为,$G$中与$v$关联的边的数目,每个环算作两条边。$\delta(v)$和$\Delta(v)$分别表示最小度和最大度。

以 $v$ 为起点的边的数目为 出度(out-degree),记为 $d^+(v)$;以 $v$ 为终点的边的数目为 入度(in-degree),记为 $d^-(v)$。

定理 1.1 (握手定理/图论基本定理)
$$
\sum\limits_{v\in V}d(v)=2\varepsilon
$$
:这个证明是显而易见的,每条边都会为两个端点各贡献一个度,因此总度数为边数的两倍。

推论 1.1
在任何图中,奇点的个数为偶数。
证:设$V_1$和$V_2$分别为$G$的奇点集和偶点集,由定理1.1可知:
$$
\sum\limits_{v\in V_1}d(v)+\sum\limits_{v\in V_2}d(v)=\sum\limits_{v\in V}d(v)=2\varepsilon
$$
为偶数,由于$\sum\limits_{v\in V_2}d(v)$为偶数,所以$\sum\limits_{v\in V_1}d(v)$也为偶数,由于奇点集中每个点的度都为奇数,因此$\mid V_1\mid$为偶数。
$$
\sum\limits_{v\in V}d^+(v)=\sum\limits_{v\in V}d^-(v)=|E|
$$

  • 若 $d(v)=0$ ,则称 $v$ 为 孤立点(isolated vertex)
  • 若 $d(v)=1$ ,则称 $v$ 为 叶节点 (leaf vertex)/**悬挂点 (pendant vertex)**。
  • 若 $d(v)=\mid V\mid-1$,则称 $v$ 为 **支配点 (universal vertex)**。

文章作者: xitie2000
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 xitie2000 !
评论
  目录