本章节介绍 the minimum degree algorithm ，我个人将其翻译为最小度数算法。这里我们看如何用商图表示和转换消元图。

Computer Representation of Elimination Graphs

在这一章节汇总，我们研究如何在计算中表示和转换 elimination graphs 。

Explicit and Implicit Representations

让我们回顾一下消元的转换过程， 是从 消除节点 得到的图， 的相邻结构可以按照下面的方式获得：

1. 获得 中的相邻集合

2. 从相邻结构中移除节点 及其相邻列表

3. 对于任何一个节点 ， 在 中新的相邻列表通过合并两个子集得到

   

这里有两点需要注意，首先在相邻结构中用于存储 的空间可以在第二步之后重复使用；第二， 可能会比 占用更多的空间。

我们需要一种更加灵活的数据结构，用于存储在 elimination graphs 中结构的动态变化，比如之前提到的 adjacency linked list 。

Quotient Graph Model

让我们首先对下面的图进行消元，我们消除节点 到 之后得到右边的消元图。

设 ，在 implicit model 中，为了发现 ，我们必须先找到路径 。相似地， 也是因为存在路径 。注意这两个路径的长度分别为 4 和 5 。

我们有两个观测结果：

1. 如果未消元的节点间的 reachable path 的长度可以缩减，那么生成 reachable sets 的工作量会降低
2. 如果上面的这些路径可以缩减到极端的情况，那么我们就可以得到 explicit elimination graphs 。

我们寻求一个妥协，通过聚集连接的消除的节点，我们获得了一个新的图结构。举个例子，在上面的图中，在图 中存在两个连通组分，分别为 和 。通过形成两个 “supernodes”，我们获得下面的图

为了方便，我们设 和 来表示 中的这两个连通组分。在这个新图中，我们注意到存在路径

和

这两条路径的长度为 2，一般来说，如果采用这种策略，那么所有这样的路径的长度均会小于等于 2 。

这种策略的另一个优势可以 implemented in-place ，也就是说，这种方式不会占用比原始的图结构更多的空间。

为了正式描述这种消元方式，我们引入商图 (quotient graphs) 。设 是一个给定的图，设 是一种基于节点集合 的分隔形式

即 ,

我们定义 基于 的商图为图 ，其中当且仅当 时 。通常我们将这个图标记为 。

上面图 5.3.2 就是一个商图，其切分方式为

设 是一个给定的图，我们考虑消元的一个阶段，其中 是已经消除的节点集合。我们现在将其联系为一个基于 的商图，定义集合

对 的切分为

则可以唯一地定义商图

则可以视为对 中的聚集的连通集合得到的图，图 5.3.2 就是对 生成的商图。我们现在研究消元过程中的商图间的相关性。设 为给定图 消元的一系列节点，就像之前一样，设

对于每一个 ，子集 可以推导出分隔方式 ，而相应的商图为

用这种方式，我们可以得到一系列商图

下图就是上面例子中的这一系列商图。

下图的定理说明了上面商图其实就是 elimination graphs 的另一种表示。

定理 5.3.1：对于任意 ，我们有

证明略

确定在商图 的 reachable set 很直接，对于一个给定的节点 ，下面的算法会返回集合 ，注意这里应用了商图的 reachable path 长度最多为 2 的特性 。

实际上我们可以从商图中获得 elimination graph ，算法如下：

为了说明这个事先，我们考虑上例中从 生成 的过程（加粗表示商图，不加粗表示 elimination graph ），见下图

商图模型处于两种模型的中间

这三种模型的对应关系总结如下表

Implementation of the Quotient Graph Model

我们考虑由消除的节点集合 形成的商图 ，如果 ，我们采用符号 来表明在子图 中的包含 的连通组分。比如，在上面的例子中

换句话说，对于一个给定的连通组分 ，我们可以选择 中的任意一个节点 ，然后使用 来表示 ，即 。在我们讨论如何选择 之前，我们先证明商图模型可以 implemented in-place ，也就是说，只利用原始图的相邻结构的空间。

引理 5.3.2：设 , ，其中 是一个连通的子图，那么我们有

证明：因为 是一个连通子图，因此在 中至少有 条边，这些边在 中会计算两次，得证。

设 是节点序列， ，对于 ，我们有：

引理 5.3.3：设 ，那么

证明： 的相邻节点可以分为两类，属于 和 不属于 的节点。对于不属于 的节点，原图和商图均不受影响；对于属于 的节点，商图可能会合并成一个 “supernode”，因此数目会减少。因此得证 。

同时容易证明 ，如果 ，那么 无论 是否与其它节点进行合并，都不会影响 的相邻节点数目，因此 。如果 ，此时如果 是孤立的，那么 的相邻节点不变，如果 与其它节点进行合并，那么此时 的相邻节点数目要么不变，要么会减1。因此得证成立。

定理 5.3.4：

证明：考虑商图 和 ，如果 在子图 中是孤立的，那么显然 ；否则 会合并到 的某个连通组分中，形成 ，那么消元节点内的边数目不变，而根据 ，说明不属于 的节点的边的数目最多和之前相等，再加上减少的 的边，因此得到 ，因此在所有的情况中均存在 ，因此得证 。

这个定理说明通过消元生成的商图占用的空间不会超过原始的图，而且通过引理 5.3.2，对于 ，会富裕出 个位置。

设 是节点序列， 。我们选择 作为 的代表，其中

也就是说， 是 中最后消除的节点。

到此为止，我们描述了商图的数据结构以及如何表示 supernodes ，另一个重要的部分就是在消元的过程中商图的转换。下面的算法展现了如何从 中剔除节点 得到 。

让我们用图 5.3.3 中从 到 的过程为例，在 中 ，我们对 采用第一步，得到

和

因此，新的 ”supernode“ 为

新的拆分方式为

最后，在第三步我们更新相邻集合，得到

和

商图转换的效果可以通过一个例子来说明，采用图 5.3.3 中的例子，其中我们其相邻结构如图 5.3.6 所示。图 5.3.7 展示生成商图的一些步骤，在 到 的形成过程中，相邻结构没有改变。而从 到 的转换过程中，节点 和 聚合到了一起，因此在 中，节点 的新的相邻结构包含了原图中 的相邻结构。这里 的相邻列表的最后位置采用了一个链表（貌似是其相邻节点排好序，先放到 的相邻列表中第1个到倒数第二个位置，还有多的再放到其它节点的相邻列表中。此时最后一个位置的链接采用负数，这里就是 -2 。将相邻节点最后一个位置之后的一个位置设为0，表示终止位置，对应下图中划线的方块 ）。注意在 的相邻列表中，其相邻节点 在 中改为了 ，因此此时 已经变成了子集 的代表。

参考文献

1. George A, Liu J, Ng E. Computer solution of sparse linear systems[J]. Oak Ridge National Laboratory, 1994.