1.3 图形的度量

与卷1一样，在本书中，我们用输入长度的一个函数来分析不同算法的运行时间。当输入是单个数组时（例如在排序算法中），就存在一种很明显的方式来定义“输入长度”，即数组的长度。当算法的输入涉及图时，就必须指定图的表现形式，并明确它的“长度”的含义。

1.3.1 图的边数量

图的度量是由两个参数控制的，分别是顶点的数量和边的数量。下面是这两个量较常用的表示方法。

在小测验1.1中，我们思考无向图中边的数量与顶点数量的依赖关系。对于这个问题，我们假设每对顶点之间最多只有一条无向边，不允许出现“平行边”。我们还假设图是“连接的”，2.3节将正式定义这个概念。连接的图就是指图是“一整块的”，没有办法在不切断任何一条边的情况下把图分割为两个部分。图1.1(b)和图1.2(a)中的图是连接的，但图1.3中的图是非连接的。

1.3.2 稀疏图和稠密图

在小测验1.1中，我们已经看到了图的边数是如何根据顶点的数量变化的。现在，我们可以讨论稀疏图和稠密图之间的区别。它们的区别是非常重要的，因为有些数据结构和算法更适用于稀疏图，而另一些则更适用于稠密图。

我们把小测验1.1的答案转换为渐进性表示法。首先，如果一个具有n个顶点的无向图是连接的，那么边的数量m至少与n呈线性关系（也就是说，m=Ω (n)）。其次，如果这个图没有平行边，那么m=O(n2)。我们可以总结为：一个不存在平行边的连接无向图的边数是在顶点数的线性关系与平方关系之间。

通俗地说，如果边的数量大致与顶点的数量呈线性关系，那么这个图就是稀疏图；如果边的数量大致与顶点的数量呈平方关系，那么这个图就是稠密图。例如，具有n个顶点和O(n log n)条边的图一般被认为是稀疏图，而边的数量为Ω (n2/log n)的图一般被认为是稠密图。边的数量约等于n3/2的“部分稀疏”图既可以认为是稀疏图，又可以认为是稠密图，取决于具体的应用。

1.3.3 小测验1.1的答案

正确答案：（a）。在一个具有n个顶点并且没有平行边的连接无向图中，边的数量至少为n−1，最多为n(n−1)/2。为了理解这个下界为什么是正确的，可以以图G=(V,E)为例。作为一种理论试验，可以想象在创建G时一次创建一条边，从顶点集V和0条边开始。首先，在添加任何边之前，n个顶点中的每一个顶点都是完全隔离的，因此这个图可以看成n个不同的“片段”。添加一条边(v,w)的效果就是把包含v的片段与包含w的片段融合在一起（见图1.4）。因此，每添加一条边，最多会把片段的数量减少1。为了从n个片段最终缩减为1个片段，至少需要添加n−1条边。有大量的连接图具有n个顶点并且只有n−1条边，这种图称为树（见图1.5）。

一个没有平行边的图的最大边数是由完全图实现的，它包含了每一条可能出现的边。

一个具有n个顶点的图共有对顶点，该值也是边的最大数量。例如，当n=4时，边的最大数量是（见图1.6）。注1

注1：的意思是“在n个中选择2个”，又称“二项式系数”。为了理解为什么从一组n个对象中选择一对不同的无序对象的方法数量是，可以考虑选择第1个对象（从n个选项中），然后选择第2个对象（从n −1个剩余选项中）。在总共n(n−1)个结果中，每对(x, y)对象都出现了2次（一次是首先选择x，然后选择y；另一次是首先选择y，然后选择x）。因此，不同的顶点对数就是。