动机
图形画在纸上的位置、线段的长度都不是图本身的一部分;关键是哪些顶点相连。比较两幅图时,我们需要明确什么叫做只改变名称。计算时还需决定如何存储相邻关系。表示法使用一套具体标号,同构则说明两张图仅在顶点名称上不同。
定义与存储
定义 8.1.1
(邻接矩阵与邻接表)
本节的 是有限简单无向图:每条边是 的二元素子集,没有自环或重边。记 、,并选择顶点次序 。邻接矩阵 的元素 在 时为 ,否则为 。它是对称的,对角线全为零。反过来,每个对称、对角线为零的零一矩阵,都唯一确定其有序顶点集上的一个简单图。
邻接表为每个顶点记录它的邻居。每条边在两张表中各出现一次;孤立顶点的表为空,但仍须记录顶点集,避免丢失孤立顶点。
矩阵占 个位置,可通过一次索引查询两个顶点是否相邻。邻接表占 个位置,计入访问表头后,完整扫描 的邻接表需 次操作;但查询任意一对顶点是否相邻可能需要扫描一张表。这些估计假设顶点已编号,数组访问为常数时间;对表排序或使用哈希会改变这种权衡。
编码记录了什么,没有记录什么
设一个数据文件只给出边对 与 。它没有说明顶点集是 ,还是另有孤立顶点 。这两种理解给出不同构的图。完整的编码必须同时给出顶点和边。若顶点已编号为 ,列出这些编号或给出整数 就补足了缺少的信息。在声称为简单图的边表中重复一条边,并不会产生另一条边;程序要么拒绝重复项,要么明确把输入当作集合处理。下面的结果都假设给出的是简单图的有效编码。
矩阵使这种区别特别明显。孤立顶点会增加一整行零和一整列零。第 行中 的个数等于 ,而全部元素之和为 :每条边在两个对称位置各产生一个元素。因此只检查对角线以上的位置就能重建边集。但这并不表示矩阵本身与顶点次序无关。换一个次序,会改变哪一行描述哪个顶点,尽管底层的图没有改变。
例题 8.1.2
(孤立顶点也是图的一部分)
设 的顶点集为 ,边为 。按这个次序,其矩阵为
各行之和为 ,总和为 。第四行说明顶点 是孤立顶点。若顶点集改为 ,同样两对边就描述一条三顶点路径,其矩阵是左上角的 子块。两图不同构,因为大小不同的顶点集之间不存在双射。
子图:选择顶点与选择边
比较两张完整的图之前,先分清“取出图的一部分”有哪些不同含义。
定义 8.1.3
(子图、生成子图与诱导子图)
的一个子图是图 ,其中 ,且
这里 表示 的所有二元素子集组成的集合。因此,保留下来的每条边,其两个端点都必须在 内;但即使两个端点都保留,也可以删去它们之间的边。如果 ,这个子图称为生成子图:所有原顶点都保留,包括删边以后变成孤立顶点的那些顶点。由 决定的诱导子图记作 ,它保留原图中两个端点都在 内的每一条边:
因此,选定 后,诱导子图就唯一确定;一般子图在同一个顶点集上还可以少保留一些边。删去顶点 ,要连同所有与它关联的边一起删去,得到 。删去一条边则只移除该边,不删除任何顶点。两种操作不能混淆,即使画图时常把删边后留下的孤立顶点漏画了。
从邻接矩阵看,形成 就是同时保留由 索引的行与列,且保留它们原来的相对次序。所得矩阵称为主子矩阵。若要形成顶点集为 的一般子图,还可以把某些对称位置上的一对 改为 。只删一行而不删相应的列,并不表示从图中删除一个顶点。
例题 8.1.4
(一条路径可以是子图,却不是诱导子图)
设 的顶点为 ,边为 。对 , 是三角形,因为边 都必须保留。顶点集同为 、但只含边 的图是子图,却不是由 诱导的子图。如果保留全部四个原顶点、边仍只取 ,得到的则是生成子图;顶点 仍然存在,并且孤立。最后,从 删去顶点 ,留下的是顶点 和唯一的边 ,并不是含边 的路径。
这种区别会影响性质能否传给子图。无圈图的每个子图仍无圈,因为子图中的圈必然也是原图中的圈。二部图的每个子图仍是二部图:把原来的两个独立顶点集分别与保留的顶点集取交;删边不会在同一侧内引入新边。但连通性不同。在路径 中, 诱导的子图只有两个孤立顶点。原来连接保留顶点的路径,可能必须经过一个已经删去的顶点。
最短路径内部没有可用的弦
定义 8.1.5
(诱导路径与弦)
路径 的顶点互异,并含边 。如果这些边恰好是 的全部边,就称它为诱导路径。额外出现的边 ,其中 ,称为这条路径的弦。
一串顶点构成路径,并不代表周围的图中没有这些弦;上面三角形中的两边路径就是例子。
定理 8.1.6
(无权图的最短路径必为诱导路径)
设有限简单图中的 之间存在路径。任意一条从 到 、边数最少的路径都是诱导路径。反过来不一定成立。
证明
(弦会缩短路径)
设 是最短路径。如果有弦 ,其中 ,就用这一条边取代路径段 。新序列仍是路径:其顶点只是原来互异顶点的一个子序列。新路径的长度为 ,与最短性矛盾。因此弦不存在。长度为零或一时,本来就没有可能的弦,结论同样成立。
证明透视
最短路径论证改变了什么
两个端点始终固定,优化目标只是边数。一条弦至少省去一条边,并且不改变端点。但还可能有一条更短路线经过原路径以外的顶点;诱导路径的定义完全不检查那些顶点。因此证明只得到一个方向,不能反推。加权最短路径也不能直接套用同一论证:一条弦的权重可能比它取代的整段路径还大。
例题 8.1.7
(诱导路径不一定最短)
考虑五圈,边为 。路径 是诱导路径,因为这四个顶点之间只有 三条边。但它并不是从 到 的最短路径: 只有两条边,而原路径有三条。更短路线使用了顶点 ;判断原路径是否诱导时,并没有检查这个顶点。相比之下,三角形中的两边路线连诱导性都不满足,因为它的两个端点本来就相邻。
同构保留边与非边
定义 8.1.8
(同构与自同构)
从 到 的同构是双射 ,并且对任意不同的顶点 ,
两个方向都必要:边与非边都要保留。图到自身的同构称为自同构。空图通过空双射与自身同构,但不与有顶点的图同构。
用矩阵等式描述重新标号
定理 8.1.9
(置换矩阵描述同构)
设 的有序顶点分别为 和 ,邻接矩阵为 。两图同构当且仅当存在置换矩阵 使 。
证明
(计算 的元素)
为看清约定,令 的第 列为标准基向量 ,则 。因此等式恰好表示映射 同时保留相邻与不相邻。反过来,从 到 的任意同构都给出一个这样的置换。同构的逆仍是同构,故所述等价成立。特别地,改变同一图的顶点次序时,矩阵要按相同置换同时改变行和列,不能独立随意置换行与列。
定义 8.1.10
(同构不变量)
被每个同构保留的性质称为不变量。不变量取值不同可证明不同构;取值相同只说明这项检验没有区分两图。要证明同构,应给出双射并检验相邻关系的等价性,而非只列出相同的不变量。
例如,同构把每个顶点的邻居双射到其像的邻居。因此度、排序后的度序列、顶点数、边数,以及连通分支的数量和大小均被保留。路径映成路径,这说明了关于分支的结论;再使用逆映射,就知连通分支一一对应。
反例模式
度序列不能确定图
六圈 与不交并 都有六个顶点、六条边,度序列都是 。但 连通,两个三角形不连通,故不存在同构。图形可以帮助发现这一差别,而连通性给出了与画法无关的证明。
检验给出的对应
同构之所以是有用的证书,是因为读者可以直接检验它。先检查给出的像都属于目标顶点集,并且每个目标顶点恰好出现一次。然后检查源图每一对不同顶点:比较它的相邻位与其像的相邻位。若全部一致,定义成立;若有一对不一致,这一对就是映射失败的简短而明确的理由。有两个邻接矩阵时,检查双射之后,这样检验给定映射需要 次顶点对比较;除输入外,存储映射及其逆需要 空间。这是验证的代价,而不是寻找合适映射的界。逐个检验全部 个双射是一个有限的判定方法,但单凭这一点并不能给出一般的高效算法。
若两图都以有效的边表给出,还有另一种检验。验证双射性,映射源图的每条边,再把所得集合与目标边集比较。两者相等就保证边与非边都被保留:不在像中的目标边,或在目标中不存在的映射顶点对,都表明失败。在双射下,不同的源边有不同的像。若已知源图与目标图边数相同,只需检查每条映射后的源边都是目标边,因为同样大小的有限边集之间的单射必为满射。没有边数相等这一条件,这个捷径就不成立。所需时间取决于如何实现对目标边集的成员查询;不能仅因为有邻接表就保证常数时间查询。
例题 8.1.11
(保留边的双射仍可能失败)
设 的顶点为 、边为 , 的顶点为 、边为 。双射 、、 把 的每条边都映成 的边,却把非边 映成了边 ,所以它不是同构。事实上两图分别有两条和三条边,因此任何其他双射也不可能是同构。这个例子说明了定义为什么使用等价,而不只是正向蕴含。
画法不能挽救一个失败的证书。交叉点若没有列为顶点,就不会自动成为顶点;反过来,把两个顶点画得很近也不会使它们相邻。每个声称的对应都必须对照给定的顶点集和边集来检验,而不是对照外观上的相似。一张画得很复杂的连通图,与同一张图不带交叉的画法,在恒等映射下仍有完全相同的相邻数据。
补图:恰好记录缺少的边
定义 8.1.12
(补图)
简单图 的补图 保留同一顶点集 ,边集则为 。对于每一对不同顶点, 与 中恰有一个包含连接它们的边。补图不会引入自环。
因此,若固定顶点次序后 的邻接矩阵为 ,则
其中 是每个元素均为一的 矩阵, 是单位矩阵。非对角位置上的 与 互换;对角位置则为 。若只写成 ,便会错误地在每个顶点加入自环。另外,取两次补图会回到 ,并且 ,因为 的 个可能邻居被两张图分配完毕。
一个双射是从 到 的同构,当且仅当同一个双射也是从 到 的同构。理由是:两个不同顶点在补图中相邻,恰好表示它们在原图中不相邻;对原来相邻关系的等价式两边同时取否定,就得到补图的等价式。再取一次补图,可得反方向。同样,取诱导子图与取补图可以交换次序:
两边的顶点集都是 ; 中的一对不同顶点在任一边构成边,当且仅当它们在 中不相邻。注意左边的补图是在顶点集 上取的,不是在更大的 上取的。
定理 8.1.13
(不连通图的补图必连通)
设有限简单图 有 个顶点,而且不连通。那么 中任意两个不同顶点之间,都有长度至多为二的路径。特别地, 连通。
证明
(不同分支或同一分支)
若 属于 的不同连通分支,它们在 中不相邻,因而在 中直接相邻。若它们属于同一分支,则因 不连通,可以在另一个分支选择顶点 。边 在 中都不存在,因此 是 中的路径;三个顶点互异。这两种情况穷尽了所有不同顶点对。
所以,当 时, 与 至少有一个连通,但不一定恰好一个连通。定理的前提是原图不连通;它的等价逆否命题是“补图不连通,则原图连通”。
反例模式
原图与补图可以同时连通
四顶点路径的边为 ,补图的边为 。这些边构成路径 ,所以两图均连通。映射 、、、 甚至给出了原图到补图的同构:原来的三条边恰好映为 。但不能由此认为取补图总保留连通性。至少有两个顶点的完全图是连通的,其补图却完全没有边。
关于子图与补图的练习
快速检查
(图的顶点为 ,边为 。判断路径 是否诱导、是否是其两个端点之间的最短路径,并与 比较。)
解答 · 答案
在 上只有边 ,所以第一条路径是诱导的。由于 不是边,不存在一边路线;给定的两边路径便是最短的。第二条确实也是路径,但它有弦 ,把 换成 即可缩短。因此第二条既非诱导,也非最短。
快速检查
(设 由 上的三角形和孤立顶点 组成。求 ,并说明它为何连通,以及两个顶点间的最大距离为何恰为二。)
解答 · 答案
缺少的顶点对为 ,所以补图是以 为中心的星形图。每片叶都与中心相邻;不同的两片叶经中心相连,但并不直接相邻,故距离恰为二。这也说明定理中的“至多二”一般不能改成“至多一”。相反,如果不连通的 没有任何边,其补图就是完全图,不同顶点之间的距离为一。
快速检查
(设 是同构,。证明把 限制在 上,得到同构 。“诱导”这个条件为什么重要?)
解答 · 答案
限制后的映射是从 到 的双射。 中的一对顶点在 中构成边,当且仅当它们在 中构成边,当且仅当其像在 中构成边,也当且仅当其像在 中构成边。因此边与非边都保留。如果任意而独立地选取两个子图,结论就可能失败:即使原同构是三角形上的恒等映射,也不能把两边生成路径同构地映到完整三角形。诱导限制保留了所有顶点对原有的相邻信息,原来的等价式才得以直接沿用。
矩阵幂计数游走
定理 8.1.14
(矩阵幂编码游走数)
对每个整数 , 等于从 到 长度为 的游走数。游走可以重复顶点和边。这里 ,故长度为零的游走停在起点。
证明
(对游走长度作归纳)
当 时,单位矩阵恰好给出这些游走; 时结论就是邻接的定义。假设结论对 成立。矩阵乘法给出 。第 项统计倒数第二个顶点为 的游走:若边 存在,就将它接在一条长度为 的游走后面。这些类别互不相交,且穷尽所有长度为 的游走,由归纳法得证。 时没有下标需要检验。
例如, 时 是共同邻居的数目,而 。后者统计走出去再走回的游走,即使简单图没有自环。矩阵元素为正表示存在指定长度的游走,不一定存在同样长度的简单路径。
例题
例题 8.1.15
(给出重新标号)
设 的顶点集为 、边为 ; 的顶点集为 、边为 。映射 、、、 将上述五条边依次映为 。它是双射。两图各恰好列出五条边,五条不同的边像便穷尽 ;因此非边也保留,故它是同构。
例题 8.1.16
(从矩阵平方读出游走)
对路径 ,令 ,则 。其中 计数 与 ,而 计数 。前两条游走重复顶点;按通常简单圈的约定,这些游走都不是圈。
重新标号与游走数
设 对某个置换矩阵满足 。由于 ,反复相乘得到对每个 都有 。也可以直接看出这一等式:把游走中的每个顶点改名,保留其相继的边和长度,再用逆改名把构造反过来。特别地,对应顶点在每个固定长度上的闭游走数相同;把对角元素相加得到 。因此这些量可以否定一个所谓的同构。它们仍然只是不变量,一组相同的不变量本身并不是一个给出的双射。
三角形有一个有用的特殊情形。在简单图中,长度为三的闭游走有三个不同顶点:相邻两步重复同一顶点需要自环,而两步后回到起点会使第三步成为不允许的自环。因此每条这样的游走都沿一个三角形走一圈,而每个三角形共贡献六条游走:三个顶点各作起点,两个方向各一条。于是 等于三角形的个数。这个除法依赖于简单无向图的约定;若允许自环或重边,就需要重新论证。
常见错误
常见错误
(把零对角线读作“没有边”)
对角线为零只说明没有自环,并不说明没有边,因为边记录在对角线以外。
常见错误
(把任何零一矩阵都读作无向图)
对称且对角线为零的零一矩阵表示无向简单图;不对称的零一矩阵只有在另外选定约定之后,才表示有向的相邻关系。
常见错误
(只置换行而不置换列)
交换两行而不交换相应的两列,可能破坏对称性,也不是给顶点改名的矩阵运算。改变标号必须同时作用于每条边两端的名称。
练习
快速检查
(顶点为 的图有边 。按此次序写出其邻接矩阵和包含每个顶点的邻接表,并给出到路径 的双射。)
解答 · 答案
矩阵的四行为 、、、。邻接表为 、、、。双射 、、、 将列出的三条边恰好映为目标的三条边,因此也保留非边。
快速检查
(六圈与两个互不相交的三角形是否同构?说明度相同为何不足,并给出能区分它们的不变量。)
解答 · 答案
不同构。两图各顶点的度都为二,但前者只有一个连通分支,后者有两个。同构必须保留连通分支,因此度序列相同并不足够。
快速检查
(对简单图证明对角元素 是包含 的三角形个数的两倍。为什么这不表示所有长度为三的游走都是三角形?)
解答 · 答案
以 为起点的长度三闭游走形如 。由于图是简单图,相邻顶点互不相同,闭合的那条边迫使 ;同时 。因此三个顶点互异并组成三角形。每个包含 的三角形恰好给出两条这样的游走,每个方向一条。矩阵幂定理统计的正是它们。不闭合的长度三游走可以折返,例如单条边上的 ,它不是三角形。