庫拉托夫斯基定理（英語：Kuratowski's theorem）是一個關於平面圖的等價判定定理，它由波蘭數學家卡齊米日·庫拉托夫斯基提出[1]。這個定理表明，一個圖是平面圖若且唯若它不包含K5 或 K3,3的細分。其中，K5是包含5個頂點的完全圖，K3,3是包含6個頂點的完全二分圖，其中三個頂點和另外三個頂點兩兩相連，K3,3也被稱作utility graph。
 |
進一步闡述
平面圖（planar graph)是可以畫在平面上，使得不同的邊在除了端點之外互不相交的圖。
細分(subdivision)是在一個圖的一些邊上加入一些點，使得這些邊被分割成包含一條或多條邊的路徑。庫拉托夫斯基定理表明，一個圖G是平面圖，如果它不能通過細分K5或 K3,3的邊，然後再加上一些多餘的邊或點得到。等價地，一個圖是平面圖若且唯若它不包含同胚（Homeomorphism）於K5 或 K3,3的子圖。
庫拉托夫斯基子圖
G是一個圖，如果它包含K5或 K3,3的細分H，那麼H被稱為G的一個庫拉托夫斯基子圖。[2]
K5和 K3,3均不是平面圖，這可以分類討論或利用歐拉公式進行驗證。此外，細分一個非平面圖不可能得到一個平面圖。這是顯然的，如果一個圖G的細分G′有平面畫法，那麼把G′中通過細分邊e得到的路徑的平面曲線段當作原圖G邊e的平面曲線段，我們也可以得到G的一個平面畫法。因此，一個包含庫拉托夫斯基子圖的圖不是平面圖。定理的另一邊證明則更加困難。
相關結論
庫拉托夫斯基定理和另一個平面圖等價判定定理瓦格納定理(Wagner's theorem)[3]高度相關。瓦格納定理表明，一個圖是平面圖若且唯若 K5 或 K3,3 不是它的次圖（minor）。次圖又稱圖子式，如果無向圖H可以通過圖G刪除邊和頂點或收縮邊得到，則稱H為G的子式或次圖。
顯然，如果圖G包含庫拉托夫斯基子圖，那麼K5 或 K3,3一定是它的子式。反之，可以驗證任意包含K5 或 K3,3子式的圖G也必然包含庫拉托夫斯基子圖[4]。因此，兩個定理實際上是等價的。
參考資料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
