度ど (圖ず論ろん)

用度ようど標記ひょうき頂點ちょうてん的てき多重たじゅう圖ず

在ざい圖ず論ろん中ちゅう，一いち個こ頂點ちょうてん在ざい圖ず中なか的てき度ど (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 .