图论
一些点,加上点与点之间的连线:这就是图的全部。然而同一幅图可以描述道路地图、朋友关系网、分子和互联网;而关于它的问题,从需要几种颜色到能否一笔画出,自 1736 年以来一直让数学家们忙个不停。
顶点和边
图由顶点(也叫节点)和边组成,每条边连接两个顶点。顶点画在哪里并不重要,重要的只是哪些顶点对相连,所以同一张图画在纸上可能看起来大不相同。游乐场中的图都是简单图:没有从顶点连回自身的边,两个顶点之间最多只有一条边。n 个顶点最多可以有 n(n − 1) / 2 条边;所有边都有的图称为完全图,K5 就是五个顶点的完全图。
度数与握手引理
顶点的度数是与它相连的边的条数。把所有度数加起来,恰好得到边数的两倍,因为每条边都有两个端点,在每一端各计一次。这就是握手引理:在任何一群人中,逐人统计的握手次数之和,等于握手总次数的两倍。这也意味着度数为奇数的顶点个数总是偶数。每个顶点度数都等于 k 的图称为 k-正则图。
连通图、树和环
如果从每个顶点都能沿着边到达其他任何顶点,图就是连通的;否则它会分成若干部分,称为连通分量。环是一条不重复经过顶点、最后回到起点的回路,最短环的长度称为围长。没有环的连通图是树,有 n 个顶点的树总是恰好有 n − 1 条边:少一条就会断开,多一条就会出现环。每个连通图都包含一棵生成树,即只用部分边就能到达所有顶点的树。
二部图与着色
给顶点着色,使得没有一条边连接两个同色顶点。做到这一点所需的最少颜色数就是色数。只有在没有边时,一种颜色才够用。两种颜色够用,恰好是在图为二部图时:它的顶点分成两边,每条边都横跨两边。1936 年,德内什·柯尼希证明,这等价于图中没有奇数长度的环,因为奇环无法用两种颜色交替着色。对于三种或更多颜色,还没有已知的这类简单判据:判断三种颜色是否够用是 NP 完全问题,所以程序只能搜索,游乐场也是这样做的。
示例:彼得森图
取一个五边形 A–B–C–D–E,在里面放一个五角星 F–H–J–G–I,再把五边形的每个角连到五角星的一个顶点:A–F、B–G、C–H、D–I 和 E–J。这就是彼得森图,有 10 个顶点和 15 条边。每个顶点的度数都是 3,所以度数之和为 30,正是 15 的两倍。它的最短环长度为 5,所以没有三角形;但五边形是奇环,所以它不是二部图,需要 3 种颜色。任意两个顶点之间最多相隔 2 条边,所以直径为 2。十个度数全是奇数,所以它没有欧拉路径,而且无法不交叉地画出来。
欧拉路径与柯尼斯堡七桥
柯尼斯堡城有七座桥,连接着四块陆地,人们问:能否恰好走过每座桥一次?1736 年,莱昂哈德·欧拉证明这做不到,图论由此诞生。每次走过一块陆地都要用掉两座桥,所以只有起点和终点可以连着奇数座桥,而柯尼斯堡的四块陆地连着的桥都是奇数座。如今,恰好经过每条边一次的路径称为欧拉路径,如果回到起点,则称为欧拉回路。1873 年,卡尔·希尔霍尔策证明这个条件也是充分的:只要所有边连成一体,且奇数度数不超过两个,这样的路径就存在,而他把一个个回路拼接起来的方法至今仍能找到它。
距离、直径和补图
两个顶点之间的距离,是连接它们的路径上最少的边数;直径是图中最大的距离,在不连通的图中为无穷大。社交网络的直径很小,这正是“六度分隔”背后的想法。图的补图有相同的顶点,恰好连接原来没有相连的顶点对。一张图和它的补图,至少有一个总是连通的。
动手试试
游乐场打开时,显示的是用三种颜色着色的彼得森图。点击“度数”验证握手引理,点击“二部图”看一个奇环,然后加载立方体,看两边如何出现。加载房子,点击“欧拉路径”,看看一笔画必须从哪里开始。画一张自己的图,一次加一条边:看最短环变短、直径下降,以及在 K4 的最后一条边加上时色数如何升高。
常见问题
路径、迹和途径有什么区别?
途径是由边相连的任意顶点序列,顶点和边都可以重复。迹可以重复顶点,但不能重复边,所以欧拉路径(严格地说是欧拉迹)可以多次经过同一个顶点。路径则两者都不重复。
什么是四色定理?
它说的是,任何能在纸上画成边不交叉的图,都可以用最多四种颜色着色,因此任何地图最多只需要四种颜色。1976 年,肯尼斯·阿佩尔和沃尔夫冈·哈肯借助计算机证明了它,这是第一个用这种方式证明的重要定理。
什么是哈密顿回路?
恰好经过每个顶点一次(而不是每条边一次)的环。它看起来很像欧拉问题,但没有已知的简单判据:判断一张图是否有哈密顿回路是 NP 完全问题。彼得森图有哈密顿路径,但没有哈密顿回路。
图论用在哪里?
路线规划工具在道路图中搜索,搜索引擎根据链接给网页排名,编译器通过图着色来分配处理器寄存器,排课表时给冲突图着色来避免时间冲突,化学家把分子当作图来计数,计算机网络、电网和朋友关系网也都作为图来研究。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开图论游乐场