度ど (图论)

用度ようど标记顶点的てき多重たじゅう图

在ざい图论中ちゅう，一いち个顶点在ざい图中なか的てき度ど (degree)为与这个顶点相しょう连接的てき边的てき数すう目もく。在ざい多重たじゅう图中なか，自じ环被ひ计数两次。 顶点 $v$ 的まと度ど记作$\deg(v)$或ある$\deg v$。图G的てき最大さいだい度ど记作Δでるた(G)，最小さいしょう度ど记作δでるた(G)，分ふん别为图中所有しょゆう顶点度ど的てき最大さいだい值和最小さいしょう值。 在ざい右みぎ边的多重たじゅう图中なか，最大さいだい度ど为5，最小さいしょう度ど为0。 在ざい正せい则图中なか，所有しょゆう度ど都と是ぜ相しょう同どう的てき，因いん为我们可以直接ちょくせつ说该图的度ど是ぜ多少たしょう。 完全かんぜん图是正ぜせい则图中ちゅう的てき一种特殊情况，其任意にんい两个点てん均ひとし相しょう连，若わか顶点数すう为p，则该图的度ど为p-1。

给定一いち个图$G=(V,E)$,其度ど求もとめ和わ公式こうしき为：

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

该公式しき表明ひょうめい，在ざい任意にんい无向图中，度ど为奇数すう的てき顶点的てき个数为偶数すう，即そく为握手あくしゅ定理ていり。该定理ていり名称めいしょう来き自じ于一个热门的数学问题，即そく证明在ざい一个团体中与他人握手奇数次的人的数量为偶数个。

对于有向ゆうこう图：

• 节点（顶点）的てき入いれ度ど是ぜ指ゆび进入该节点てん（顶点）的てき边的条じょう数すう；
• 节点（顶点）的てき出で度たび是ぜ指ゆび从该节点（顶点）出だし发的边的条じょう数すう。

度ど序列じょれつ

两个有ゆう相しょう同どう度ど序列じょれつ的てき异构图 (3, 2, 2, 2, 2, 1, 1, 1).

无向图的度ど序列じょれつ是ぜ指ゆび包含ほうがん其顶点てん度ど的てき非ひ递增序列じょれつ；前文ぜんぶん的てき图其序列じょれつ为(5,3,3,2,2,1,0)。度ど序列じょれつ是ぜ一いち个图不变量，所以ゆえん同どう构图具有ぐゆう相しょう同どう的まと度ど序列じょれつ。但ただし是ぜ，度ど序列じょれつ一般不能惟一地识别一个图；在ざい某ぼう些情况下，异构图具有ぐゆう相しょう同どう的まと程度ていど序列じょれつ。

度ど序列じょれつ问题是ぜ寻找图中包含ほうがん顶点度ど的てき一个非递增正整数序列的问题。(后きさき面めん的てき零れい可か以忽略りゃく，因いん为它们是通どおり过向图中添加てんか适当数量すうりょう的てき孤立こりつ顶点来らい实现的てき。)度ど序列じょれつ中ちゅう，能のう使し度ど序列じょれつ问题有ゆう解かい的てき序列じょれつ被ひ称しょう为图序列じょれつ。根ね据すえ度ど序列じょれつ公式こうしき，任にん何なん和わ为奇数すう的てき序列じょれつ，如(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的てき图。

参まいり见

• 度ど分布ぶんぷ
• 二分にぶん图的てき度ど序列じょれつ
• 并行计算

參考さんこう文獻ぶんけん

• 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 .