图的交叉理论与层次映射

最近在研究图的最小交叉理论，这边记录一下。

前提

通常对于一个有向无环图来说，层级分配完成之后，每个层级内的顶点的顺序至关重要。一个良好的层级之间的顶点顺序的分配，可以大大减少交叉边的产生。

层级可达性矩阵

首先需要已知的有向图的层级分配的可达性矩阵。矩阵的行和列都是图中所有的顶点，矩阵中的每个值都是表达两个顶点之间是否可达。例如对于如下的一个有向图：

图的交叉理论与层次映射

的层级可达性矩阵如下：

图的交叉理论与层次映射

矩阵的行和列代表了顶点{A,B,C,D,E,F,G,H,I}。图的层级结构由顶点和有向边组成，其中每个层级是图的顶点集的有序子集。这组层级是有序的，层级结构的每个边都从较低的级别指向较高的级别。对于上述的有向图来说，层级中的顺序为(A，B),(C,D,E,F)和(G,H,I)。并且只需要两个互连矩阵就能代表三层结构，如下图：

图的交叉理论与层次映射

名词说明

我们将边的跨度定义为通过从边终止的层级数中减去边起源的层级数得出的差值的大小。如果层次结构中的每个边的跨度均为1，则该层次结构称为“适当”；否则是不正确的。如果层次结构不正确，可以根据需要，通过引入其他顶点以使所有跨度等于1。

层次结构中的级别数在这里称为层次结构的长度，我们将任何级别中的最大顶点数称为层次结构的宽度。边的数量在此称为层次的度量。因此，上述的可达性矩阵代表的图的层次结构的长度为3，宽度为4，度量值为9。如果层次结构的长度为1，则可以说它是平坦的或单层的。

合适的层级结构和矩阵

如果层次结构合适，则绘制层次结构所需要的所有块互连矩阵信息（如果忽略交叉点）都在可达性矩阵的对角线的下方。与适当层级的定义类似，我们说如果每行至少包含一个1，则互连矩阵是适当的。我们说，如果可达性矩阵M是矩阵A’= A + I的有限次幂，则它是适当的。其中，A是位于主对角线的正下方，具有与M相同的块互连矩阵，而A中的所有其他条目均为0，其中I是一个单位矩阵。

算法：去除跨度超过1的边

首先我们需要一个已知层级的可达性矩阵M'，通常来说，这个矩阵不是一个适当的矩阵，我们需要根据以下的过程构建一个适当的矩阵。

首先从顶部开始依次访问各个层级，在检查级别φ_i时，依次检查这个级别的所有顶点{s₁ , s₂ , … , s_ki}。比如说在上述的有向无环图中，顶点被分为三个层级φ₁，φ₂，φ₃。层级φ₁对应的顶点就是{A,B}。当前正在访问的顶点称为s_j，其中s_j∈φ_i。这边使用A(s_j)表示顶点s_j的前置集合(所有可以到达顶点s_j的顶点的集合，包括s_j本身)。前置集合A(s_j)减去当前顶点s_j，在减去集合∪A{s_z????_z ∈ [A(s_j) ∩ φ_i+1]}，剩下的元素存入集合D_j。如果D_j为空，访问下一个顶点，否则表示出现了跨度大于1的边，需要在层级φ_i+1的最后面插入虚拟顶点s_μ，并且把s_μ的前置集合设置为D_j，并且把虚拟顶点s_μ加入到s_j的前置集合A(s_j) 。这样就相当于在跨度大于1的边上插入虚拟顶点，加入一个虚拟顶点，边的跨度就会减少一位。

比如在下图当中，就是在跨度大于1的边6 -> 1当中添加了一个虚拟顶点7，如果同一个层级出现具有除自己外相同的前置集合，需要合并两个虚拟顶点。

图的交叉理论与层次映射

整体流程图如下：

图的交叉理论与层次映射

直接矩阵实现

层次结构的绘图称为地图。图1的3级图可以完全由图3中所示的两个矩阵的乘积表示。如下图的公式所示
$T^{(o)} = N1N2\tag{1}$
被称为上述三个层级的“直接矩阵实现”。通常，层次结构的矩阵实现需要以下条件：

a): 有序的矩阵集，其数量等于地图中的层数。
b): 需要实现每个矩阵的有序的垂直和水平索引集。
c): 索引集排序的一致性，以便实现中的相邻矩阵可以合法地相乘在一起。
d): 保留层次结构元素之间指定的所有连接。

间接矩阵实现

在大多数应用中，在满足矩阵实现的条件c）的前提下，映射在各个级别上的顶点排序是可选的。这允许改变顺序以获得改进的可读性。在间接矩阵实现中，索引集的顺序可以与直接实现中出现的顺序不同。另外，只要保留原始顶点和路径，就可以引入与其他矩阵对应的其他级别。细节将在后面讨论。

两级地图

对于在行和列的索引集中没有公共元素的每个适当的m x n二进制矩阵N，考虑通过行和列的排列来最小化两级地图中的交叉数量，并开发了一种算法来实现最小化。下图很好的描述了两级Map中的互联矩阵。

图的交叉理论与层次映射

交叉统计公式

在地图上的交叉是指仅两条边缘的交点。N的交叉数用K(N)或K(p,q)表示，其中p和q分别代表N的行和列的有序索引集。通过检查图6(b)可以看出，对于N在图6(a)中，应该是K(N)=7。

现在假设一个m x n互连矩阵N具有一个有序的垂直索引集V，并且矩阵N的第i行表示为:
$V^{(i)}=v^{(i)}_1,v^{(i)}_2,v^{(i)}_3,...,v^{(i)}_n.\tag{2}$
然后，对于有序行对(V⁽ⁱ⁾,V^(j))产生的交叉数为：
$k(V^{(i)},V^{(j)})=\sum_{t=1}^{n-1}\sum_{p=t+1}^{n}v^{(j)}_tv^{(i)}_p\tag{3}$
通过对所有有序行对求和得出交叉总数K(N)：
$K(N)=\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}k(V^{(i)},V^{(j)})\tag{4}$
可以使用基于公式(4)的简单计数技术来确定矩阵中的交叉次数。对于矩阵N中每个1的条目，确定N中1的其他多少条目位于上方和右侧。将此称为所选条目的计数。所有计数的总和等于穿越次数。可以使用此技术来验证示例中出现的某些结果。

矩阵的置换族

如果对N的行和列的索引集之一或两者及其对应的行或列条目进行置换，则交叉计数可能会发生变化。该属性通常允许减少交叉，同时保留所有连接。为了给减少两级地图中的交叉次数的操作建立基础，引入了矩阵N的置换族。

置换矩阵说明

置换矩阵如果是在左边乘矩阵N，表示矩阵N以当前置换矩阵相对于单位矩阵的行移动情况移动。置换矩阵如果是在右边乘矩阵N，表示矩阵N以当前置换矩阵相对于单位矩阵的列移动情况移动。以行交换为例子，如下图所示：

图的交叉理论与层次映射

令N^’=P₁NP₂，其中P₁，P₂表示置换矩阵。我们说N^’ ∈ F(N)，其中F(N)称为矩阵N的置换族。显然，大小为m×n的矩阵N的置换族将具有m!×n!成员，对应于行和列索引的所有可能排列的集合。

最小交叉矩阵

因为适当的互连矩阵N的置换族是有限的，所以必然有一些N^* ∈ F(N)使得K(N^*)比F(N)的任何其他成员交叉数量都要小。这样的矩阵N^*被称为最小交叉矩阵。

如果N具有任何重复的行或列（行或列的值完全一样），则可以在寻求最小交叉矩阵之前消除此类重复项。在找到族F(N)中的最小交叉矩阵N^*时，可以通过消除行或列之间的所有重复值，这样就形成了矩阵N的一个压缩矩阵。一旦在压缩矩阵族中找到最小交叉矩阵，就可以将重复的行或列到浓缩矩阵中。上述方式是建立在如下的定理上的：

如果N^*是具有两个相同行（或列）的最小交叉矩阵，则重复行或者列在N^*中彼此相邻。否则在F(N)中一定存在另外的最小交叉矩阵，这个最小交叉矩阵具有两个相同的行（或列），并且相同的行（或列）彼此相邻。

为了证明上述的定理，我们先假设它是假的。即存在一个含有重复行的最小交叉矩阵，重复行之间互不相邻，并且F(N)中不存在重复行相邻的最小交叉矩阵。那么必然必须有一个最小交叉矩阵N *N^*，其中包含N的完整列的子矩阵，形式为N₁=(r B r)^T，其中r代表N的单行，B代表一个或多个其他行。假设另外两个矩阵N₂=(B r r)^T、N₃=(r r B)^T。那么根据假设，一定会有[K(N₂) - K(N₁)] > 0 && [K(N₃) - K(N₁)] > 0。那么这跟如下定理[K(N₂) - K(N₁)] + [K(N₃) - K(N₁)] = 0矛盾，得以证明。

假设矩阵 N₁=(r B r)^T、N₂=(B r r)^T、N₃=(r r B)^T，其中r代表单行，B代表其他的附件行，有[K(N₂) - K(N₁)] + [K(N₃) - K(N₁)] = 0

我们现在结合公式(3)(4)证明如上定理。

证明

对于矩阵N₁、N₂、N₃的交叉数量表示如下：
$K(N_1)=\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}k(A^{(i)},A^{(j)})$

$K(N_2)=\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}k(B^{(i)},B^{(j)})$

$K(N_3)=\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}k(C^{(i)},C^{(j)})$

由于(r B r)表示的矩阵的行位置改变，不能直接使用如上公式，但是转置矩阵(r B r)^T表示的行位置就是固定的，所以可以直接使用如上公式。也就是证明[K(N₂) - K(N₁)] + [K(N₃) - K(N₁)] = 0，我们只需要证明对于某两行(i,j)有如下关系：
$[k(B^{(i)},B^{(j)}) - k(A^{(i)},A^{(j)})] + [k(C^{(i)},C^{(j)}) - k(A^{(i)},A^{(j)})] = 0$
接下来我们使用N₁矩阵的描述符号a⁽ⁱ⁾来表达N₂、N₃：

对于N₁计算交叉数：
$k(A^{(i)},A^{(j)})=\sum_{t=1}^{n-1}\sum_{p=t+1}^{n}a^{(j)}_ta^{(i)}_p$
对于N₂计算交叉数：
$k(B^{(i)},B^{(j)})=\sum_{t=2}^{n-1}\sum_{p=t+1}^{n}a^{(j)}_ta^{(i)}_p + \sum_{t=2}^{n}a^{(j)}_ta^{(i)}_1$
对于N₃计算交叉数：
$k(C^{(i)},C^{(j)})=\sum_{t=1}^{n-2}\sum_{p=t+1}^{n-1}a^{(j)}_ta^{(i)}_p + \sum_{p=1}^{n-1}a^{(j)}_1a^{(i)}_p$
k(B⁽ⁱ⁾,B^(j)) - k(A⁽ⁱ⁾,A^(j)) ：
$[k(B^{(i)},B^{(j)}) - k(A^{(i)},A^{(j)})] = \sum_{t=2}^{n}a^{(j)}_ta^{(i)}_1 - \sum_{p=2}^{n}a^{(j)}_1a^{(i)}_p$
k(C⁽ⁱ⁾,C^(j)) - k(A⁽ⁱ⁾,A^(j)) ：
$[k(C^{(i)},C^{(j)}) - k(A^{(i)},A^{(j)})] = \sum_{p=1}^{n-1}a^{(j)}_1a^{(i)}_p - \sum_{t=1}^{n-1}a^{(j)}_ta^{(i)}_1$
两式相加 [k(B⁽ⁱ⁾,B^(j)) - k(A⁽ⁱ⁾,A^(j)) ] + [k(C⁽ⁱ⁾,C^(j)) - k(A⁽ⁱ⁾,A^(j))] = 0，即得证。

未完，待续。。。

图的交叉理论与层次映射