握手定理：在無向圖中，度數為奇數的頂點必然有偶數個。

?? ? ? ? ? ? ?證明：設n1為偶數度頂點的個數，n2為奇數度頂點的個數，無向圖中每條邊有兩個度，設邊數為m，則2m=n1+n2,2m一定為偶數，n1也是偶數（讀數為偶 ? ? ? ? ? ? ? ? ? ? ? 數的各個頂點的度數和必為偶數），故n2必定為偶數個，即得證。

?

歐拉圖判定定理：（格尼斯堡七橋問題）

歐拉路徑：遍歷圖的每條邊一次僅且一次的路徑。

歐拉回路：遍歷圖的每條邊一次且僅一次的回路。

歐拉圖：具有歐拉回路的圖。

?注：如果圖中存在孤立點并不會影響歐拉路徑的討論，因為歐拉路徑的要求是遍歷圖中的每條邊而非遍歷圖中的頂點。

?

判斷一個無向連通圖是否為歐拉圖的 充分必要條件：一個無向連通圖是歐拉圖，當且僅當該圖所有頂點的度數均為偶數。

判斷一個有向連通圖是否為歐拉圖的 充分必要條件：一個有向連通圖是歐拉圖，當且僅當該圖的每個頂點的出度等于入度。

?

哈密頓回路有關定理：（遍歷正12面體的每個頂點一次最后回到頂點）

哈密頓路徑：在無向圖中，遍歷圖中每個頂點一次且僅一次的路徑。

哈密頓回路：遍歷圖中每個頂點一次且僅一次的回路稱為哈密頓回路。

哈密頓圖：具有哈密頓回路的圖。

?

判斷哈密頓回路存在的必要條件：

?? ? ?設圖G<V,E>是哈密頓圖，則，對V的每個非空真子集S均有w（G-S）≤|S|，其中|S|是S的點數，w（G-S）表示G刪去頂點集S后得到的圖的連通分圖的個數。

?? ? ?注：必要條件只是可以用來判斷某些圖是否是哈密頓圖，不能判斷所有的有該性質的圖，如彼德森圖。

判斷哈密頓回路存在的充分條件：

?? ? ? 若圖G<V,E>是具有n≥3個頂點的簡單無向圖，且在圖中每一對頂點的度數和都不小于n，那么圖中必然存在一條哈密頓回路。

?? ? ? 注：滿足充分條件的圖一定是哈密頓圖，但是不滿足該條件的也可能是哈密頓圖

???

轉載于:https://www.cnblogs.com/Blanche/archive/2010/10/26/1861965.html

總結

以上是生活随笔為你收集整理的图中几个常用的定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。