图论中一些与之相关最基本重要的定义( 二 ) _小知识

文章插图

在一个有向图中，可能出现这种情况：从一个顶点开始，沿着边前进，最终回到起始顶点。如果发生了这种情况，表明我们走了一个圈，我们走过的路径形成了一个环（cycle）。在一个无向图中，如果允许向后退，我们总能回到起点，因此我们说走了一个圈指的是在不沿着边后退的情况下回到起点。存在环的图被称为有环的（cyclic），不包含环的图被称为无环的（acyclic）。图 2-8 显示了两个包含多个环的有向图。注意，右边图中的一些边的起、止都是同一个顶点。这些边形成了长度为 1 的环，我们称之为自环（loop）。自环在无向图中也是可能的，但并不常见。有向无环图出现在非常多的应用中，以至于人们特意为其起了一个名字，简称 dag 。为了使这部分图形完整，图 2-9 显示了两个无环图，一个是无向的，另一个是 dag 。
【图论中一些与之相关最基本重要的定义】

文章插图

将一个图的顶点分为两个集合，使得所有边都是连接一个集合中的顶点和另一个集合中的顶点，这是可能的，这样我们就得到了一个二部图（bipartite graph）。二部图的一个经典应用是匹配（matching）问题，其中我们希望将一个集合中的实体与另一个集合中的实体进行匹配（例如，可能一个集合中是人，另一个集合中是分配给人的任务）。实体表示为顶点，指出实体兼容的连接用边表示。为避免陷入困境之中，实体间一对一精确匹配是很重要的。如图 2-10 所示，一个图是否为二部图，检查结论并不总是那么清晰，除非我们重新安排顶点位置。

文章插图

有大量边的图和没有大量边的图有着重要区别。一个图如果有大量的边，我们称它是稠密的（dense），否则我们称它是一个稀疏图（sparse graph）。一种极端情况是，在一个图中可能任意两个顶点间都有边相连，这种图被称为完全图（complete graph），你可以在图 2-11 中看到一个例子。显然，它有很多条边。对 n 个顶点的图，由于每个顶点连接到所有其他 n-1 个顶点，我们有 n(n-1)/2 条边。一般而言，如果一个 n 个顶点的图有接近 n2 条边，我们就可以说它是稠密的，如果它的边数接近 n ，就称它是稀疏的。这在 n 和 n2 间留下了一个模糊区域，但我们通常从上下文就可以知道我们处理的是稀疏图还是稠密图。实际上大多数应用使用的是稀疏图。例如，设想我们有一个图表示人之间的朋友关系。我们以一个包含 70 亿(n=7×10^9)个顶点的图为例，即假定这个星球上几乎所有人都在这个图中。我们还假定每个人连接到 1000 个朋友，这在实际中几乎是不可能的。则边的数量为 7×10^12 ，即 7 万亿。而对于 n=7×10^9 ， n(n-1)/2 的值约为 2.5×10^19 ，即约 2000 亿亿，这远大于 7 万亿。这个例子说明，一个图可能有非常多的边，但它仍是稀疏的。
本文摘编自机械工业出版社华章公司出版的《真实世界的算法：初学者指南》