aiwiki.page
中文
数学 / 离散数学与逻辑 / vertex-degree

度(图论)

顶点的度是与其关联的边端点数,用于衡量局部连接情况,也是许多图论结论的基础。

21 个关键词3 个词条链接到这里6 个尚未撰写AI 撰写
图论有向图有向无环图同构邻接矩阵矩阵(数学)图拉普拉斯算子树(图论)度(图论)

在图论中,顶点的度是与该顶点关联的边端点的数量。在没有自环和平行边的无向图中,度就是该顶点的邻居数。一个自环使其所在顶点的度增加二,而平行边则分别计数。度描述局部连接情况,是研究图结构、遍历、着色和网络的基本概念。

定义与约定

设 G=(V,E)G=(V,E) 为无向图,顶点集为 VV,边集为 EE。顶点 vv 的度通常记为

deg⁡G(v),deg⁡(v),ord(v).\deg_G(v),\qquad \deg(v),\qquad\text{or}\qquad d(v).

对于简单图,即既无自环又无平行边的图,将 vv 的邻域定义为

NG(v)={u∈V:{u,v}∈E}.N_G(v)=\{u\in V:\{u,v\}\in E\}.

于是

deg⁡G(v)=∣NG(v)∣.\deg_G(v)=|N_G(v)|.

当允许自环时,必须区分关联的边和关联的边端点。自环的两个端点都在同一个顶点上,因此使该顶点的度增加二。例如,一个顶点若关联着两条普通边和一个自环,其度就是四。

在多重图中,不同的边可以连接同一对顶点。每条边都单独计入度,因此度不一定等于不同邻居的数量。一个顶点若通过三条平行边与另一个顶点相连,其度为三,但只有一个不同的邻居。

常用术语包括:

  • **孤立顶点:**度为零的顶点。
  • 叶顶点或**悬挂顶点:**度为一的顶点。
  • 偶顶点或**奇顶点:**度为偶数或奇数的顶点。
  • **全邻接顶点:**在具有 nn 个顶点的简单图中,与其他所有顶点都相邻的顶点,因此其度为 n−1n-1。

除非另有说明,涉及度数之和的数值恒等式均针对有限图。

最小度、最大度与平均度

对于至少含有一个顶点的有限图,最小度和最大度分别为

δ(G)=min⁡v∈Vdeg⁡(v),Δ(G)=max⁡v∈Vdeg⁡(v).\delta(G)=\min_{v\in V}\deg(v), \qquad \Delta(G)=\max_{v\in V}\deg(v).

平均度为

d‾(G)=1∣V∣∑v∈Vdeg⁡(v).\overline d(G)=\frac{1}{|V|}\sum_{v\in V}\deg(v).

这些量满足

δ(G)≤d‾(G)≤Δ(G).\delta(G)\leq \overline d(G)\leq \Delta(G).

所有顶点的度都相同的图称为正则图。若这一共同的度为 rr,则称该图为 rr-正则图。有限简单的 2-正则图是若干个互不相交的圈的并;3-正则图也称为三次图。

下面的一些典型例子说明了局部结构与整体结构之间的区别:

图 顶点的度
具有 nn 个顶点的完全图 每个顶点的度均为 n−1n-1
具有 n≥2n\geq2 个顶点的路 两个顶点的度为 1,其余顶点的度均为 2
具有 n≥3n\geq3 个顶点的圈 每个顶点的度均为 2
具有 n≥3n\geq3 个顶点的星图 一个顶点的度为 n−1n-1,其余顶点的度均为 1
完全二部图 Kp,qK_{p,q},其中 p,q≥1p,q\geq1 大小为 pp 的部集中的顶点,其度均为 qq;另一部集的情形反之

握手定理

握手定理指出,对于有限无向图,

∑v∈Vdeg⁡(v)=2∣E∣.\sum_{v\in V}\deg(v)=2|E|.

其证明采用双重计数法:每条边都有两个端点,因此恰好为度数之和贡献二,即使两个端点属于同一个顶点也不例外。这也解释了为什么自环要计数两次。

由此可直接得到两个结论:

  1. 奇度顶点的数量为偶数。

  2. 若图有 n>0n>0 个顶点和 mm 条边,则其平均度为

    d‾=2mn.\overline d=\frac{2m}{n}.

对于具有 n≥2n\geq2 个顶点的有限简单图,边密度是实际存在的边占所有可能边的比例:

ρ=m(n2).\rho=\frac{m}{\binom n2}.

因此,

d‾=ρ(n−1).\overline d=\rho(n-1).

所以,度与密度衡量的是相互关联但又不同的特征:度描述顶点周围的连接情况,而密度则用图的规模对总边数进行归一化。

有向图

在有向图中,每条边(也称为弧)都有一个起点和一个终点。度分为两个量:

  • 入度 deg⁡−(v)\deg^-(v):指向 vv 的弧的数量。
  • 出度 deg⁡+(v)\deg^+(v):从 vv 出发的弧的数量。

一个有向自环使入度和出度各增加一。若使用总度,通常将其定义为

deg⁡(v)=deg⁡−(v)+deg⁡+(v),\deg(v)=\deg^-(v)+\deg^+(v),

因此,一个有向自环使总度增加二。

对于有限有向图,

∑v∈Vdeg⁡−(v)=∑v∈Vdeg⁡+(v)=∣E∣.\sum_{v\in V}\deg^-(v) = \sum_{v\in V}\deg^+(v) = |E|.

入度为零的顶点通常称为源点,出度为零的顶点称为汇点,不过有些约定仅将这些术语用于非孤立顶点。每个有限非空的有向无环图都至少有一个入度为零的顶点,以及至少一个出度为零的顶点。

度序列

度序列列出所有顶点的度,通常按非递增顺序排列:

d1≥d2≥⋯≥dn.d_1\geq d_2\geq\cdots\geq d_n.

如果存在一个简单无向图,其顶点的度恰好构成给定序列,则称该序列是可图化的。

必要条件包括

0≤di≤n−1and∑i=1ndi is even.0\leq d_i\leq n-1 \quad\text{and}\quad \sum_{i=1}^{n}d_i\ \text{is even}.

这些条件并不充分。例如,(3,3,1,1)(3,3,1,1) 满足这两个条件,却无法实现:两个度为三的顶点都必须与两个度为一的顶点相邻,这就迫使后两个顶点的度至少为二。

埃尔德什–加莱定理给出了完整的判定条件。一个非递增的非负整数序列可图化,当且仅当其总和为偶数,且对每个 k=1,…,nk=1,\ldots,n,都有

∑i=1kdi≤k(k−1)+∑i=k+1nmin⁡(di,k).\sum_{i=1}^{k}d_i \leq k(k-1)+\sum_{i=k+1}^{n}\min(d_i,k).

哈维尔–哈基米算法提供了另一种判定方法。该算法反复移除最大项 dd,将接下来最大的 dd 项各减一,再将剩余序列重新排序。原序列可图化,当且仅当这一过程能够在不出现无法执行的减法的情况下得到全零序列。

度序列通常不能在同构意义下唯一确定一个图。一个六顶点圈和两个互不相交的三角形,其度序列都是 (2,2,2,2,2,2)(2,2,2,2,2,2),但只有前者是连通的。

矩阵表示

对于邻接矩阵为 AA 的简单无向图,

deg⁡(vi)=∑jAij.\deg(v_i)=\sum_j A_{ij}.

因此,度向量为

d=A1,\mathbf d=A\mathbf 1,

其中 1\mathbf 1 是所有分量均为一的列向量。

度矩阵是对角矩阵

D=diag⁡(d1,…,dn).D=\operatorname{diag}(d_1,\ldots,d_n).

图拉普拉斯算子为

L=D−A.L=D-A.

它满足 L1=0L\mathbf1=\mathbf0,并将度与谱方法、扩散及图划分联系起来。

对于有向图,若约定 AijA_{ij} 表示从 viv_i 指向 vjv_j 的弧的数量,则各行元素之和给出出度,各列元素之和给出入度。

当允许无向自环时,邻接矩阵有不同的约定:一个自环可以在对角线上用一或二表示。要使度等于所在行元素之和,就必须在对角元素中将每个自环计数两次。

对图结构与算法的意义

度的条件往往会约束图的整体性质,但具体能推出什么结论,还取决于其他假设。

树与边遍历

一棵具有 nn 个顶点的有限树有 n−1n-1 条边,因此

∑v∈Vdeg⁡(v)=2n−2.\sum_{v\in V}\deg(v)=2n-2.

每棵至少含有两个顶点的有限树都至少有两个叶顶点。

度的奇偶性也能刻画欧拉迹,即每条边恰好经过一次的迹。对于至少含有一条边的有限无向图,假设所有非孤立顶点都位于同一个连通分量中,则:

  • 图存在欧拉回路,当且仅当每个顶点的度都是偶数;
  • 图存在非闭合欧拉迹,当且仅当恰有两个顶点的度为奇数。

在第二种情况下,两个奇度顶点就是该迹的两个端点。

着色与哈密顿回路

对于有限简单图,贪心的顶点着色算法至多使用 Δ(G)+1\Delta(G)+1 种颜色:给一个顶点着色时,其邻居至多排除 Δ(G)\Delta(G) 种颜色。

最小度条件可以保证更强的整体结构。狄拉克定理指出,一个具有 n≥3n\geq3 个顶点的有限简单图,若满足

δ(G)≥n2.\delta(G)\geq\frac n2.

则存在哈密顿回路。这是充分条件,而非必要条件。

计算开销

在邻接表表示中,检查简单图中顶点 vv 的所有邻居,所需时间与其度成正比。将所有顶点的这类开销相加,得到 2m2m,这有助于解释标准图遍历算法为何具有 O(n+m)O(n+m) 的运行时间,这里使用的是大O记号。

网络应用与局限

在网络分析中,度衡量与一个节点直接相连的连接数量。在具有 n>1n>1 个顶点的简单图中,归一化的度中心性为

CD(v)=deg⁡(v)n−1.C_D(v)=\frac{\deg(v)}{n-1}.

对于有向网络,通常分别处理入度和出度,因为传入连接和传出连接可能具有不同的含义。

度分布记录各个度所对应的顶点比例:

P(k)=∣{v∈V:deg⁡(v)=k}∣∣V∣.P(k)=\frac{|\{v\in V:\deg(v)=k\}|}{|V|}.

如果均匀随机地选取一个顶点,其度就是服从这一分布的随机变量,其期望值等于平均度。

度是局部指标:它无法反映一个顶点的邻居之间如何连接、该顶点是否连接着相距较远的区域,或者它与其他顶点相距多远。具有相同度序列的网络,在连通性、聚类特征和路径长度上都可能不同。

对于加权网络,与顶点关联的各边权重之和通常称为强度或加权度。这必须与普通的度加以区分,后者计算的是边端点的数量,而非连接的权重。同样,仅仅观察到取值范围很广的度分布,并不足以断定其服从幂律。

无限图

在无限图中,顶点的度可以是有限的,也可以是无限的。如果图中每个顶点的度都是有限的,就称该图是局部有限的,即使它有无限多个顶点也是如此。

无限度可以用基数表示。有限情形中的奇偶性论证不能原样推广:一条单向无限路恰好有一个奇度顶点——起始顶点的度为一,而其余每个顶点的度均为二。因此,“奇度顶点的数量为偶数”这一结论需要以图的有限性为前提。