圖論/平面圖

平面圖

定義

平面圖是指可以在平面上繪製的圖，沒有邊交叉。

特徵

平面圖可以透過一個定理來描述，該定理最初由波蘭數學家卡齊米日·庫拉托夫斯基在1930年證明，現在被稱為庫拉托夫斯基定理。

• 有限圖是平面圖，當且僅當它不包含一個子圖，該子圖是 $K_{5}$ 或 $K_{3,3}$ 的細分。

圖的細分是透過在邊中插入零個或多個頂點得到的。

瓦格納定理處理的是次圖，而不是細分。

• 有限圖是平面圖，當且僅當它沒有 $K_{5}$ 或 $K_{3,3}$ 作為次圖。

如果可以透過重複刪除邊和/或邊收縮從圖 G 中獲得圖 H 的副本，則圖 H 是圖 G 的次圖。