图的顶点度与度序列 顶点的度 在图论中，一个顶点的度（degree）是指与该顶点直接相连的边的数量。对于无向图，顶点的度是简单的邻接边计数。例如，若顶点 \( v \) 有 3 条边与之相连，则其度 \( \deg(v) = 3 \)。特殊地，若顶点没有边相连（孤立顶点），其度为 0。 度的性质与握手引理 无向图中所有顶点的度之和等于边数的两倍，即 \( \sum \deg(v) = 2|E| \)。这一结论称为握手引理，因为每条边为两个顶点各贡献 1 度。推论：无向图中度为奇数的顶点必有偶数个。 有向图中的度 在有向图中，顶点的度分为出度（out-degree）和入度（in-degree）。出度是以该顶点为起点的边的数量，入度是以该顶点为终点的边的数量。所有顶点的出度之和等于入度之和，且均等于边数 \( |E| \)。 度序列 度序列是一个图的所有顶点的度按非递增顺序排列成的序列。例如，图有顶点度集合 {3, 2, 2, 1}，则度序列为 (3, 2, 2, 1)。度序列可用于判断一个图是否存在（图的实现问题）。 度序列的可图化判定 埃尔德什-加莱定理（Erdős–Gallai theorem）给出了度序列可图化的充要条件：对每个 \( k \)（\( 1 \leq k \leq n \)），满足 \( \sum_ {i=1}^k d_ i \leq k(k-1) + \sum_ {i=k+1}^n \min(d_ i, k) \)。此外，Havel–Hakimi 算法通过递归删减度值提供了一种构造性判定方法。 度序列的应用 度序列用于分析网络结构，如社交网络中度的分布可揭示网络中心性；在随机图中，度序列的性质可用于研究图的连通性、鲁棒性等。