库拉托夫斯基定理
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/7/73/GP92-Kuratowski.svg/240px-GP92-Kuratowski.svg.png)
库拉托夫斯基定理(英語: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.
|