跳至內容

庫拉托夫斯基定理

維基百科,自由的百科全書
廣義佩特森圖 G(9,2)中包含K3,3的細分, 說明廣義佩特森圖不是平面圖.

庫拉托夫斯基定理(英語:Kuratowski's theorem)是一個關於平面圖的等價判定定理,它由波蘭數學家卡齊米日·庫拉托夫斯基提出[1]。這個定理表明,一個圖是平面圖若且唯若它不包含K5 或 K3,3細分。其中,K5是包含5個頂點的完全圖,K3,3是包含6個頂點的完全二分圖,其中三個頂點和另外三個頂點兩兩相連,K3,3也被稱作utility graph英語utility graph

進一步闡述

[編輯]

平面圖(planar graph)是可以畫在平面上,使得不同的邊在除了端點之外互不相交的圖。

細分(subdivision)是在一個圖的一些邊上加入一些點,使得這些邊被分割成包含一條或多條邊的路徑。庫拉托夫斯基定理表明,一個圖G是平面圖,如果它不能通過細分K5K3,3的邊,然後再加上一些多餘的邊或點得到。等價地,一個圖是平面圖若且唯若它不包含同胚(Homeomorphism)於K5 或 K3,3的子圖。

庫拉托夫斯基子圖

[編輯]

G是一個圖,如果它包含K5K3,3的細分H,那麼H被稱為G的一個庫拉托夫斯基子圖[2]

K5K3,3均不是平面圖,這可以分類討論或利用歐拉公式進行驗證。此外,細分一個非平面圖不可能得到一個平面圖。這是顯然的,如果一個圖G的細分G′有平面畫法,那麼把G′中通過細分邊e得到的路徑的平面曲線段當作原圖Ge的平面曲線段,我們也可以得到G的一個平面畫法。因此,一個包含庫拉托夫斯基子圖的圖不是平面圖。定理的另一邊證明則更加困難。

相關結論

[編輯]

庫拉托夫斯基定理和另一個平面圖等價判定定理瓦格納定理(Wagner's theorem)[3]高度相關。瓦格納定理表明,一個圖是平面圖若且唯若 K5 或 K3,3 不是它的次圖(minor)。次圖又稱圖子式,如果無向圖H可以通過圖G刪除邊和頂點或收縮邊得到,則稱HG的子式或次圖。

顯然,如果圖G包含庫拉托夫斯基子圖,那麼K5 或 K3,3一定是它的子式。反之,可以驗證任意包含K5 或 K3,3子式的圖G也必然包含庫拉托夫斯基子圖[4]。因此,兩個定理實際上是等價的。

參考資料

[編輯]
  1. ^ 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) (法語) .
  2. ^ 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 .
  3. ^ Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937, 114: 570–590, doi:10.1007/BF01594196 
  4. ^ Bondy, J. A.; Murty, U.S.R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 269, 2008, ISBN 9781846289699 .