文章目錄

• 一、完全圖
• 二、 二部圖
• 三、完全二部圖
• 四、 連通性概念
• 五、連通圖
• 六、 圖的分支
• 七、 歐拉回路 ( 閉跡 / 回路 ) [ 遍歷圖中所有的邊 | 每個邊只經(jīng)過一次 | 頂點可經(jīng)過多次 ]
• 八、 歐拉定理
• 九、 哈密頓圈 ( 閉路 / 圈 ) [ 遍歷圖中所有的頂點 | 每個頂點只經(jīng)過一次 ]
• 十、 哈密頓圈 相關(guān)定理
• 十一、 平面圖
• 十二、 面的次數(shù) 與 邊數(shù) 定理 ( 面次數(shù)之和 = 邊數(shù)兩倍 ) ★
• 十三、 歐拉定理 ★
• 十四、 平面圖的 必要條件 定理 ( 平面圖 滿足 e 小于等于 3v -6 條件 ) ★
• 十五、 圖的模型應(yīng)用★
• 十六、 完全圖★
• 十七、 握手定理 題目★

一、完全圖

完全圖 概念 :

• 1.條件 1 : $G$ 為 $n(n\ge 1)$ 階無向簡單圖 ;
• 2.條件 2 : 若 $G$ 中每個頂點 均與 其余的 $n?1$ 個頂點相鄰 ;
• 3.結(jié)論 : 則稱 $G$ 為 $n$ 階 無向完全圖 , 記做 $K_n$ ;

$G$ 的頂點集是 $V(G)$ , 其頂點個數(shù)為 $|V(G)|$ , 則稱 $G$ 為 $n$ 階圖 ;

---

二、 二部圖

二部圖概念 :

• 1.條件 1 : 圖 $G$ 的頂點集劃分為兩個非空子集 $X$ 和 $Y$ ;
• 2.條件 2 : 一條邊 有一個端點 在 $X$ 中 , 另一個端點在 $Y$ 中 ;
• 3.結(jié)論 : 滿足上述條件 , 稱 $G$ 是二部圖 或 偶圖 ;
• 4.標(biāo)記 : 記做 $G=(X\cup Y,E)$ , $(X,Y)$ 是 $G$ 的一個劃分 ( 二分類 ) ;

其中 $(a)$ 是二部圖 , $(b)$ 也是二部圖 , 其不明顯 , 改變 $(b)$ 中頂點 和 邊 位置 , 可以得到 $(c)$ , 此時就能看出 其是 二部圖 ;

注意 : 二部圖的一邊中 不允許有邊相連 ;

$G$ 指的是 Graphic 圖 ;
$E$ 指的是 Edge 邊 ;
$V$ 指的是 Vertext 頂點 ;

三、完全二部圖

完全二部圖概念 :

• 1.條件 1 : 簡單二部圖 $G=(X\cup Y,E)$
• 2.條件 2 : 如果 $X$ 中的 每個頂點 與 $Y$ 中的每個頂點都有邊連接 ;
• 3.結(jié)論 : 滿足上述條件 的 二部圖 $G$ , 稱為完全二部圖 ;
• 4.記法 : $|X|=m$ , $|Y|=n$ , 此完全二部圖 記做 $K_{m,n}$ ;
• 5.特殊存在 : $K_{1,n}$ 稱為星 ;

$G$ 指的是 Graphic 圖 ;
$E$ 指的是 Edge 邊 ;
$V$ 指的是 Vertext 頂點 ;

---

四、 連通性概念

圖中兩個頂點的連通 :

• 條件 $1$ : 如果在圖 $G$ 中 , 存在兩個頂點 $u,v$ ;
• 條件 $2$ : 兩個頂點之間存在 $(u,v)$ 路 ;
• 結(jié)論 : 滿足上述條件 , 則稱 點 $u,v$ 在圖 $G$ 中連通 ;

涉及到的其它概念 :


途徑 : 頂點和邊的交替出現(xiàn)的序列 , 其順序符合圖中的位置即可 ;
跡 : 每個邊不能相同的 途徑 ;
路 : 每個點都不相同的 跡 ;


這三個概念 , 一個比一個嚴(yán)格 ;


閉途徑 : 起點 和 終點 相同的 途徑 ;
閉跡 : 起點 和 終點 相同的 跡 , 也稱 回路 ;
圈 : 起點 和 終點 相同的 路 ;

$G$ 指的是 Graphic 圖 ;
$E$ 指的是 Edge 邊 ;
$V$ 指的是 Vertext 頂點 ;

---

五、連通圖

連通圖 : 圖 $G$ 中 , 任意兩個頂點都連通 , 那么這個圖 $G$ 是連通圖 ;

---

六、 圖的分支

圖的分支 :

• 條件 1 : 圖 $G$ 頂點集 $V(G)$ 劃分為若干非空子集 $\{V_1,V_2,?,V_n\}$ ;
• 條件 2 : 兩個頂點 屬于 同一個 子集 , 當(dāng)且僅當(dāng) 它們 在 $G$ 中連通 ;
• 滿足上述條件 : 稱 每個子圖 $G[V_i]$ 是 圖 $G$ 的一個分支 ; $(i=1,2,3,?,n)$

$G$ 指的是 Graphic 圖 ;
$E$ 指的是 Edge 邊 ;
$V$ 指的是 Vertext 頂點 ;

---

七、 歐拉回路 ( 閉跡 / 回路 ) [ 遍歷圖中所有的邊 | 每個邊只經(jīng)過一次 | 頂點可經(jīng)過多次 ]

歐拉回路 : 圖 $G(V,E)$ , $E$ 中所有邊的回路 ( 閉跡 ) 稱為 歐拉回路 ;

涉及到的其它概念 :
…
途徑 : 頂點和邊的交替出現(xiàn)的序列 , 其順序符合圖中的位置即可 ;
跡 : 每個邊不能相同的 途徑 ;
路 : 每個點都不相同的 跡 ;
…
這三個概念 , 一個比一個嚴(yán)格 ;
…
閉途徑 : 起點 和 終點 相同的 途徑 ;
閉跡 : 起點 和 終點 相同的 跡 , 也稱 回路 ;
圈 : 起點 和 終點 相同的 路 ;
…
$G$ 指的是 Graphic 圖 ;
$E$ 指的是 Edge 邊 ;
$V$ 指的是 Vertext 頂點 ;

---

八、 歐拉定理

歐拉定理 :

無向圖 存在 歐拉回路 的 充要條件 :

① 圖是連通的 ;

② 圖中 沒有 度數(shù)是奇數(shù)的頂點 ;

與頂點 $v$ 關(guān)聯(lián)的邊數(shù)之和 ( 環(huán)算 $2$ 條邊 ) 就是該頂點的度 , 記作 $d(v)$

---

九、 哈密頓圈 ( 閉路 / 圈 ) [ 遍歷圖中所有的頂點 | 每個頂點只經(jīng)過一次 ]

圖 $G=(V,E)$ 中 , 從 某頂點出發(fā) , 將所有頂點遍歷一遍 , 每個頂點只經(jīng)過一次 ;

$G=(V,E)$ , $G$ 中經(jīng)過 $V$ 中所有頂點的 圈 , 稱為 哈密頓圈 ;

$G=(V,E)$ , $G$ 中經(jīng)過 $V$ 中所有頂點的 道路 , 稱為 哈密頓道路 ;

涉及到的其它概念 :
…
途徑 : 頂點和邊的交替出現(xiàn)的序列 , 其順序符合圖中的位置即可 ;
跡 : 每個邊不能相同的 途徑 ;
路 : 每個點都不相同的 跡 ;
…
這三個概念 , 一個比一個嚴(yán)格 ;
…
閉途徑 : 起點 和 終點 相同的 途徑 ;
閉跡 : 起點 和 終點 相同的 跡 , 也稱 回路 ;
圈 : 起點 和 終點 相同的 路 ;
…
$G$ 指的是 Graphic 圖 ;
$E$ 指的是 Edge 邊 ;
$V$ 指的是 Vertext 頂點 ;

---

十、 哈密頓圈 相關(guān)定理

定理 :

設(shè) $G(V,E)$ 是 $n(n\ge 2)$ 個頂點的 簡單圖 , 如果 任意 一對頂點的度數(shù)之和 大于等于與 $n?1$ , 則 $G$ 中一定有 哈密頓道路 ;

推論 :

設(shè) $G(V,E)$ 是 $n(n\ge 3)$ 個頂點的 簡單圖 , 如果 任意 一對頂點的度數(shù)之和 大于等于與 $n$ , 則 $G$ 中一定有 哈密頓道路 ;

注意這里是任意 一對頂點的度數(shù)之和 大于等于 $n(n\ge 3)$ , 所有的能找出來的 頂點都要滿足該條件 ;

---

十一、 平面圖

平面圖 定義 :

• 1.條件 : $G=<V,E>$ 是 一個 無向圖 ;
• 2.行為 : 將 $G$ 的所有的節(jié)點 和 邊 畫在 平面上 , 使 任何 兩條邊 除了端點外 沒有 其他 的交點 ;
• 3.結(jié)論 : 滿足上述要求 , $G$ 是平面圖 ;

平面圖的特殊情況 , 改變邊的形狀可以使相交的邊不相交 , 這個圖是平面圖 ;

有些圖 表面上看 , 有相交的邊 , 但是不能肯定其不是 平面圖 , 改變某些邊的形狀 , 可以使各個邊不相交 , 那這個圖還是平面圖 ;
如下圖 , 左圖有相交的邊 , 但是把邊拉出來到外側(cè) , 各個邊可以不相交 , 因此該圖是平面圖 ;

有些圖其邊相交 , 但是無論怎么改變其 頂點位置 和 邊的形狀 , 總是有相交的邊 , 那么這個圖不是平面圖 ;

---

十二、 面的次數(shù) 與 邊數(shù) 定理 ( 面次數(shù)之和 = 邊數(shù)兩倍 ) ★

設(shè) $G$ 是有限平面圖 , 面的次數(shù)之和 等于 邊數(shù) 的兩倍 ;

有限平面圖中 , 邊在平面中劃分的區(qū)域成為面 , 包圍每個面的邊的個數(shù)成為面的次數(shù) , 又稱為面的度數(shù) ;

• 有限區(qū)域 : 有限面 , 三角形內(nèi)部的面
• 無線區(qū)域 : 無限面 , 三角形外部的面

---

十三、 歐拉定理 ★

$G$ 是平面連通圖 , $v$ 是頂點數(shù) , $e$ 是邊數(shù) , $r$ 是面數(shù) ;

歐拉公式 : $v?e+r=2$

( 該公式 是 頂點 邊 面 之間的關(guān)系 , 沒有面的度數(shù) )

面的度數(shù)之和 是 $2e$ , 可以與上面組成方程組 , 前提是 $G$ 是平面連通圖 ;

$v$ : 頂點數(shù) ;
$e$ : 邊數(shù) ;
$r$ : 面數(shù) ;
$d_{all}$ : 所有面度數(shù)之和 ;
公式 1 : $2e=d_{all}$ , 設(shè) $G$ 是有限平面圖 , 面的次數(shù)之和 等于 邊數(shù) 的兩倍
公式 2 : $v?e+r=2$
公式 3 : $G$ 是平面圖 $?$ $e\le 3v?6$
助記 : 三角形 : 3 個頂點 , 3條邊 , 2個面 ( 內(nèi)部一個面 , 外部一個面 )

---

十四、 平面圖的 必要條件 定理 ( 平面圖 滿足 e 小于等于 3v -6 條件 ) ★

$G$ 是簡單連通平面圖 , 其頂點數(shù) $v\ge 3$ , 其邊數(shù) $e$ ;

那么 $e\le 3v?6$ ;

如果是平面圖 , 那么公式一定成立 ;
公式成立 , 這個圖不一定是平面圖 ;

該定義用來證明該圖不是平面圖 , 公式不成立 , 那么該圖一定不是平面圖 ;

---

十五、 圖的模型應(yīng)用★

題目 :

• 條件 $1$ : 一個班級的學(xué)生選修 $A,B,C,D,E,F$ 六門課程 ;
• 條件 $2$ : 一部分人同時選修 $D,C,A$ , 一部分人同時選修 $B,C,F$ , 一部分人選修 $B,E$ , 還有一部分人選修 $A,B$
• 問題 : 要求安排考試 , 不能有學(xué)生連續(xù)兩天參加考試 ;

解題思路 :

• 1.構(gòu)造圖 : 每門課程當(dāng)做一個頂點 , 共同被選修的課程用邊相連 ;
• 2.構(gòu)造補圖 : 將其它頂點用虛線連起來 , 虛線部分是上圖的補圖 ;
• 3.找哈密頓道路 : 在 補圖中 中找到一個哈密頓道路 即可 , 道路沿線頂點就是每天考試課程 ;

黑色的邊是共同選修的課程連接在一起 ;

紅色的邊是補圖 ;

從紅色邊中找出一個哈密頓圈 , 對應(yīng)的哈密頓道路就是結(jié)果 ;

哈密頓圈中 , 每個頂點都不能重復(fù) ;

哈密頓道路為 : $B\to D\to F\to A\to E\to C$

---

十六、 完全圖★

題目 : $G$ 是 $n$ 個頂點的 簡單連通平面圖 , 且每個面的度數(shù)都是 $3$ , 求此圖的邊數(shù) $e$ , 面數(shù) $r$ ;

$v$ : 頂點數(shù) ;
$e$ : 邊數(shù) ;
$r$ : 面數(shù) ;
$d_{all}$ : 所有面度數(shù)之和 ;
公式 1 : $2e=d_{all}$ , 設(shè) $G$ 是有限平面圖 , 面的次數(shù)之和 等于 邊數(shù) 的兩倍
公式 2 : $v?e+r=2$
公式 3 : $G$ 是平面圖 $?$ $e\le 3v?6$
助記 : 三角形 : 3 個頂點 , 3條邊 , 2個面 ( 內(nèi)部一個面 , 外部一個面 )

涉及到的相關(guān)概念 :

• 1. 圖的幾個屬性 : 頂點數(shù) $v$ , 邊數(shù) $e$ , 面數(shù) $r$ , 面的度數(shù)之和 $D$ ;
• 2. 面的度數(shù)之和 是 邊數(shù)的兩倍 :
  $D=2e$
• 3. 歐拉定理 :
  $v?e+r=2$

解 :

① 列出方程 1 : 頂點數(shù) $v=n$ , 每個面度數(shù)是 $3$ , 那么 度數(shù)之和 是 $3r$ ;

先根據(jù) 面的度數(shù)之和 = 邊數(shù)兩倍寫出方程 :

$3r=2e$
$r=\frac{2e}{3}$

② 列出方程 2 : 根據(jù)歐拉定理 $v?e+r=2$ 寫出下面方程
$n?e+r=2$

③ 解方程 : 使用 $n$ 表示 $e,r$ 即可 ;

$n?e+\frac{2e}{3}=2$
$e=3(n?2)$
$r=\frac{2e}{3}=2(n?2)$

---

十七、 握手定理 題目★

題目 : 證明空間中不可能存在這樣的多面體 , 其面數(shù)是奇數(shù) , 每個面都由奇數(shù)條線段圍成 ;

證明 :

① 用反證法 , 假設(shè)存在這樣的多面體 $H$ , 其面數(shù) 是 奇數(shù) , 每個面 都有 奇數(shù)條線段圍成 ;

將空間中的多面體 與 平面中的平面圖 建立一一對應(yīng)關(guān)系

② 構(gòu)造多面體 及 對應(yīng)的 圖 :
構(gòu)造圖 : 如果有這樣的多面體 , 以 此 多面體的面集合 為頂點 , 構(gòu)造圖 $G$ ;
構(gòu)造圖中連線標(biāo)準(zhǔn) : 當(dāng)且僅當(dāng) $H$ 中 兩個面 有公共邊界時 , 才能在 $G$ 中 兩個面 對應(yīng)的 兩個頂點 之間連一條邊 ;

③ 提取關(guān)鍵信息 : 提取其中構(gòu)造圖 $G$ 的 頂點個數(shù) 和 頂點的度 信息 ;
$H$ 有奇數(shù)個面 , 代表著 $G$ 有奇數(shù)個頂點 ,
$H$ 中每個面 都有 奇數(shù)條線段 , 代表 $G$ 中每個點的度數(shù)都是奇數(shù) ;

④ 使用握手定理證明該假設(shè)不成立 :
握手定理 : 圖的所有頂點度數(shù)之和等于邊的兩倍 ; ★
握手定理推論 : 奇數(shù)個頂點的個數(shù) 必定是 偶數(shù)個 ; ★

圖 $G$ 中 頂點的個數(shù)是奇數(shù)個 , 每個頂點的度是奇數(shù) , 與握手定理 及 推論 沖突 , 假設(shè)不成立 ; 因此這種多面體不存在 ;

---

總結(jié)

以上是生活随笔為你收集整理的【图论】简单 概念 及 公式 入门 ( 完全图 | 二部图 | 连通图 | 欧拉回路 | 哈密顿圈 | 平面图 | 欧拉定理 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。