-
正则
-
完全
图论游乐场
图是一组点(称为顶点)和连接它们的线(称为边)。在这里点几下就能画出一张图,游乐场会告诉你它是哪种图:它分成几个连通块、是不是树、最少需要几种颜色、能不能一笔画出,等等。点击某个性质就能在图上看到它;改动一条边,看看答案如何随之变化。 点击空白处可添加顶点。先点击一个顶点,再点击另一个,就能用一条边把它们连起来;再做一次则删除这条边。拖动顶点可以移动它。把“点击”切换为“擦除”,再点击顶点或边即可删除。选中顶点后,按 Delete 删除它,按 Escape 取消选择。点击某个性质,即可在图上显示。“示例”加载一张著名的图,“随机图”生成一张图,“整理”让顶点均匀散开,“补图”恰好连接原来没有相连的顶点对。Ctrl+Z 撤销一步。
它是如何运作的
- 点击空白处添加顶点。先点击一个顶点,再点击另一个,把它们连起来;再做一次则删除这条边。拖动顶点可以移动它。
- 查看图下方的性质,点击其中一个即可显示:一种着色、两边的划分、一条欧拉路径、一棵生成树、最短环或直径。
- 加载彼得森图等示例,生成随机图,求补图,或把“点击”切换为“擦除”来删除顶点和边。
各个性质的含义
顶点的度数是与它相连的边的条数。如果每个顶点都能沿着边到达其他任何顶点,图就是连通的;如果连通且没有环,就是树。如果顶点能分成两边,且每条边都横跨两边,图就是二部图,这恰好等价于图中没有奇数长度的环。色数是让相邻顶点颜色各不相同所需的最少颜色数。最短环的长度称为围长,直径则是两个顶点之间的最大距离,以边数计。
一笔画
欧拉路径恰好经过每条边一次。1736 年,莱昂哈德·欧拉通过柯尼斯堡七桥问题看出了其中的障碍:路径每经过一个顶点,就要用掉它的两条边。因此,要么所有顶点的度数都是偶数,路径可以回到起点;要么恰好有两个顶点的度数是奇数,路径必须从其中一个走到另一个。后来,卡尔·希尔霍尔策证明,只要所有边连成一体,这个条件也是充分的。加载房子示例,找找一笔画必须从哪里开始。
常见问题
图论中的图是什么?
一组点(称为顶点或节点),以及连接其中一些点对的线(称为边)。它不是函数的图像:它只描述什么和什么相连。道路地图、社交网络、分子和计算机网络都是图。
色数是怎么算出来的?
游乐场先尝试用一种颜色给图着色,然后两种、三种,依此类推;对每个数,它都会搜索所有关键的着色方式,并且总是优先给邻居已用颜色最多的顶点着色。第一个可行的数就是色数。对于这里能画出的图,这最多只需片刻;遇到非常困难的图时,搜索会提前停止,结果显示为上界。
图在什么情况下有欧拉路径?
当所有边连成一体,且奇度顶点不超过两个时。没有奇度顶点时,存在回到起点的欧拉回路;有两个时,每条欧拉路径都从其中一个出发,到另一个结束。奇度顶点的个数总是偶数,所以永远不会恰好是一个。
什么是图的补图?
顶点相同、边恰好是原来没有相连的那些顶点对的图。补图的补图就是原来的图。例如,彼得森图的补图是 6-正则的,因为每个顶点原来与其余 9 个顶点中的 3 个相连。
彼得森图为什么这么有名?
它是一张只有 10 个顶点、15 条边的小图,却是许多美好猜想的反例。每个顶点的度数都是 3,最短环长度为 5,任意两个顶点之间最多相隔 2 条边,而且无法在边不交叉的情况下画出来。游乐场一打开就是这张图。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器