图论
图论对数学对象的研究被称为图,其中包括顶点(或节点)连接边缘.(在下图中,顶点是有编号的圆,边缘与顶点相连。)
对于图论来说,任何希望检查连接对象网络结构的场景都是潜在的问题。图论的例子不仅经常出现在数学中,也经常出现在物理和计算机科学中。
术语
一个非平凡的图由一个或多个组成顶点(或节点)连接边缘.每条边恰好连接两个顶点,尽管任何给定顶点都不需要用边连接。的学位是与顶点相连的边的个数。在下图中,顶点 是3次,而顶点 而且 都是2次的。顶点 的度数是1,顶点是 为0次。
注意:如果一个图的每个顶点的度数是相同的,我们可以称之为图的度.
一个可以通过从一个顶点到另一个顶点的边的横贯而到达任何顶点的图称为连接.所使用的边集(不一定是不同的)称为a路径在给定顶点之间。上图是不连接,尽管任意两个顶点之间存在路径 , , , .
一个图被称为完整的如果存在一条边连接每两对顶点。上图并不完整,但可以通过添加额外的边来使其完整:
求一个完整图的边数 顶点。
求一个完整图的边数是一个相对简单的计数问题。考虑构造一个完整的图的过程 没有边顶点。一个程序是一次处理一个顶点,并在它和所有没有连接到它的顶点之间绘制边。首先, 可以在给定顶点和对象之间绘制边 其他的顶点。接下来, 在第二个顶点和 其他顶点(减去第一个顶点,它已经连接了)。一般来说,每个连续顶点需要连接的边比它前面的边少一条。因此,总边数为
同样,选择两个顶点(必须有一条边将它们连接起来)的方法的数量为
对于不同的应用程序,给边或顶点(或两者)一些可能是有意义的重量.例如,可以考虑一个由美国各个城市组成的图表,连接它们的边代表城市之间可能的路线。如果你想找到城市之间最短的物理路径,那么用城市之间的物理距离来衡量边缘是有意义的。
图形也可以是导演或无向:有向图中的每条边都可以指向一个或两个节点(例如,表示单向旅行)。
本文其余的大部分内容将关注连接图、无权重图和无向图。
欧拉图
有许多类型的特殊图。一种常见的类型是欧拉图,它们的所有边在一条路径中只访问一次。这样的路径被称为欧拉路径.事实证明,很容易排除许多图non-Eulerian通过以下简单的规则:
欧拉图最多有两个奇次顶点。
要了解为什么这个事实是正确的,考虑一下,只有在遍历过程中,一个顶点开始或结束在奇数度顶点上,才有可能遍历连接到该顶点的所有边。否则,必须总是进入和退出一个给定的顶点,它使用两条边。但是,入口和出口顶点可以被遍历奇数次。因此,这样的顶点不可能超过两个,否则在试图遍历图时,其中一个顶点会在某个点上“卡住”。
经典的欧拉图问题是Königsberg的七座桥的问题,欧拉在1736年解决了这个问题。
Königsberg的七座桥:
Königsberg的城市由七座桥连接,如图所示。每座桥只过一次就能游览整个城市吗?
首先,我们将城市的不同部分表示为顶点,将每座桥表示为连接城市两个部分的顶点,如下所示。
该图包含两个以上的奇次顶点,因此它不是欧拉图。因此,每座桥只过一次是不可能的。
类似的图形类型是哈密顿路径在这种情况下,可以通过访问每个节点来遍历图顶点完全一次。一般来说,计算哈密顿路径(如果存在的话)不是一个简单的任务。
平面图形
图着色
图论中的一个重要问题是图着色.假设图中的每个顶点都被分配了一种颜色,这样相邻的顶点就没有相同的颜色。显然,可以用这种方式为每个图上色:在最坏的情况下,可以简单地使用与顶点数量相等的颜色数量。(事实上,对于一个完整的图,颜色的最小数量等于顶点的数量。)特别有趣的是最低数量的颜色 需要避免连接颜色相似的顶点,这被称为彩色数字 的图。等价地,这个图被称为 似是而非的。
特别是,在给地图上色时,一般都希望避免两国边界相同的颜色。的问题地图着色简洁地简化为一个图形着色问题:简单地用顶点表示每个国家,用一条边连接共享边界的每对国家。1976年,阿佩尔和哈肯证明了四色定理,该理论认为,与地图对应的图的色数都不大于4。