度 (图论)
在图论中,一个顶点在图中的度 (degree)为与这个顶点相连接的边的数目
(重定向自出度)
在图论中,一个顶点在图中的度 (degree)为与这个顶点相连接的边的数目。在多重图中,自环被计数两次。[1] 顶点 的度记作或。图G的最大度记作Δ(G),最小度记作δ(G),分别为图中所有顶点度的最大值和最小值。 在右边的多重图中,最大度为5,最小度为0。 在正则图中,所有度都是相同的,因为我们可以直接说该图的度是多少。 完全图是正则图中的一种特殊情况,其任意两个点均相连,若顶点数为p,则该图的度为p-1。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/UndirectedDegrees_%28Loop%29.svg/220px-UndirectedDegrees_%28Loop%29.svg.png)
给定一个图,其度求和公式为:
该公式表明,在任意无向图中,度为奇数的顶点的个数为偶数,即为握手定理。该定理名称来自于一个热门的数学问题,即证明在一个团体中与他人握手奇数次的人的数量为偶数个。
对于有向图:
- 节点(顶点)的入度是指进入该节点(顶点)的边的条数;
- 节点(顶点)的出度是指从该节点(顶点)出发的边的条数。
度序列
编辑无向图的度序列是指包含其顶点度的非递增序列;前文的图其序列为(5,3,3,2,2,1,0)。[2]度序列是一个图不变量,所以同构图具有相同的度序列。但是,度序列一般不能惟一地识别一个图;在某些情况下,异构图具有相同的程度序列。
度序列问题是寻找图中包含顶点度的一个非递增正整数序列的问题。(后面的零可以忽略,因为它们是通过向图中添加适当数量的孤立顶点来实现的。)度序列中,能使度序列问题有解的序列被称为图序列。根据度序列公式,任何和为奇数的序列,如(3,3,1),均不能用一个图的度序列来实现。反之亦然:如果一个序列和为偶数,那么它就是一个多重图的度序列。这种图可以很直接构造出来:将度为奇数的顶点进行匹配,并对剩下的顶点构造自环连接。一个给定的度序列是否可以用一个简单图来实现是一个很具挑战性的。这个问题也被称为图枚举问题,可以通过Erdős-Gallai定理或Havel-Hakimi算法来解决。找到或估测具有给定度序列图的数目的问题来源于图枚举领域。
特殊值
编辑全局属性
编辑参见
编辑注释
编辑参考文献
编辑- 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., Gráfok előírt fokszámú pontokkal (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.