这样的线路能否布在单面印刷电路板上

随着电子工业的迅猛发展，印刷电路板线路的设计和制造日益受到人们的重视。在印刷电路板的线路图上，元件用顶点表示，元件之间的连线用相应的边表示。设计的基本要求是：在单面板上，图中的边至多在顶点处相交，不能在其他地方相交，这样才不会发生短路。

现在要问：右面这个图（图1）如果被制成印刷电路，它能够被布在单面板上吗？

图1

告诉你：这个图尽管看上去很简单，但它却是不可能被布在单面板上的。为什么呢？这个道理可以分几步来说明。

大家知道，整个平面可以看成一个连通区域。5个顶点、4条边的连通图在图论中称为“树图”，总共有图2～4这三种类型。它们都不能将整个平面分隔成两个不同的区域。树图都能够被布在单面印刷电路板上。

5个顶点、5条边的连通图，共有图5～9五种类型。它们不是树图，但也都能够被布在单面印刷电路板上，并且将整个平面分隔成两个不同的连通区域。

将图2～9进行归纳比较，我们可以发现一个重要的数学关系式：

连通区域数=边数-3。

这个关系式对于5个顶点的、可以布在单面板上的连通图是普遍成立的。当边数分别等于4、5的时候，我们已经从上面列举的图例中知道它是正确的。

根据上述关系式可以看出，由于图1是允许情况下边数最多的图（任意两个顶点之间都有边连接），共有10条边，因此在我们讨论的问题中，连通区域数不会超过7个。下面对连通区域数k应用数学归纳法，证明上列关系式是正确的。

设上式在连通区域数等于k时成立。在连通区域为k+1（这里k+1≤7，否则没有意义）时，任意挑出1条处于2个连通区域公共边界上的边。删去这条边以后，所牵涉到的2个连通区域就并成1个连通区域，其他的连通区域保持不变。从总体上说，连通区域数减少了1个，后一图中的连通区域数为k。根摇数学归纳法的假设，这时图中的边数应该是k+3，所以原来在连通区域数为k+1的时候，边数一定是k+4，仍是满足上列关系式。这就证明了该关系式对于5个顶点的、可以布在单面板上的连通图都是成立的。

这样一来，对于开始提出的问题其答案就比较明朗了。图1中有10条边，如果这个图可以布在单面板上的话，那么整个平面一定被分隔成7个连通区域，这是由上面公式所得出的必然推论。另一方面，如果图1可以被布在单面板上并且出现7个连通区域的话，在这个具体问题中，每个连通区域的边界至少有3条边；在统计边的总数时，每条边都被重复计算了一次，所以图1的边数必须不小于21/2，即至少有11条边。这是一个矛盾，从而证实了图1不可能被布在单面板上。

在图论中，图1专门用记号K₅表示。与K₅类似的是右面的图10，它也不可能被布在单面板上，这个图在图论中专门用K_3，3表示。

图10

K₅与K_3，3这两个图除了不能布在单面板这个共同特点以外，在图中任意删去一个顶点（当然此时与该顶点相连的边也随之删去），或者在图中任意删去一条边以后，得到的图一定可以布在单面板上。这件事很有趣，你不妨动手验证一下。

如果一个图是另一个图用链图换去边而得到的，那么这个图叫做另一个图的“剖分图”。例如，图11是K₅的剖分图，图12是K_3，3的剖分图。1930年，波兰数学家库拉托夫斯基发表了一条非常著名的定理：一个线路可以被布在单面板上filj充分必要条件是，对应的图中不包含K₅、K_3，3以及它们的剖分图。也就是说，一个图无论怎样复杂、庞大，只要它不含有K₅，不含有K_3，3，以及不含有它们的剖分图，那么一定可以被布在单面板上。这条定理对于印刷电路板的线路设计及制造，当然是极其重要的了。