跳转到内容

握手引理

维基百科，自由的百科全书

在圖論中，握手引理（英語：handshaking lemma）為在每個有限無向圖中，頂點鄰接奇數個邊的數量有偶數個。也可以說，度數為奇數的頂點有偶數個。例如，在某派對上大家互相握手，則「跟奇數個人握手的人」有偶數個。[1]此引理是由度求和公式（英語：degree sum formula）推導而得，內容為無向圖中所有頂點的度數（鄰接到該頂點的邊數）總和為該圖邊數的兩倍。上面的兩個結果都由 李昂哈德‧歐拉 （1736）在他著名的柯尼斯堡七橋問題的論文上證明，也就是圖論研究的起點。[2]

此圖中，有偶數個頂點（編號為2、4、5、6的四個頂點）的度數為奇數。所有六個頂點的度數總和為 2+3+2+3+3+1=14，是邊數的兩倍。

除了後來催生一筆畫問題的柯尼斯堡七橋問題之外，度求和公式的其他應用還包括了某些組合結構的證明。例如，在斯苯納引理（英语：Sperner's lemma）和爬山問題的證明中，該公式的幾何特性經常出現。複雜度類 PPA 概括了在給定大型隱式定義圖（英语：Implicit graph）中給定一個奇數頂點的情況下，找出第二個奇數頂點的難度。

定義與陳述

[编辑]

在無向圖中，包含一系列的頂點與連接無序頂點對的邊。在任何的圖中，頂點 的度數 定義為以 為端點的邊的數量。對於允許包含連接頂點本身，也就是包含環的圖，為了符合握手引理，每個環應該對其端點的度數貢獻兩單位（即有環的頂點本身度數加二）。[3]然後握手引理指出，在每個有限無向圖中，度數 為奇數的頂點數必須為偶數。[4]圖中度數為奇數的頂點有時稱為奇頂點（或奇節點）；[5] 以此術語而言，握手引理可改述為「每個圖都有偶數個奇頂點」的陳述。[5][6]

度求和公式指出：其中 是圖中節點（或頂點）的集合且 是圖中邊的集合。也就是說，頂點度數的總和等於邊數的兩倍。[7] 在有向圖中，度求和公式的另一種形式指出，所有頂點的入度（英語：in-degree）之和與出度（英語：out-degree）之和皆等於邊的數量。這裡的入度是指「起點為某節點的邊的數量」，出度是指「終點為某節點的邊的數量」。[8] 度求和公式的一個版本也適用於有限的集族，等價於多重圖：元素度數的總和（其中度數等於包含它的集合的數量）總是等於集合的勢總和。[9]

這兩個結果也適用於給定圖的任何子圖，特別是其連通元件。推論是對於任何奇數頂點，必存在一條路徑將其連接到另一個奇頂點。[10]

應用

[编辑]

歐拉路徑與迴路

[编辑]
柯尼斯堡七橋示意圖
以每塊陸地為頂點，每座橋為邊的圖

萊昂哈德·歐拉在研究柯尼斯堡七橋問題時首次證明了握手引理。這個問題是關於如何在柯尼斯堡（現為加里寧格勒）城中進行一次徒步旅行，跨過七座橋，且每座橋都只能走一次。以圖論的術語來說，相當於在一個代表城市和橋樑的連通圖中尋找一條歐拉路徑（英語：Euler path）或歐拉迴路（英語：Euler tour）：遍歷圖中每條邊一次的路徑，其區別為歐拉路徑的起點和終點不同，而歐拉遊覽行徑則會回到起點。

歐拉根據圖中奇頂點的數量闡述了此問題的基本結果，握手引理則將奇數頂點的數量限制為偶數。如果奇頂點的數量為零，則存在歐拉迴路；如果為兩個，則存在歐拉路徑。否則，問題就無法解決。在柯尼斯堡七橋問題中，代表該問題的圖有四個奇數頂點，因此既不存在歐拉路徑，也不存在歐拉迴路。[2]這表示在柯尼斯堡，不可能在不重複過橋的情況下走完所有七座橋。

在近似旅行推銷員問題（縮寫為 TSP）的克里斯托菲德斯算法中，度求和公式的幾何意義扮演著至關重要的角色，使該演算法得以將頂點成對連接，從而構建一個圖，並在此圖上形成一個歐拉迴路作為近似 TSP 路徑。[11]

組合計數

[编辑]

某些組合結構的數量可以透過將它們與適當的「交換圖（exchange graph）」中的奇頂點相關聯來證明其為偶數。[12]

舉例，如 C. A. B. Smith（英语：Cedric Smith (statistician)） 所證，在任何立方圖 中，通過任何固定邊 的漢米頓迴圈數量必為偶數；這些迴圈恰好經過每個頂點一次。湯瑪森 (1978) 則是利用基於握手引理的證明，將此結果推廣到所有頂點都具有奇數度數的圖。湯瑪森定義一個交換圖 ，其頂點與 中始於 並持續通過邊 的漢米頓路徑一一對應。若一條路徑 可透過在 的末端添加一條新的邊並從 中間移除另一條邊來獲得，那麼 和 這兩條路徑在 中被定義為透過一條邊連接。此操作是可逆的，形成一個對稱關係，因此 是一個無向圖。若路徑 結束於頂點 ，則 中對應於 的頂點的度數等於 可透過不連接回 的邊進行擴展的方法數；也就是若 不構成通過 之漢米頓迴圈的一部分，則 中此頂點的度數為 （偶數）；若 通過 之漢米頓迴圈的一部分，則為 （奇數）。因為 具有偶數個奇頂點，因此 必須有偶數個通過 的漢米頓迴圈。[13]

其他應用

[编辑]

握手引理（或度求和公式）在數學中也用於證明其他幾項結果。其中包括：

經過斯苯納染色的三角形分割圖，其中陰影部分標示出具所有三種顏色的頂點之小三角形。
  • 斯苯納引理（英语：Sperner's lemma）指出，若一個大三角形被細分成邊對邊相接的小三角形，且頂點會被標上三種顏色，使得大三角形的每條邊上只使用其中的兩種顏色，那至少有一個小三角形的頂點會包含所有三種顏色；此引理應用於不動點定理、求根演算法，與公平分配賽局。其中一個證明方法是構造一個交換圖，其頂點是這些（大大小小）的三角形且其邊連接的是共享某兩種特定顏色的兩個頂點的三角形對。這個交換圖中，大三角形的度數必然是奇數，具所有三種顏色的小三角形的度數也為奇數，而其他小三角形的度數則為偶數。根據握手定理，具所有三種顏色的小三角形的數量必為奇數，因此至少存在一個這樣的小三角形。[14]
爬山問題
  • 爬山問題指出，對於單位區間上的良態，且區間兩端點函數數值相等的函數，可以協調從兩個區間端點同時出發的點的運動（如動畫所示），使它們在區間內的某點相遇，並且在整個運動過程中始終保持在函數值相等的位置。該問題的證明方法之一，需要一個近似原始函數的，具相同極值點的分段線性函數（英语：Piecewise linear function）。接著透過單位正方形中單一點的座標來參數化兩個移動點的位置。最後，證明兩個點的可移動位置形成一個嵌入在此單位正方形中的有限圖，而該圖中只有起始位置及其反向位置為奇頂點。根據握手定理，這兩個位置屬於圖中的同一個連通元件，因此從一個位置到另一個位置的路徑必然會經過所需的相遇點。[15]
  • 重構猜想是關於從移除單一頂點所形成的子圖多重集來唯一確定圖結構的問題。給定這些資訊，度求和公式可以用來恢復原始圖中的邊數以及每個頂點的度數，而從中可以判斷給定圖是否為正則圖。如果是，則可以通過為所有度數過低的子圖頂點添加新鄰居，從任何一個刪除頂點的子圖中唯一地確定該正則圖。因此，所有正則圖都可以被重構。[16]
  • 六貫棋（Hex）是一種由兩名玩家進行的遊戲。玩家輪流在由六邊形方格組成的平行四邊形棋盤上放置自己顏色的棋子，直到其中一名玩家的棋子從棋盤的一邊連接到另一邊，形成一條連續的路徑為止。這個遊戲永遠不會出現平局：當棋盤完全被棋子填滿時，其中一名玩家必然已經形成了一條獲勝路徑。證明這一點的方法之一是從一個已經下滿棋子的棋盤構造一個圖。在這個圖中，六邊形的角點是頂點，而分隔兩種玩家顏色的六邊形邊緣則是邊。這個圖在棋盤的四個角點有四個奇頂點，其他地方的頂點則都是偶數。因此，它必然包含一條連接兩個角點的路徑，這條路徑的其中一側必然屬於其中一名玩家的獲勝路徑。[17]

證明

[编辑]

歐拉證明度求和公式時使用了雙重計數的技巧：他以兩種不同的方式，計算了關聯對 的數量，其中 是一條邊，且頂點 是它的其中一個端點。頂點 屬於 個關聯對，其中 （ 的度數）是與它鄰接的邊的數量。因此，關聯對的數量就是所有度數的總和。然而，圖中的每條邊都恰好屬於兩個關聯對，每個端點一個；因此，關聯對的數量是 。由於這兩個公式計算的是同一組物件，它們的值必然相等。同樣的證明也可以解釋為：透過兩種方式對圖的關聯矩陣（英语：Incidence matrix）中的條目進行求和，按行求和得到度數的總和，按列求和得到邊數的兩倍。[6]

對於圖而言，握手引理是度求和公式的直接推論。[9]在整數的和中，總和的奇偶性不受總和中偶數項的影響；當奇數項的數量為偶數時，總和為偶數；當奇數項的數量為奇數時，總和為奇數。由於度求和公式的一邊是偶數 ，所以另一邊的和必須有偶數個奇數項；也就是說，必須有偶數個奇數度數頂點。[6]

此外，也可使用數學歸納法來證明度求和公式，[3]或者透過從給定圖中一次移除一條邊，並對其端點的度數進行窮舉法，以確定此移除對奇數度數頂點數量奇偶性的影響，從而直接證明奇數度數頂點的數量為偶數。[18]

特殊類別的圖

[编辑]
克萊布殊圖（英语：Clebsch graph）是五度正則圖，有偶數個頂點（16個），邊數（40條）是五的倍數。
菱形十二面體是雙正則圖（英语：biregular graph），有六個度數為四的頂點和八個度數為三的頂點；6×4=8×3=24，亦為它的邊數。

正則圖

[编辑]

度求和公式意味著每個具有 個頂點的 -正則圖有 條邊。[19]因為邊的數量必須是整數，所以當 是奇數時，頂點的數量必須是偶數。[20] 此外，對於 的奇數值，邊的數量必須可被 整除。[21]

二部圖與雙正則圖

[编辑]

一個二部圖的頂點被分成兩個子集，每條邊的兩個端點分別位於不同的子集中。同樣地，透過雙重計數的論證可以推斷，在每個子集中，度數之和都等於圖中邊的數量。特別是，這兩個子集的度數之和相等。[22]對於雙正則圖（英语：Biregular graph），如果頂點被劃分為 和 兩個子集，並且子集 中的每個頂點都具有度數 ，那麼必然滿足 ；兩者都等於邊的數量。[23]

無限圖

[编辑]
只有一個奇頂點的無限圖

握手引理之通常形式不適用於無限圖，即使這些圖只有有限數量的奇數度數頂點。例如，一條只有一個端點的無限路徑圖（英语：Path graph）圖就只有一個奇數度數頂點，而不是偶數個。然而，可以利用末端（英语：End (graph theory)）（end）的概念來表述握手引理的一個版本。末端是指半無限路徑（「射線（"rays"）」）的等價類，當存在第三條射線同時無限次使用兩條射線中的頂點時，這兩條射線被視為等價。一個末端的度數是它所包含的最大邊不相交射線的數量，如果度數是有限且為奇數，則該末端是奇數的。更普遍地說，對於所有頂點都具有有限度數的圖，無論末端是否具有無限度數，都可以將其定義為奇數或偶數。然後，在這樣的圖中，奇數頂點和奇數末端的數量加總後是偶數或無限個。[24]

子圖

[编辑]

根據 Gallai（英语：Tibor Gallai） 定理，任何圖的頂點集 都可以被劃分為 ​，使得在兩個由此產生的導出子圖中， 的所有度數都是偶數，而 的所有度數都是奇數。根據握手引理， 必須是偶數。此外，也可以找到具有許多頂點的偶數度數和奇數度數的導出子圖。可以找到一個至少包含一半頂點的偶數度數導出子圖，並且（在沒有孤立頂點的圖中）可以找到一個奇數度數導出子圖，其滿足 。[25][26]

計算複雜度

[编辑]
主条目：PPA(複雜度)（英语：PPA(complexity)）

關於利用交換圖（exchange graph）方法證明組合結構存在性的問題，人們對於如何有效地找到這些結構很感興趣。例如，假設輸入是一個三次圖中的漢米頓迴圈；根據史密斯定理，存在第二個迴圈。那這個第二個迴圈能多快被找到呢？

Papadimitriou (1994) 研究了這類問題的計算複雜度，更廣義地說，是在一個大型隱式定義圖（英语：Implicit graph）中，當給定一個奇數度頂點時，尋找第二個奇數度頂點的問題。他定義了複雜度類 PPA 來概括這類問題；[27]一個密切相關、定義在有向圖上的類別 PPAD（英语：PPAD (complexity)），在演算法賽局理論（英语：Algorithmic game theory）中引起了廣泛關注，因為計算納許均衡在計算上等同於此類別中最困難的問題。[28]

被證明是 PPA 複雜度類別完備（complete）的計算問題包括與斯苯納引理（英语：Sperner's lemma）[29]相關的計算任務，以及根據Hobby–Rice 定理（英语：Hobby–Rice theorem）進行資源公平劃分的問題。[30]

參考文獻

[编辑]
  1. ^ Hein, James L. "Example 3: The Handshaking Problem". Discrete Structures. Jones & Bartlett Publishers. : 703. ISBN 9781284070408. 
  2. ^ 2.0 2.1 Euler, L., Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae, 1736, 8: 128–140 [2025-07-16], （原始内容存档于2024-12-09） . Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J., Graph Theory 1736–1936, Oxford University Press, 1976 
  3. ^ 3.0 3.1 Gunderson, David S., Handbook of Mathematical Induction: Theory and Applications, CRC Press: 240, 2014, ISBN 9781420093650 
  4. ^ Hein, James L., Example 3: The Handshaking Problem, Discrete Structures, Logic, and Computability, Jones & Bartlett Publishers: 703, 2015, ISBN 9781284070408 
  5. ^ 5.0 5.1 Higgins, Peter M., Mathematics for the Curious, Oxford University Press: 201, 1998, ISBN 9780192880727 
  6. ^ 6.0 6.1 6.2 Biggs, Norman L., 15.3: Degree, Discrete Mathematics, Oxford University Press: 181–182, 2002, ISBN 9780198507178 
  7. ^ West, Douglas B., 1.3.3. Theorem. (Degree-Sum Formula), Introduction to Graph Theory 2nd, Prentice Hall: 26, 1996, ISBN 9780132278287 
  8. ^ Loehr, Nicholas, 3.31. Theorem: Degree-Sum Formula for Digraphs, Bijective Combinatorics, CRC Press: 106, 2011, ISBN 9781439848869 
  9. ^ 9.0 9.1 Jukna, Stasys, Proposition 1.7, Extremal Combinatorics, Texts in Theoretical Computer Science. An EATCS Series, Springer: 9, 2011, ISBN 978-3-642-17363-9, doi:10.1007/978-3-642-17364-6 
  10. ^ Ray, Santanu Saha, Theorem 2.2, Graph Theory with Algorithms and its Applications in Applied Science and Technology, Springer: 16, 2012, ISBN 9788132207504 
  11. ^ Christofides, Nicos, Worst-case analysis of a new heuristic for the travelling salesman problem (PDF), Report 388, Graduate School of Industrial Administration, CMU, 1976, （原始内容存档 (PDF)于July 21, 2019） . The handshaking lemma is cited at the top of page 2.
  12. ^ Cameron, Kathie; Edmonds, Jack, Some graphic uses of an even number of odd nodes, Annales de l'Institut Fourier（英语：Annales de l'Institut Fourier）, 1999, 49 (3): 815–827 [2025-07-16], MR 1703426, doi:10.5802/aif.1694 可免费查阅, （原始内容存档于2016-03-03） 
  13. ^ Thomason, A. G., Hamiltonian cycles and uniquely edge colourable graphs, Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics 3: 259–268, 1978, ISBN 978-0-7204-0843-0, MR 0499124, doi:10.1016/S0167-5060(08)70511-9 
  14. ^ Aigner, Martin; Ziegler, Günter M., Section 28.6: Sperner's Lemma, Proofs from THE BOOK（英语：Proofs from THE BOOK） 6th, Berlin: Springer: 203–205, 2018, ISBN 978-3-662-57264-1, MR 3823190, doi:10.1007/978-3-662-57265-8 
  15. ^ Goodman, Jacob E.; Pach, János; Yap, Chee-K., Mountain climbing, ladder moving, and the ring-width of a polygon (PDF), 美國數學月刊, 1989, 96 (6): 494–510, JSTOR 2323971, MR 0999412, doi:10.2307/2323971 
  16. ^ Lauri, Josef; Scapellato, Raffaele, Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Lecture Note Series 432 2nd, Cambridge University Press: 105–106, 2016, ISBN 978-1-316-61044-2, MR 3496604, doi:10.1017/CBO9781316669846 
  17. ^ Gale, David, The game of Hex and the Brouwer fixed-point theorem, 美國數學月刊, 1979, 86 (10): 818–827, JSTOR 2320146, MR 0551501, doi:10.1080/00029890.1979.11994922 
  18. ^ Neto, Antonio Caminha Muniz, An Excursion through Elementary Mathematics, Volume III: Discrete Mathematics and Polynomial Algebra, Problem Books in Mathematics, Springer: 132, 562, 2018, ISBN 9783319779775 
  19. ^ Aldous, Joan M.; Wilson, Robin J., Theorem 2.2, Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag: 44, 2000, ISBN 978-1-85233-259-4 
  20. ^ Wallis, W. D., Section 7.1, Introduction to Graphs, Corollary 1, A Beginner's Guide to Discrete Mathematics 2nd, Springer: 219, 2011, ISBN 9780817682866 
  21. ^ Clark, John; Holton, Derek Allan, Problem 1.4.6, A First Look at Graph Theory, Allied Publishers: 16, 1995, ISBN 9788170234630 
  22. ^ Lovász, László, Combinatorial Problems and Exercises 2nd, Elsevier: 281, 2014, ISBN 9780080933092 
  23. ^ Pisanski, Tomaž; Servatius, Brigitte, 2.3.4: Semiregular Bipartite Graphs, Configurations from a Graphical Viewpoint, Birkhäuser Advanced Texts: Basler Lehrbücher, New York: Birkhäuser/Springer: 35, 2013, ISBN 978-0-8176-8363-4, MR 2978043, doi:10.1007/978-0-8176-8364-1 
  24. ^ Bruhn, Henning; Stein, Maya, On end degrees and infinite cycles in locally finite graphs, Combinatorica（英语：Combinatorica）, 2007, 27 (3): 269–291, MR 2345811, S2CID 8367713, doi:10.1007/s00493-007-2149-0 ; see Proposition 15, p. 284
  25. ^ Ferber, Asaf; Krivelevich, Michael, Every graph contains a linearly sized induced subgraph with all degrees odd, Advances in Mathematics, 2022, 406, MR 4448268, arXiv:2009.05495 可免费查阅, doi:10.1016/j.aim.2022.108534 
  26. ^ Honner, Patrick, What a Math Party Game Tells Us About Graph Theory, Quanta, 2022-03-24 [2022-03-27], （原始内容存档于2025-05-25） 
  27. ^ Papadimitriou, Christos H., On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences（英语：Journal of Computer and System Sciences）, 1994, 48 (3): 498–532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7 可免费查阅 
  28. ^ {{citation|first1=Xi|last1=Chen|first2=Xiaotie|last2=Deng|contribution=Settling the complexity of two-player Nash equilibrium|title=Proc. 47th Symp. Foundations of Computer Science（英语：Symposium on Foundations of Computer Science）|year=2006|pages=261–271|doi=10.1109/FOCS.2006.69|isbn=0-7695-2720-5 |s2cid=14102058
  29. ^ Grigni, Michelangelo, A Sperner lemma complete for PPA, Information Processing Letters（英语：Information Processing Letters）, 2001, 77 (5–6): 255–259, MR 1818525, doi:10.1016/S0020-0190(00)00152-6 
  30. ^ Filos-Ratsikas, Aris; Goldberg, Paul W., Consensus halving is PPA-complete, Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (编), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018（英语：Symposium on Theory of Computing）: 51–64, 2018, ISBN 978-1-4503-5559-9, S2CID 8111195, arXiv:1711.04503 可免费查阅, doi:10.1145/3188745.3188880 
检索自“https://zh.wikipedia.org/w/index.php?title=握手引理&oldid=88345993”