同態

如果給定兩個圖 G₁ 和 G₂可以透過從圖 'G' 切割一些邊和一些頂點來獲得，則稱這些圖是同構的。請看下面的示例 -

將邊 'rs' 切割成兩條邊，方法是新增一個頂點。

下面顯示的圖同構於第一個圖。

如果 G₁ 同構於 G₂，則 G 同構於 G₂，但反之不一定成立。

• 具有 4 個或更少頂點的任何圖都是平面的。

• 具有 8 條或更少邊的任何圖都是平面的。

• 完全圖 K_n 僅在 n ≤ 4 時是平面的。

• 完全二分圖 K_{m, n} 僅在 m ≤ 2 或 n ≤ 2 時是平面的。

• 具有最小頂點數的簡單非平面圖是完全圖K₅。

• 具有最小邊數的簡單非平面圖是 K_{3, 3}。

多面體圖

一個簡單的連通平面圖稱為多面體圖，如果該圖中每個頂點的度數≥ 3，即 deg(V) ≥ 3 ∀ V ∊ G。

• 3|V| ≤ 2|E|
• 3|R| ≤ 2|E|

Mahesh Parahar 翻譯

更新於： 2019-08-23

1 千次瀏覽

開啟您的 職業生涯

完成課程並獲得認證

開始學習