Untitled Course平面图

尝试将每个房屋连接到下面的每个公用设施，而您的任何线路都不能相交：

就像以前的柯尼斯堡桥一样，您很快就会发现这个问题也是不可能的。似乎可以绘制一些没有重叠边的图-这些被称为__平面图__ - 但是其他图则不能。

该完全图 K5是最小图同时又是非平面。任何其他包含K5作为子图的图在某种程度上也不是平面的。这包括K6 ， K7 ，以及所有较大的完全图。

三个基础设施难题中的图是二分图 K3,3 。事实证明，任何非平面图都必须包含一个K5或一个K3,3 （或这两个图的细分 ）作为子图。这称为_Kuratowski定理_ 。

欧拉公式

所有平面图会将它们绘制的平面划分为多个区域，称为 面 。

比较这些数字时，您会注意到边缘的数量总是少一大与面数加顶点数相同。换一种说法， F + V = E +1。该结果称为__欧拉方程__ ，并以解决柯尼斯堡桥问题的同一位数学家的名字命名。

不幸的是，有无限多的图，我们不能检查每个图来看看欧拉方程是否有效。相反，我们可以尝试找到适用于任何图形的简单证明 ……

可以通过从一个顶点开始并一个接一个地添加更多的顶点来构造任何（有限）图。我们已经表明，无论以哪种方式添加新顶点，欧拉方程都是有效的。因此，它对所有图均有效。

我们使用的过程称为 数学归纳法 。这是一种非常有用的技术，可通过从最简单的案例入手，并在构造更复杂的案例时证明每一步的结果都成立，从而在无限多的案例中证明结果。

许多平面图看起来非常类似于多面体 （具有多边形面的三维形状）的网络。如果我们认为多面体是由弹性带制成的，我们可以想象将其拉伸直到它们变成平坦的平面图：

这意味着我们不仅可以将Euler公式用于平面图，而且可以将其用于所有多面体 – 差别很小。将多面体转换为图时，图中的一个面消失了：多面体的最上面的面成为“外面”。

换句话说，如果您计算_任何_多面体的 边 面 和 顶点，您会发现 F + V = E + 。