度 (图论)

度序列

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