圖的基本概念

頂點(diǎn)v：非空頂點(diǎn)集

邊e：邊集，弧集

無向圖(v1，v2)，其中e3和e2稱為平行邊或多重邊

有向圖<v1，v2>，其中v4叫做孤立點(diǎn)

底圖：有向圖將有向邊改為無向邊得到的無向圖

結(jié)點(diǎn)與邊之間的關(guān)系

1. 鄰接點(diǎn)：同一條邊的兩個端點(diǎn)
2. 孤立點(diǎn)：沒有邊與之關(guān)聯(lián)的結(jié)點(diǎn)
3. 鄰接邊：關(guān)聯(lián)同一個結(jié)點(diǎn)的兩條邊
4. 孤立邊：不與任何邊相鄰接的邊
5. 自回路(環(huán))：關(guān)聯(lián)同一個結(jié)點(diǎn)的一條邊(v,v)或者<v,v>
6. 平行邊(多重邊)：關(guān)聯(lián)同一對結(jié)點(diǎn)的多條邊，兩結(jié)點(diǎn)間相互平行的邊的條數(shù)稱為該平行邊的重數(shù)

圖的分類

1. 零圖：有n個頂點(diǎn)，0條邊
2. 平凡圖：有1個頂點(diǎn)，0條邊
3. 多重圖：含有平行邊的圖
4. 線圖：非多重圖
5. 簡單圖：不含平行邊和自回環(huán)的圖
6. 完全圖Kn：任意兩個結(jié)點(diǎn)之間都鄰接的簡單圖（n個結(jié)點(diǎn)）
7. 二部圖Kn,m：一部分n個結(jié)點(diǎn)m條邊，另一部分m個結(jié)點(diǎn)n條邊的簡單圖

結(jié)點(diǎn)的度

關(guān)聯(lián)：點(diǎn)與邊

鄰接：點(diǎn)與點(diǎn)、邊與邊

最大度：各個結(jié)點(diǎn)中的最大度

最小度：各個結(jié)點(diǎn)中的最小度

有向圖的度：出度+入度（環(huán)有兩個度，孤立點(diǎn)沒有度）

握手定理：任意圖 中 所有頂點(diǎn)的度數(shù)之和 = 邊數(shù)×2

奇結(jié)點(diǎn)：度數(shù)為奇數(shù)的結(jié)點(diǎn)

偶結(jié)點(diǎn)：度數(shù)為偶數(shù)的結(jié)點(diǎn)

推論：因?yàn)槎葦?shù)肯定是偶數(shù)，所有每個圖必須有偶數(shù)個奇結(jié)點(diǎn)

k度正則圖：每個結(jié)點(diǎn)的度數(shù)都等于k的無向圖

無向完全圖Kn：每個頂點(diǎn)的度數(shù)都是n-1，一共有n(n-1)/2條邊

圖的同構(gòu)

判斷兩個圖是否同構(gòu)：兩個圖的點(diǎn)集一一對應(yīng)，邊與邊也是一一對應(yīng)，鄰接關(guān)系也是一樣的，如果是有向圖，那方向也要保持一致。

同構(gòu)的性質(zhì)：

1. 圖之間的同構(gòu)關(guān)系具有自反性、對稱性、傳遞性
2. 相同的結(jié)點(diǎn)數(shù)
3. 相同的邊數(shù)
4. 度數(shù)相同的結(jié)點(diǎn)數(shù)目相同
5. 有相同重數(shù)的邊數(shù)相同

圖的同構(gòu)判定算法：

1. 關(guān)聯(lián)度序列法
2. 黃金分割關(guān)聯(lián)度序列法

子圖和補(bǔ)圖

子圖：頂點(diǎn)集和邊集都包含于圖；

真子圖：頂點(diǎn)集和邊集都包含于圖，并且不能與圖相同；

生成子圖：頂點(diǎn)集和圖必須一致，邊集都包含于圖；

頂點(diǎn)集導(dǎo)出子圖：頂點(diǎn)集都包含于圖，邊就是這些頂點(diǎn)可能連接的邊；

邊集導(dǎo)出子圖：邊集都包含于圖，由邊所引出的頂點(diǎn)；

G`是G的補(bǔ)圖：

1. 相同的頂點(diǎn)集
2. 邊集不相交
3. 互為補(bǔ)圖
4. 邊總數(shù)=n(n-1)/2 = G`的邊集+G的邊集

路徑與回路

路徑：從起點(diǎn)到終點(diǎn)（V0e1V1e1...emVm）

通路：開路、閉路

回路（閉路，圈）：起點(diǎn)=終點(diǎn)

簡單(回)路：無向圖中邊互不相同的路

基本(回)路：無向圖中頂點(diǎn)互不相同的路（任何結(jié)點(diǎn)到自身都有長度為0的基本路），每條基本路必定是簡單路。

無向圖的連通性

連通：兩個頂點(diǎn)之間存在路徑

連通圖：圖中任意兩個頂點(diǎn)都是連通的

結(jié)點(diǎn)自身：不是鄰接除非有環(huán)，但是連通的

連通分支：圖是一個連通圖就是它自己w(G) = 1，圖是一個分離圖，頂點(diǎn)集可以按照等價關(guān)系劃分。

連通分支的個數(shù)：w(G) = n

刪除頂點(diǎn)和邊

刪除頂點(diǎn)集（G-S）：圖G中刪除頂點(diǎn)集S，將G中刪除點(diǎn)，以及點(diǎn)所連接的邊；

刪除邊集（G-T）：圖G中刪除邊集T，將G中刪除邊；

點(diǎn)割集(不唯一)：圖G是連通圖，刪除頂點(diǎn)集V，就不是連通圖了(分離圖)；

割點(diǎn)(不唯一)：圖G是連通圖，只刪除頂點(diǎn)V，就不是連通圖了(分離圖)；

點(diǎn)連通度k(G)：G不是完全圖，圖的全部點(diǎn)割集中包含點(diǎn)最少的點(diǎn)割集；分離圖k(G)=0，存在割點(diǎn)的連通圖k(G)=1；

邊割集：圖G是連通圖，刪除邊集E，就不是連通圖了；

割邊：圖G是連通圖，只刪除邊e，就不是連通圖了(分離圖)；

邊連通度入(G)：G不是平凡圖，圖的全部邊割集中包含邊最少的邊割集；分離圖入(G)=0，存在割邊的連通圖入(G)=1；

對于任何一個無向圖G，k(G)≤k(G)≤最小度

有向圖的連通性

單向可達(dá)：兩個點(diǎn)之間存在一條有向路（自反性、傳遞性）

單向連通：圖中任意兩個點(diǎn)至少存在一邊單向可達(dá)

雙向可達(dá)：兩個頂點(diǎn)雙向可達(dá)，是一個等價關(guān)系

無向圖的連通性關(guān)系：連通圖、分離圖

有向圖的連通性關(guān)系：強(qiáng)連通圖(回路) => 單向連通(通路) => 弱連通圖 => 分離圖

強(qiáng)分圖：G`是G的子圖，G`是強(qiáng)連通圖，G`增加G中其他任意的點(diǎn)或邊就不再是強(qiáng)連通；

單向分圖：

弱分圖：

無向歐拉通路：無向圖中只存在0個或者2個奇度結(jié)點(diǎn)

有向歐拉通路：是每條邊經(jīng)過且僅經(jīng)過一次的通路

判斷是有向歐拉通路的充分必要條件：

1. 有向圖中有兩個頂點(diǎn)的出度與入度不相等，其中一個出度比入度多1，另一個的入度比出度多1；
2. 所有頂點(diǎn)都是出度=入度

判斷是有向歐拉回路的充分必要條件：

1. 所有頂點(diǎn)都是出度=入度

哈密頓通路：每個頂點(diǎn)經(jīng)過且僅經(jīng)過一次的通路；

判斷是哈密頓通路的充分條件：n階無向簡單圖，存在兩個頂點(diǎn)不連接，兩個頂點(diǎn)的度數(shù)之和≥n-1；

判斷不是哈密頓回路的必要條件(滿足一定不是，不滿足不一定是)：

1. 有割點(diǎn)或橋的圖一定不是哈密頓圖（推論）
2. 連通分支數(shù) ≤ 刪掉的頂點(diǎn)數(shù)

判斷是哈密頓回路的充分條件：（n階無向簡單圖G中）

1. 頂點(diǎn)v與頂點(diǎn)u不鄰接，d(v)+d(u) ≥ n（奧爾定理）
2. 最小度 ≥ n/2（狄拉克定理）
3. 圖的閉包是一個無向完全圖，那原圖就是哈密頓圖

無向完全圖Kn一定是哈密頓圖

圖的閉包C：連接任意兩個度數(shù)之和≥n且不鄰接的頂點(diǎn)（加邊）