词汇表

选择左侧的一个关键字...

Untitled Course平面图

阅读时间: ~15 min

这是与图论有关的另一个难题。

在一个小村庄里,有三座房屋和三个公用设施,可生产水,电和煤气。我们必须将每座房屋都连接到每个公用设施,但是由于村庄的布局,不同的管道和电缆不允许交叉。

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

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

K3是平面的。

K4

K5

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

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

平面度

这是一个平面图,但是${n}个顶点已被打乱。重新排列顶点,以使所有边均不重叠。

欧拉公式

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

个顶点 个面 条边 11个顶点+面

个顶点 个面 条边 15个顶点+面

个顶点 个面 条边 25个顶点+面

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

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

FVE
010

0 + 1  =  0 + 1

简单的图由一个顶点组成。我们可以很容易地检查欧拉方程是否有效。
让我们在图中添加一个新顶点。我们还要加一条边,欧拉方程仍然有效。
如果我们想给图添加第三个顶点,我们有两种可能。我们可以创建一个小三角形:这增加了一个顶点,一个面和两个边,所以欧拉方程仍然有效。
相反,我们可以简单地将一条边延长:这就增加了一个顶点和一条边,欧拉方程仍然有效。
让我们继续:如果我们现在创建一个四边形就添一个顶点,两个边和一个面。欧拉方程仍然有效。

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

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

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

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

二十面体 20 个面 12 个顶点 30 条边

菱形十二面体 62 个面 60 个顶点 120 条边

二十面体截断 32 个面(12个黑,20个白) 60 个顶点 90 条边

Archie