圖論 - 同構
圖可以以不同的形式存在，具有相同的頂點數、邊數以及相同的邊連通性。這樣的圖稱為同構圖。請注意，我們在本章中主要對圖進行標記，以便於參考和區分它們。
同構圖
如果兩個圖 G1 和 G2 滿足以下條件，則稱它們為同構：
它們的組成部分（頂點和邊）數量相同。
它們的邊連通性保持不變。
注意 - 簡而言之，兩個同構圖中，一個只是另一個的修改版本。未標記的圖也可以被認為是同構圖。
There exists a function ‘f’ from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.
注意
如果 G1 ≡ G2，則：
|V(G1)| = |V(G2)|
|E(G1)| = |E(G2)|
G1 和 G2 的度數序列相同。
如果頂點 {V1, V2, .. Vk} 在 G1 中形成長度為 K 的迴圈，則頂點 {f(V1), f(V2),… f(Vk)} 應該在 G2 中形成長度為 K 的迴圈。
以上所有條件對於圖 G1 和 G2 同構都是必要的，但不足以證明這兩個圖是同構的。
（G1 ≡ G2）當且僅當（G1− ≡ G2−），其中 G1 和 G2 是簡單圖。
（G1 ≡ G2）如果 G1 和 G2 的鄰接矩陣相同。
（G1 ≡ G2）當且僅當 G1 和 G2 的對應子圖（透過刪除 G1 中的一些頂點及其在圖 G2 中的映像獲得）是同構的。
例子
以下哪些圖是同構的？
在圖 G3 中，頂點“w”的度數僅為 3，而其他所有圖頂點的度數均為 2。因此，G3 與 G1 或 G2 不同構。
取 G1 和 G2 的補圖，得到：
這裡，（G1− ≡ G2−），因此（G1 ≡ G2）。
平面圖
如果一個圖“G”可以繪製在平面上或球面上，使得任意兩條邊在非頂點處不交叉，則稱該圖“G”為平面圖。
例子
區域
每個平面圖將平面劃分為稱為區域的連通區域。
例子
有界區域的度數r = deg(r) = 包圍區域 r 的邊的數量。
deg(1) = 3 deg(2) = 4 deg(3) = 4 deg(4) = 3 deg(5) = 8
無界區域的度數r = deg(r) = 包圍區域 r 的邊的數量。
deg(R1) = 4 deg(R2) = 6
在平面圖中，以下性質成立：
在一個具有“n”個頂點的平面圖中，所有頂點的度數之和為：
根據區域度數之和/定理，在一個具有“n”個區域的平面圖中，區域度數之和為：
基於上述定理，您可以得出以下結論：
在平面圖中，
如果每個區域的度數為 K，則區域度數之和為：
如果每個區域的度數至少為 K（≥ K），則
如果每個區域的度數至多為 K（≤ K），則
注意 - 假設所有區域的度數相同。
根據平面圖上的尤拉公式，
如果一個圖“G”是連通平面圖，則
如果一個平面圖具有“K”個連通分量，則
其中，|V| 是頂點數，|E| 是邊數，|R| 是區域數。
邊頂點不等式
如果“G”是一個連通平面圖，且每個區域的度數至少為“K”，則
|E| ≤ k / (k-2) {|v| - 2}
已知，|V| + |R| = |E| + 2
K.|R| ≤ 2|E|
K(|E| - |V| + 2) ≤ 2|E|
（K - 2)|E| ≤ K(|V| - 2)
|E| ≤ k / (k-2) {|v| - 2}
如果“G”是一個簡單連通平面圖，則
|E| ≤ 3|V| − 6 |R| ≤ 2|V| − 4
存在至少一個頂點 V •∈ G，使得 deg(V) ≤ 5。
如果“G”是一個簡單連通平面圖（至少有 2 條邊）且沒有三角形，則
|E| ≤ {2|V| – 4}
庫拉托夫斯基定理
一個圖“G”是非平面圖當且僅當“G”有一個子圖與 K5 或 K3,3 同胚。
同態
如果兩個圖 G1 和 G2 可以從同一個圖“G”透過用更多頂點劃分 G 的一些邊得到，則稱這兩個圖 G1 和 G2 為同態。請看下面的例子：
透過新增一個頂點將邊“rs”分成兩條邊。
下面顯示的圖與第一個圖同態。
如果 G1 與 G2 同構，則 G 與 G2 同胚，但反之不一定成立。
任何具有 4 個或更少頂點的圖都是平面圖。
任何具有 8 個或更少邊的圖都是平面圖。
完全圖 Kn 是平面圖當且僅當 n ≤ 4。
完全二部圖 Km, n 是平面圖當且僅當 m ≤ 2 或 n ≤ 2。
具有最少頂點數的簡單非平面圖是完全圖 K5。
具有最少邊數的簡單非平面圖是 K3, 3。
多面體圖
如果一個簡單連通平面圖的每個頂點的度數都≥ 3，即 deg(V) ≥ 3 ∀ V ∈ G，則稱該圖稱為多面體圖。
3|V| ≤ 2|E|
3|R| ≤ 2|E|