庫拉托夫斯基定理
 |
庫拉托夫斯基定理（英語：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]。因此，兩個定理實際上是等價的。
參考資料
- ^ Kuratowski, Kazimierz, Sur le problème des courbes gauches en topologie (PDF), Fund. Math., 1930, 15: 271–283 [2020-12-22], （原始內容存檔 (PDF)於2018-07-23） （法語）.
- ^ Tutte, W. T., How to draw a graph, Proceedings of the London Mathematical Society, Third Series, 1963, 13: 743–767, MR 0158387, doi:10.1112/plms/s3-13.1.743.
- ^ Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937, 114: 570–590, doi:10.1007/BF01594196
- ^ Bondy, J. A.; Murty, U.S.R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 269, 2008, ISBN 9781846289699.