图论的应用

平面图形

一个图G如果它可以在平面上以这样一种方式表示，即顶点都是不同的点，边都是简单的曲线，并且除了端点之外没有两条边彼此相交，则称为平面的。例如,K₄，四个顶点上的完整图为平面，为图4一所示。

有两个图是同胚的如果两者都可以通过边的细分从同一图中获得。例如，图图4一而且图4 b是同胚的。

的K_米，n图是一个图，其中顶点集可分为两个子集，一个与米顶点和另一个n顶点。同一子集中的任意两个顶点是不相邻的，而不同子集中的任意两个顶点是不相邻的相邻．波兰数学家卡兹米尔兹Kuratowski在1930年证明了以下著名定理:

一个图的充要条件G平面是指它不包含同胚的子图K₅或K_{3, 3}所示图5．

图的初等收缩G是一个变换G到一个新的图形G₁，使两个相邻顶点u取υ ofG被一个新的顶点所取代w在G₁而且w是相邻的G₁到任意的顶点u或者取υ是相邻的G．一个图表G*被认为是a收缩G如果G*可从G通过一个初等序列宫缩．下面是德国数学家K.瓦格纳在1937年对平面图形的另一种描述。

一个图是平面的当且仅当它不能收缩到K₅或K_{3, 3}．

的四色地图问题

一个多世纪以来，每一个试图解决四色地图问题的分析家都没有找到答案。这个问题可能已经引起了Möbius的注意，但第一次书面提到它似乎是一封来自弗朗西斯·格思里的信，他的兄弟，一个学生奥古斯都·摩根1852年。

问题在于平面地图——也就是说，将平面细分为由简单闭合曲线限定的不重叠区域。在地理地图中，根据经验，在许多尝试过的特殊情况下，我们观察到，要给两个地区上色，最多需要四种颜色，这样，两个有共同边界的地区的颜色总是不同的，在某些情况下，至少需要四种颜色。只在某一点会合的地区，如美国的科罗拉多州和亚利桑那州美国，不认为有一个共同的边界)。它的形式化经验观察构成这就是所谓的"四色定理"问题是证明或推翻这一断言，即这是对每一个平面地图的情况。那三种颜色不会足够了是很容易证明的，而五种颜色的充分性是在1890年由英国数学家P.J.海伍德证明的。

1879年，英国人a·b·肯普提出了四色问题的解决方案。虽然Heawood证明了Kempe的论点是有缺陷的，但它的两个概念在后来的调查中被证明是富有成效的。其中之一被称为不可避免性，它正确地指出，不可能构建一个地图，其中四种构型中的任何一种都不存在(这些构型包括一个有两个邻居的区域，一个有三个邻居，一个有四个邻居，一个有五个邻居)。第二个概念，可还原性，得名于肯普的有效性证明如果有一张地图需要至少五种颜色，并且包含一个有四个(或三个或两个)邻居的地区，那么必须有一张地图需要五种颜色，用于较少数量的地区。肯普试图证明一张包含五个相邻区域的地图的可约性错误的，但它在1976年由美国的肯尼斯·阿佩尔和沃尔夫冈·哈肯发表的证明中得到了修正。他们的证明吸引了一些人批评因为它需要评估1936个不同的案例，每个案例涉及多达50万个逻辑操作。阿佩尔、哈肯和他们的合作者设计了一些程序，使大型数字计算机处理这些细节。计算机需要1000多个小时来完成这项任务，最终的正式证明长达数百页。

欧拉循环和Königsberg桥问题

一个油印G由非空集合组成V（G)的顶点和子集E（G的不同元素的无序对的集合V（G)以一个频率f每对上有≥1个连接。如果配对(x₁，x₂)f属于E（G)，然后是顶点x₁而且x₂由f边缘。

一个欧拉周期一个多重图的G是一个闭链，其中每条边恰好出现一次。欧拉证明，当且仅当多重图连通(除孤立点外)且奇度顶点数为0或2时，多重图具有欧拉循环。

这个问题首先以以下方式出现。普雷格尔河，由融合它的两条支流之一，穿过Königsberg镇，流经Kneiphof岛的两侧。有七座桥，如图所示图6．镇上的人想知道是否有可能去散步，每座桥都只过一次。这等价于找到一个欧拉循环图6 b．欧拉证明了这是不可能的因为有四个奇序顶点。

指示图

有向图G由一组非空元素组成V（G)，称为顶点，以及一个子集E（G的不同元素的有序对V（G)．元素(x，y)E（G)可以称为边，边的方向是从x来y．两个(x，y)及(y，x)可能是边。

一个封闭路径在有向图中是顶点序列x₀x₁x₂····x_n＝x₀，以致于(x_我，x_{我+ 1}的有向边我= 0,1，···，n−1。对于每条边(x，y有向图的)G可以分配一个非负的权重函数f（x，y)．接下来的问题是找到一条封闭路径G遍历所有顶点，使路径中所有边的权值之和为最小值。这是典型的优化问题。如果顶点是特定的城市，边是连接城市的路线，权重是路线的长度，那么这就变成了旅行推销员问题也就是说，他可以访问每个城市而不重走原路吗?除了某些特殊情况外，这个问题仍然没有解决。