库拉托夫斯基定理
库拉托夫斯基定理
条目
定理背景
最常见的就是布线问题。一个复杂的网络能否布在平面上而又不自相交叉？做印制电路时自然会碰到这个问题。有的图把一条对角线移到方形外面就可以布在平面上。但有的图却无论怎样移动都不能布在平面上。1930年K·库拉托夫斯基证明，一个网络是否能嵌入平面，就看其中是否不含有k5或k3,3两个图之一。
判定方法
判断一个图是否为平面图是一件困难的事。通常我们可以采用直观的方法，即：在图中找出一个长度尽可能大的且边不相交的圈；然后将图中那些相交于非结点的边，适当放置在已选定的圈内侧或外侧，若能避免除结点之外边的相交，则该图为平面图，否则便是非平面图。