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