网络能布在平面上吗—嵌入问题

在我们现在信息时代，最常见的就是复杂的电路，电路的结点可以成千上万，抽象来看，就是由顶点及其间连线构成的图。图可分成三类：一类图画出来，其中每条连线均彼此不相交，这类图称为平面图；一类图画出来时，连线有的相交，但是经过移动后，可变成没有相交连线的平面图，这种图称为可平面化的图，或者称为可以嵌入到平面上的图。还有的图无论怎么样改造，总也不能变成平面图，这种图称为不可平面化的图，最典型的不可平面化的图是k5及k（3，3）一个有p个顶点，q条连线的图可平面化的条件是什么呢？它必须满足q≤3P－6 （P≥3）而且可平面的图一定包含一个顶点，它的阶（即过顶点的连线数目）≤5。由上面不等式我们可以证明K5不可平面化。K5有5个顶点和10条连线，因此10＞3×5－6＝9与上面不等式矛盾。但K（3，3）不可平面化需要其他工具。
     一个线路能否布在平面上而不自相交叉，这类问题称为嵌入问题，如图K5和 K3，3两个线路图就无法布在平面上而不自相交叉。现代的电路十分复杂，我们当然希望知道它能不能布在平面上不自相交叉，要是不能嵌入在平面当中，交叉就要用分层、穿孔等办法弄到空间去，线路画起来、看起来都麻烦，这就要靠拓扑学了。1930 年，波兰数学家库拉托夫斯基证明：K5、K（3，3）两图是一个图不能嵌入到平面中去的仅有障碍，也就是说，一个图能够嵌入到平面中去的充分必要条件是它不含有像K5和K（3，3）那样的部分图。从拓扑上来讲，我们也可把图嵌入到球面和其他走向曲面之上。