查看“度 (图论)”的源代码

[[File:UndirectedDegrees_(Loop).svg|缩略图|用度标记顶点的多重图]]
在[[图论]]中，一个[[顶点 (图论)|顶点]]在[[图 (数学)|图]]中的'''度''' ('''degree''')为与这个顶点相连接的[[邊 (圖論)|边]]的数目。在[[多重图]]中，[[自环]]被计数两次。<ref>Diestel p.5</ref> 顶点 <math>v</math> 的度记作<math>\deg(v)</math>或<math>\deg v</math>。图''G''的'''最大度'''记作Δ(''G'')，'''最小度'''记作δ(''G'')，分别为图中所有顶点度的最大值和最小值。 在右边的[[多重图]]中，最大度为5，最小度为0。 在[[正则图]]中，所有度都是相同的，因为我们可以直接说该图的度是多少。 [[完全圖|完全图]]是正则图中的一种特殊情况，其任意两个点均相连，若顶点数为p，则该图的度为p-1。

给定一个图<math>G=(V, E)</math>,其'''度求和公式'''为：

: <math>\sum_{v \in V} \deg(v) = 2|E|\, .</math>

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

== 度序列 ==
[[File:Conjugate-dessins.svg|缩略图|200x200像素|两个有相同度序列的异构图 (3, 2, 2, 2, 2, 1, 1, 1).]]
无向图的'''度序列'''是指包含其顶点度的非递增序列；右边的图其序列为(5,3,3,2,2,1,0)。<ref>Diestel p.278</ref>度序列是一个[[图不变量]]，所以[[图同构|同构图]]具有相同的度序列。但是，度序列一般不能惟一地识别一个图；在某些情况下，异构图具有相同的程度序列。

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

== 特殊值 ==
[[File:Depth-first-tree.png|缩略图|一个包含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''的图。

== 参见 ==

* [[有向图]]
* [[度分布]]
* [[二分图]]的[[二分图#度序列|度序列]]

== 注释 ==
<references group="" responsive="1"></references>

== 参考文献 ==

* {{Citation|last=Diestel|first=Reinhard|title=Graph Theory|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|publisher=Springer-Verlag|place=Berlin, New York|edition=3rd|isbn=978-3-540-26183-4|year=2005}}.
* {{Citation|first=P.|last=Erdős|author-link=Paul Erdős|first2=T.|last2=Gallai|author2-link=Tibor Gallai|title=Gráfok előírt fokszámú pontokkal|language=hu|journal=Matematikai Lapok|volume=11|year=1960|pages=264&ndash;274|url=http://www.renyi.hu/~p_erdos/1961-05.pdf}}.
* {{Citation|last=Havel|first=Václav|author-link=V. J. Havel|year=1955|title=A remark on the existence of finite graphs|language=cs|journal=Časopis pro pěstování matematiky|volume=80|pages=477–480|url=http://eudml.org/doc/19050}}
* {{Citation|last=Hakimi|first=S. L.|author-link=S. L. Hakimi|journal=Journal of the [[Society for Industrial and Applied Mathematics]]|mr=0148049|pages=496–506|title=On realizability of a set of integers as degrees of the vertices of a linear graph. I|volume=10|year=1962}}.
* {{Citation|last=Sierksma|first=Gerard|last2=Hoogeveen|first2=Han|doi=10.1002/jgt.3190150209|number=2|journal=[[Journal of Graph Theory]]|mr=1106533|pages=223–231|title=Seven criteria for integer sequences being graphic|volume=15|year=1991}}.
[[Category:图论]]
[[Category:有未审阅翻译的页面]]