度(圖論) - 維基百科，自由的百科全書

在圖論中，一個頂點在圖中的度(degree)為與這個頂點相連接的邊的數目。

... 該公式表明，在任意無向圖中，度為奇數的頂點的個數為偶數，即為握手定理。

度(圖論) 維基百科，自由的百科全書 跳至導覽 跳至搜尋 用度標記頂點的多重圖 在圖論中，一個頂點在圖中的度(degree)為與這個頂點相連接的邊的數目。

在多重圖中，自環被計數兩次。

[1]頂點 v {\displaystylev} 的度記作 deg ⁡ ( v ) {\displaystyle\deg(v)} 或 deg ⁡ v {\displaystyle\degv} 。

圖G的最大度記作Δ(G)，最小度記作δ(G)，分別為圖中所有頂點度的最大值和最小值。

在右邊的多重圖中，最大度為5，最小度為0。

在正則圖中，所有度都是相同的，因為我們可以直接說該圖的度是多少。

完全圖是正則圖中的一種特殊情況，其任意兩個點均相連，若頂點數為p，則該圖的度為p-1。

給定一個圖 G = ( V , E ) {\displaystyleG=(V,E)} ,其度求和公式為： ∑ v ∈ V deg ⁡ ( v ) = 2 | E | . {\displaystyle\sum_{v\inV}\deg(v)=2|E|\,.} 該公式表明，在任意無向圖中，度為奇數的頂點的個數為偶數，即為握手定理。

該定理名稱來自於一個熱門的數學問題，即證明在一個團體中與他人握手奇數次的人的數量為偶數個。

對於有向圖： 節點（頂點）的入度是指進入該節點（頂點）的邊的條數； 節點（頂點）的出度是指從該節點（頂點）出發的邊的條數。

目次 1度序列 2特殊值 3全局屬性 4參見 5注釋 6參考文獻 度序列[編輯] 兩個有相同度序列的異構圖(3,2,2,2,2,1,1,1). 無向圖的度序列是指包含其頂點度的非遞增序列；前文的圖其序列為(5,3,3,2,2,1,0)。

[2]度序列是一個圖不變量，所以同構圖具有相同的度序列。

但是，度序列一般不能惟一地識別一個圖；在某些情況下，異構圖具有相同的程度序列。

度序列問題是尋找圖中包含頂點度的一個非遞增正整數序列的問題。

(後面的零可以忽略，因為它們是通過向圖中添加適當數量的孤立頂點來實現的。

)度序列中，能使度序列問題有解的序列被稱為圖序列。

根據度序列公式，任何和為奇數的序列，如(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的圖。

參見[編輯] 度分布 二分圖的度序列 並行計算 注釋[編輯] ^Diestelp.5 ^Diestelp.278 參考文獻[編輯] Diestel,Reinhard,GraphTheory3rd,Berlin,NewYork:Springer-Verlag,2005[2019-04-23],ISBN 978-3-540-26183-4,（原始內容存檔於2011-07-28） . Erdős,P.;Gallai,T.,Gráfokelőírtfokszámúpontokkal(PDF),MatematikaiLapok,1960,11:264–274（匈牙利語） . Havel,Václav,Aremarkontheexistenceoffinitegraphs,Časopispropěstovánímatematiky,1955,80:477–480[2019-04-23],（原始內容存檔於2017-07-29）（捷克語）  Hakimi,S.L.,Onrealizabilityofasetofintegersasdegreesoftheverticesofalineargraph.I,JournaloftheSocietyforIndustrialandAppliedMathematics,1962,10:496–506,MR 0148049 . Sierksma,Gerard;Hoogeveen,Han,Sevencriteriaforintegersequencesbeinggraphic,JournalofGraphTheory,1991,15(2):223–231,MR 1106533,doi:10.1002/jgt.3190150209 . 閱論編圖論圖 種類 有向圖 無向圖 有向無環圖 二分圖 多分圖 連通圖 完全圖 圖標號 超圖 多重圖 平面圖 偽圖 正則圖 樹 賦權圖 輪圖 線圖 結構 節點 邊 迴路 自環 弦 環 橋 子圖 團 補圖 屬性 邊連通 圍長 重數 階 尺寸 頂點連通 圖不變量 二元運算 圖乘積 圖運算 取自「https://zh.wikipedia.org/w/index.php?title=度_(图论)&oldid=69202778」 分類：圖論並發計算隱藏分類：CS1匈牙利語來源(hu)CS1捷克語來源(cs)有未審閱翻譯的頁面 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 已展開 已摺疊 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 已展開 已摺疊 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他語言 العربيةCatalàČeštinaDanskDeutschEnglishEsperantoEspañolFrançaisעבריתHrvatskiMagyarÍslenska日本語NederlandsPolskiPortuguêsRomânăРусскийSlovenščinaСрпски/srpskiSvenskaதமிழ்ไทยУкраїнськаTiếngViệt 編輯連結