本文首發(fā)于 2017-11-14 19:07 原地址：http://www.blockchainbrother.com/article/112
區(qū)塊鏈當中一個重要分支就是密碼學。而密碼學當中涉及到相當?shù)臄?shù)學知識。密碼學和數(shù)學的關(guān)系可謂深之又深，甚至可以說信息安全的很大基石就是數(shù)學（密碼學是信息安全中的一部分）。圖論（Graph Theory）是數(shù)學的一個分支，屬于應(yīng)用數(shù)學，其以圖為研究對象。
區(qū)塊鏈當中一個重要分支就是密碼學。而密碼學當中涉及到相當?shù)臄?shù)學知識，比如：數(shù)論、初等數(shù)學、代數(shù)學、組合數(shù)學以及概率論等。若沒有一點數(shù)學基礎(chǔ)的話，密碼學的研究將是進行不通的。密碼學和數(shù)學的關(guān)系可謂深之又深，甚至可以說信息安全的很大基石就是數(shù)學（密碼學是信息安全中的一部分）。學習和掌握一些數(shù)學知識是必要的，在此我主要分享一些有關(guān)于密碼學的數(shù)學知識。
圖論（Graph Theory）是數(shù)學的一個分支，屬于應(yīng)用數(shù)學，其以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定的關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系。圖論的概念和結(jié)果來源非常廣泛，既有來自生產(chǎn)實踐的問題，也有來自理論研究的問題。歷史上參與研究圖論問題的人既有著名的數(shù)學家也有普通的業(yè)余愛好者。
談到圖論不得不提的就是著名的哥尼斯堡七橋問題。在貫穿古普魯士哥尼斯堡城的普瑞格爾河上有七座橋連接兩岸及河中的兩個小島，當?shù)鼐用穸己芟矚g去島上游玩，但有一個問題困擾著當?shù)鼐用窳撕荛L的時間。在1736年，該市的一位市民向大數(shù)學家歐拉（Euler）提出了此問題。該問題是，從家里出發(fā)，七座橋每座橋都恰好通過一次，然后再回到家里，是否可以辦到。事實上，當?shù)鼐用褚郧霸捶磸蛷驮囼灹硕啻?，不論怎么樣行走，都不能成功的實現(xiàn)每座橋恰好只經(jīng)過一次，但卻沒有人嚴格證明過。
歐拉將兩岸分別用B和C兩點進行表示，兩島分別用A和D來表示，A、B、C、D各點的位置并不重要，僅當兩塊陸地之間有橋時，把每座橋用連接對應(yīng)點的一條邊代替，每條邊的曲直長短也不重要，于是歐拉將上圖的實際場景抽象為下圖，并且將此圖形稱為圖（graph）。
為了解決這個具體的問題，歐拉提出了判定一般圖存在這種走法的充要條件，并給出了必要性證明，開創(chuàng)了圖論（一維拓撲）的研究。這個結(jié)果發(fā)表于1736年，其把問題歸結(jié)為一筆畫問題，證明了從家里出發(fā)，七座橋每座橋都恰好通過一次，然后再回到家里，是不可以辦到的。此論文被公認為第一篇圖論文章，歐拉本人也被尊崇為圖論和拓撲學之父。歐拉在解決此問題的同時給出了連通圖可以一筆畫的充要條件是：奇點的數(shù)目不是0個就是2個（連接到一點的數(shù)目如果是奇數(shù)條，就稱為奇點，如果是偶數(shù)條就稱為偶點，要想一筆畫成必須中間點均是偶點，也就是說來去必須有對應(yīng)，奇點只可能在兩端，因此任何圖如果要一筆畫成，奇點要么沒有要么在兩端）
當時的數(shù)學界起初并未對歐拉解決七橋問題的意義有足夠的認識，甚至有些人僅僅當其為一個數(shù)學游戲。圖論誕生后并未及時獲得足夠的發(fā)展，直到200年后的1936年，匈牙利數(shù)學家科尼希出版了《有限圖與無限圖理論》，此為圖論的第一部專著，其總結(jié)了圖論200年的成果，是圖論發(fā)展的第一座里程碑。此后，圖論進入發(fā)展與突破的階段，又經(jīng)過了半個多世紀的發(fā)展，現(xiàn)已成長為數(shù)學科學的一個獨立的重要學科。而且其分支很多，例如圖論、算法圖論、極值圖論、代數(shù)圖論、隨機數(shù)圖論、模糊圖論、超圖論等。特別值得一說的是，由于現(xiàn)代科學尤其是大型計算機的迅猛發(fā)展，使得圖論大有用武之地，無論是數(shù)學、物理、化學、地理、生物等基礎(chǔ)科學，還是信息、交通、戰(zhàn)爭、經(jīng)濟乃至社會科學的眾多問題，都可以應(yīng)用圖論方法予以解決。當然，圖論也是計算機科學最重要的基礎(chǔ)之一。
注：一筆畫
? ? ? ?1）凡是由偶點組成的連通圖，一定可以一筆畫成。畫時可以將任意一偶點作為起點，最后一定可以以此點為終點畫完此圖。
? ? ? ?2）凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須將一個奇點作為起點，而另一個奇點將為終點。
3）其它情況的圖都不能一筆畫出。//奇點數(shù)除以二便可以算出此圖需要幾筆才能畫成。
注：歐拉通過對七橋問題的研究，不僅解決了哥尼斯堡居民提出的問題，而且得到并證明了更為廣泛的有關(guān)一筆畫的三條結(jié)論，人們將之稱為歐拉定理。對于一個連通圖，通常把某點出發(fā) ? ? ? ?一筆畫所經(jīng)過的路線叫歐拉路，同時將一筆畫成又回到出發(fā)點的歐拉路稱為歐拉回路，而具有歐拉回路的圖被稱為歐拉圖。
于中陽 Mercina-zy
