词汇表

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

平面图

阅读时间: ~15 min
此页面已自动翻译,可能包含错误。如果您想帮助我们审核翻译,请与我们取得联系!

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

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

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

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

K3是平面的。

K4

K5

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

三个实用程序难题中的二部图 K3,3 。事实证明,任何非平面图都必须包含一个K5或一个K3,3 (或这两个图的细分 )作为子图。这称为Kuratowski定理

平面度

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

欧拉公式

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

顶点
面孔

11个顶点+面

顶点
面孔

15个顶点+面

顶点
面孔

25个顶点+面

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

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

FVE
010

0 + 1  =  0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.
Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.
If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.
Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.
Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

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

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

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公式用于平面图,而且可以将其用于所有多面体–差别很小。将多面体转换为图形时,其中一个面消失了:多面体的最上面的面成为“外面”;图。

换句话说,如果您计算边缘 面孔 任何多面体的_顶点 ,您会发现{.b.blue} F_ + V = E +

二十面体
20张面孔
12个顶点
30条优势

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

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