User:Z423x5c6/握手引理
圖論入面,握手引理(英文:handshaking lemma)指出,喺一個有限無向圖入面,連住「單數咁多條邊」嘅頂點數量係雙數。用日常嘅語言嘅話,喺一個聚會入面啲人互相握手,同過單數咁多個人握手嘅人數一定係雙數。[1]握手引理可以用度和公式嚟證明,而有啲人直程會將度和公式叫做握手引理。[2]度和公式指出,一幅圖所有點嘅度加埋等於邊嘅數量嘅兩倍。兩個定理都係由歐拉喺佢好出名、研究七橋問題嘅論文入面證明,呢篇亦都係世界上第一篇研究圖論嘅論文。[3]
除咗用嚟研究七橋問題同佢嘅推廣一筆畫問題之外,握手引理可以證明某啲組合性嘅結構數量一定係雙數,亦都可以用嚟幫手證明Sperner引理同行山問題。畀一幅好大嘅隱定義圖同埋入面一粒奇度嘅點,要搵另一粒奇度點出嚟嘅運算複雜度叫做PPA類。
定義同定理內容
編輯一個無向圖入面有一柞點,另外有一柞邊,每條邊連住兩點,呢啲邊係無方向嘅,即係話A點連去B點同B點連去A點無分別。圖入面,一粒頂點v嘅度(degree)即係有幾多條邊連去呢一點。如果幅圖容許有迴圈(即係一點連去佢自己度),咁計度嗰陣呢啲邊計兩條。[2]用呢啲術語嘅話,握手引理就係講一幅有限圖入邊,度係奇數嘅點數量係一個雙數。[1]「度係奇數嘅點」有時又叫奇點(odd node[4]/odd vertex[5]),咁嘅話握手引理即係話任何有限圖都有偶數粒奇點。[4][5]
度和公式指出,
- ,
其中 係幅圖嘅點集, 係幅圖嘅邊集,亦即係話所有點嘅度加埋係等於邊數嘅兩倍。[6]度和公式亦都有有向圖嘅版本,指出一幅圖嘅入度和同出度和都等於邊數,呢到入度係數入一粒點嘅邊,出度就數出一粒點嘅邊。[7]度和定理仲有一個集合族嘅版本,集合族等價於超圖,點嘅度和等於啲集合基數嘅和。[8]
握手引理同度和公式都可以應用落去子圖到,包括幅圖嘅連通部分,其中一個推論就係,畀一粒奇點,一定存在一條路徑將佢連去另一粒奇點。[9]
應用
編輯一筆畫
編輯歐拉喺佢篇研究七橋問題嘅論文入面首次證明握手引理。七橋問題係問可唔可以喺柯尼斯堡(依家嘅加里寧格勒)入面行一個圈,而且嗰七條橋都係啱啱好經過一次。呢篇文開創咗圖論同埋拓樸學。用現代嘅圖論語言嚟講,條問題即係問喺右邊嘅圖入面,存唔存在歐拉路徑或者歐拉迴路。歐拉解決咗呢個問題,個答案同圖入面嘅奇點數量有關。握手引理指出呢個奇點數量一定係偶數,若果係 0 嘅話幅圖就有歐拉迴路,係 2 嘅話就有歐拉路徑(不過唔係歐拉迴路,即係起點同終點係唔同嘅),4 或以上就歐拉迴路同歐拉路徑都無。[3]
用 Christofides–Serdyukov 算法嚟逼近旅行推銷員問題(traveling salesperson problem,TSP)嘅時候,握手引理好重要,因為佢令個算法可以將啲點連成一對對,用歐拉迴路嚟逼近 TSP 迴路。[10]
組合枚舉
編輯其他應用
編輯握手引理(或者度和公式)亦都可以用嚟證明其他數學定理,包括:
證明
編輯特別嘅圖
編輯正則圖
編輯度和公式指出,一幅有 粒點嘅 -正則圖會有 條邊[11],而由於邊嘅數量一定係整數,若果 係單數嘅話頂點嘅數量就一定要係雙數[12],而且喺呢個時候邊數一定可以被 整除[13]。
二分圖同雙正則圖
編輯無限圖
編輯子圖
編輯運算複雜度
編輯參考資料
編輯- ↑ 跳到去: 1.0 1.1 Hein, James L. (2015), "Example 3: The Handshaking Problem", Discrete Structures, Logic, and Computability, Jones & Bartlett Publishers, p. 703, ISBN 9781284070408
- ↑ 跳到去: 2.0 2.1 Gunderson, David S. (2014), Handbook of Mathematical Induction: Theory and Applications, CRC Press, p. 240, ISBN 9781420093650
- ↑ 跳到去: 3.0 3.1 Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press
- ↑ 跳到去: 4.0 4.1 Higgins, Peter M. (1998), Mathematics for the Curious, Oxford University Press, p. 201, ISBN 9780192880727
- ↑ 跳到去: 5.0 5.1 Biggs, Norman L. (2002), "15.3: Degree", Discrete Mathematics, Oxford University Press, pp. 181–182, ISBN 9780198507178
- ↑ West, Douglas B. (1996), "1.3.3. Theorem. (Degree-Sum Formula)", Introduction to Graph Theory (第2版), Prentice Hall, p. 26, ISBN 9780132278287
- ↑ Loehr, Nicholas (2011), "3.31. Theorem: Degree-Sum Formula for Digraphs", Bijective Combinatorics, CRC Press, p. 106, ISBN 9781439848869
- ↑ Jukna, Stasys (2011), "Proposition 1.7", Extremal Combinatorics, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 9, doi:10.1007/978-3-642-17364-6, ISBN 978-3-642-17363-9
- ↑ Ray, Santanu Saha (2012), "Theorem 2.2", Graph Theory with Algorithms and its Applications in Applied Science and Technology, Springer, p. 16, ISBN 9788132207504
- ↑ Christofides, Nicos (1976), Worst-case analysis of a new heuristic for the travelling salesman problem (PDF), Report 388, Graduate School of Industrial Administration, CMU, 原先內容歸檔 (PDF)喺July 21, 2019. The handshaking lemma is cited at the top of page 2.
- ↑ Aldous, Joan M.; Wilson, Robin J. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 978-1-85233-259-4
- ↑ Wallis, W. D. (2011), "Section 7.1, Introduction to Graphs, Corollary 1", A Beginner's Guide to Discrete Mathematics (第2版), Springer, p. 219, ISBN 9780817682866
- ↑ Clark, John; Holton, Derek Allan (1995), "Problem 1.4.6", A First Look at Graph Theory, Allied Publishers, p. 16, ISBN 9788170234630
引用錯誤 <ref>
tag with name "bruhnstein" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "cameron-edmonds" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "chen-deng" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "configs" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "filgol" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "gale" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "grigni" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "lausca" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "lovasz" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "mountain" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "neto" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "papadimitriou" defined in <references>
is not used in prior text.
引用錯誤 <ref>
tag with name "sperner" defined in <references>
is not used in prior text.
<ref>
tag with name "thomason" defined in <references>
is not used in prior text.