平面图(planar graph)是画在平面上的无向图，它要求不同的边不能重叠。btw,如果不太熟悉图的定义，你可能很难读下去。
这种图是自然的，为什么这么说呢？因为在地球上，如果把每个国家抽象化为一个点，国家之间相邻看做两个点有连接（有边）的话，那么所有国家及其相邻情况就可以被视作一个图，而且这个图是平面图。你可能怀疑，地球可是圆的啊，真的可以吗? 实际上，球面与闭复平面的结构是相同。所以把地图展开到闭复平面上再转化为平面图就没有困难了。
有趣的是，平面图有很多优良的，直观的性质，这也是我为什么写这篇博客的原因。
其中一马当先的是欧拉公式。我想很多人都熟悉欧拉公式，这是一个神奇的、普适的公式。V + F - E = 2. 这个公式实际上来自拓扑，适用于具有很精致的结构的复型。 V, F, E分别代表vertex, face, edge的个数。
任何的平面图本身都是一个复型，或者说它符合欧拉公式。这与其他的图结构是很不相同的：有交叉边的图无法使用欧拉公式。因此我们从几何结构的观点区分出了平面图：平面图具有的简洁的结构使得欧拉公式可以应用。
为了有个直观的理解，我们拿正方体举例，8个点，6个面，12条边，算一算果真是2. 应用于正四面体，4 + 4 - 6 = 2. 而这些凸多面体本质上都是平面图，这也是为什么欧拉公式被人们熟知可以应用到凸多面体上的原因。（连通性在文中都被假定为单连通）
很抱歉没有添加几副图片，昨天刚听导师说了加入图片方便听众理解。主要是，我把博客当作自己记录的地方，没有那么多的心思去提高其阅读质量，否则我也不会写对基础知识要求这么高的博客了。
还有一点，对于平面图，任何一条边都被面用了两次，而每个面至少用了三条边围出来，因此我们有 3F \leq 2E.（早知道用stackedit了）
代入欧拉公式，我们有 E \leq 3V - 6. 这预示着，不可能每条边的度都大于等于6，否则 E \geq 3V. 而这引申出了另一个有趣的问题：染色问题。
大家都听说过四色定理：四个颜色画地图（也就是染色平面图）足够了。这是一个多年前被计算机通过穷举证明的问题，引发了数学家们一系列的争论。而通过上面我们得到的结论，6种颜色染色平面图总是可以的，其逻辑比较复杂，我就不赘述了，但是这也告诉我们，4色、5色、6色问题的难度是完全不同的。（其中5色问题已被数学证明）
还有一个有趣的应用就是 三间小屋问题，具体statement可以通过链接找到。我想很多人都思考过类似的问题，尤其是玩游戏的时候，怎么连管子可以不用重叠。3-3的完全二分图不是平面图就告诉我们，三个房子，三种公共资源公司，怎么连都不能保证管子不重叠。（虽然这不是现实问题）
而更有趣的是，上面两个例子就构成了平面图的全部内容：
一个简单图是平面图当且仅当它并不包含一个是 K5 或 K3,3 的分割的子图。
这是库拉托夫斯基禁用准则，称得上是定理。K5 就是我们刚才说的，如果你找到了K5（5个点的完全图）,那么 E = 10, 3V-6 = 9, 于我们通过欧拉公式得到的平面图的必要条件相矛盾；而后者K3,3是3-3的完全二分图，正是我们讨论的三间小屋问题。
总结而言，一个无向图要想成为平面图，就必须没有K5，K3,3子图产生的矛盾。同时为了染色平面图的点，我们需要且仅需要四种颜色，而6种颜色使得染色过程比较平滑，甚至写出一个专门的算法。
平面图作为图论中与现实联系相当紧密的图，也算被研究地先当透彻了。下次我会聊聊平面图的对偶图，这也是个很有趣的概念
没有评论:
发表评论