度 (图论)

在图论中，一个顶点在图中的度 (degree)为与这个顶点相连接的边的数目。在多重图中，自环被计数两次。^[1] 顶点 ${\displaystyle v}$ 的度记作${\displaystyle \deg(v)}$或${\displaystyle \deg v}$。图G的最大度记作Δ(G)，最小度记作δ(G)，分别为图中所有顶点度的最大值和最小值。 在右边的多重图中，最大度为5，最小度为0。 在正则图中，所有度都是相同的，因为我们可以直接说该图的度是多少。 完全图是正则图中的一种特殊情况，其任意两个点均相连，若顶点数为p，则该图的度为p-1。

用度标记顶点的多重图

给定一个图${\displaystyle G=(V,E)}$,其度求和公式为：

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,.}$

该公式表明，在任意无向图中，度为奇数的顶点的个数为偶数，即为握手定理。该定理名称来自于一个热门的数学问题，即证明在一个团体中与他人握手奇数次的人的数量为偶数个。

对于有向图：

• 节点（顶点）的入度是指进入该节点（顶点）的边的条数；
• 节点（顶点）的出度是指从该节点（顶点）出发的边的条数。

度序列

 

两个有相同度序列的异构图 (3, 2, 2, 2, 2, 1, 1, 1).

无向图的度序列是指包含其顶点度的非递增序列；前文的图其序列为(5,3,3,2,2,1,0)。^[2]度序列是一个图不变量，所以同构图具有相同的度序列。但是，度序列一般不能惟一地识别一个图；在某些情况下，异构图具有相同的程度序列。

度序列问题是寻找图中包含顶点度的一个非递增正整数序列的问题。(后面的零可以忽略，因为它们是通过向图中添加适当数量的孤立顶点来实现的。)度序列中，能使度序列问题有解的序列被称为图序列。根据度序列公式，任何和为奇数的序列，如(3,3,1)，均不能用一个图的度序列来实现。反之亦然：如果一个序列和为偶数，那么它就是一个多重图的度序列。这种图可以很直接构造出来：将度为奇数的顶点进行匹配，并对剩下的顶点构造自环连接。一个给定的度序列是否可以用一个简单图来实现是一个很具挑战性的。这个问题也被称为图枚举问题,可以通过Erdős-Gallai定理或Havel-Hakimi算法来解决。找到或估测具有给定度序列图的数目的问题来源于图枚举领域。

特殊值

 

一个包含4,5,6,7,10,11与12这些子节点的无向图

• 度为0的顶点称为孤立顶点。
• 度为1的顶点称为叶节点或端点，与该顶点相关联的边称为悬挂边。在右图中，{3,5}是一条悬挂边。这个术语在数据结构与图论中对树的研究中很常见。
• 有n个顶点的图中度为n-1的顶点称为全连接顶点。

全局属性

• 如果图中每个顶点的度均为k，那么这个图被称作k-正则图，可称该图的度为k。类似地，在二分图中，在同一侧顶点的度相同的图被称作双正则图。
• 无向连通图当且仅当它有0或2个奇数度的顶点时其有一个欧拉路径。如果它有0个奇数度的顶点，欧拉路径即为欧拉环路。
• 有向图当且仅当每个顶点的出度都不超过1时为一个伪森林。函数图是伪森林的一种特殊情况，其中每个顶点的出度都恰好为1。
• 根据布鲁克斯定理，除了团和有奇数个顶点的循环图以外的所有图的最大着色数Δ，根据Vizing定理，所有图的最大着色数为Δ+1。
• k-退化图是一个所有子图顶点的度最大为k的图。

参见

• 度分布
• 二分图的度序列
• 并行计算

注释

1. Diestel p.5
2. Diestel p.278

參考文獻

• Diestel, Reinhard, Graph Theory 3rd, Berlin, New York: Springer-Verlag, 2005 [2019-04-23], ISBN 978-3-540-26183-4, （原始内容于2011-07-28） .
• Erdős, P.; Gallai, T., (PDF), Matematikai Lapok, 1960, 11: 264–274 [2019-04-23], （原始内容 (PDF)存档于2022-01-20） （匈牙利语） .
• Havel, Václav, A remark on the existence of finite graphs, Časopis pro pěstování matematiky, 1955, 80: 477–480 [2019-04-23], （原始内容于2017-07-29） （捷克语） 
• Hakimi, S. L., On realizability of a set of integers as degrees of the vertices of a linear graph. I, Journal of the Society for Industrial and Applied Mathematics, 1962, 10: 496–506, MR 0148049 .
• Sierksma, Gerard; Hoogeveen, Han, Seven criteria for integer sequences being graphic, Journal of Graph Theory, 1991, 15 (2): 223–231, MR 1106533, doi:10.1002/jgt.3190150209 .