Dag中的完整路径数量问题
2021-04-27
tags: 有向无环图, DAG, 路径, 复杂度
前两天李春淼在论文中遇到一个问题与我讨论，是关于其在程序分析中遍历执行流的复杂度问题。原本的直觉说这个复杂度应该是多项式的，最多可能是二次，但是事后又想了一下并没有这么简单，只是当时举得例子过于简单。在搜索了图论的一些文献之后并没有找到想要的结论，于是自己上手分析一下。
1. 定义：
- 源点（Source）
- 有向图（Directed Graph）中入度为0的点称为源点
- 汇点（Destination）
- 有向图中出度为0的点称为汇点
- 完整路径（Complete Path）
- 有向图中从源点到汇点的一条单向路径称为一条完整路径
- DAG完整路径数量上界问题
- 设\(\mathcal{G} = \langle V, E \rangle\)是一个有向无环图（Directed Acyclic Graph， DAG），\(cp(\mathcal{G})\)为\(\mathcal{G}\)中包含的完整路径的数量，求\(\displaystyle \max_{\mathcal{G}} cp(\mathcal{G})\)的数量级
2. 分析
设\(\displaystyle f(\mathcal{G}) = \max_{\mathcal{G}} cp(\mathcal{G})\)，接下来分别分析求得\(sup(f(\mathcal{G}))\)与\(inf(\mathcal{G})\)，从而得到\(f(\mathcal{G})\)的数量级。
2.1. 分析\(inf(f(\mathcal{G}))\)
要分析\(f(\mathcal{G})\)的下界，可以构造一个具体的实例。
Example 1. 首先构造一个具有n个节点的有向完全图\(\mathcal{G}_c\)，并将其节点分别用整数1, 2, …, n标记，记作\(v_1, v_2, \dots, v_n\)。对于其每一条边\(e\)，\(e\)的方向为由编号小的点指向编号更大的点。
Lemma 2. \(\mathcal{G}_c\)是一个DAG
Proof. 如果\(\mathcal{G}_c\)中有环，则必然存在一条边从编号更大的点指向编号更小的点，与Example 1矛盾。 \(\Box\)
Theorem 3. \(cp(\mathcal{G}_c) = 2^{n - 2}\)
Proof. 根据Example 1，\(v_1\)和\(v_n\)分别是\(\mathcal{G}_c\)的源点和汇点，并且\(\mathcal{G}_c\)中不存在其他源点和其他汇点，因此\(cp(\mathcal{G}_c)\)就是\(v_1\)和\(v_n\)之间所有路径数量的总和。
可以按照路径长度分别计算路径数量，然后进行汇总。对于长度为\(k\)的路径，相当于在\(v_2, \dots, v_{n-1}\)中选取\(k-1\)个点并按顺序连接起来，因此数量为\(\displaystyle \begin{pmatrix}n-2\\k-1\end{pmatrix}\)。
则:
\[\displaystyle cp(\mathcal{G}_c) = \sum_{k=1}^{n-1}\begin{pmatrix}n-2\\k-1\end{pmatrix} = \sum_{i=0}^{n-2}\begin{pmatrix}n-2\\i\end{pmatrix} = 2^{n-2}\].\(\Box\)
2.2. 分析\(sup(f(\mathcal{G}))\)
对于\(\mathcal{G}\)中的任意一条完整路径\(p\)，都可以将其写为路径上点的顺序排列\(v_1, v_2, \dots, v_k\)，记作\([p]\)。
Lemma 4. 设\(p,q\)为\(\mathcal{G}\)中的两条完整路径，则\([p]\)和\([q]\)中不存在两个顺序相反的顶点对。即，\(\forall v_i, v_j \in [p], v_i, v_j \in [q]\)，\(v_i\)和\(v_j\)在\([p]\)和\([q]\)中出现的顺序相同。
Proof. 反证，若Lemma 4不成立，则\(\mathcal{G}\)中有环：\(v_i \rightsquigarrow v_j \rightsquigarrow v_i\)。 \(\Box\)
Lemma 5. \(\mathcal{G}\)中不存在两条长度相同且顶点相同的不同的完整路径。
Proof. 设\(p\)和\(q\)是\(\mathcal{G}\)中两条不同的完整路径，且其包含的顶点一致，路径长度一致。那么\([p]\)和\([q]\)中一定包含两个顺序相反的顶点对，与Lemma 4矛盾。 \(\Box\)
Theorem 6. \(f(\mathcal{G}) \le 2^n - 1\)
Proof. 根据Lemma 5，\(\mathcal{G}\)中的所有的相同长度的完整路径所包含的顶点集合必然两两不同。则：
\[\displaystyle f(\mathcal{G}) = \sum_{k=0}^{n-1} 长度为k的路径长度数量 \le \sum_{k=0}^{n-1} \begin{pmatrix}n\\k+1\end{pmatrix} = \sum_{i=1}^{n}\begin{pmatrix}n\\i\end{pmatrix} = 2^n-1\].\(\Box\)
2.3. 求\(f(\mathcal{G})\)
根据Theorem 3，\(f(\mathcal{G}) = \Omega(2^n)\)；而根据Theorem 6，\(f(\mathcal{G}) = O(2^n)\)。则：\(f(\mathcal{G}) = \Theta(2^n)\)
事实上，我们是可以直接求出路径数量的最大值的。分析如下：
Lemma 7. 如果一个DAG中的完整路径数量是最多的，那么其中的任意两点之间都必然有一条边。
Proof. 将一个DAG按照拓扑序排列，如果两个顶点之间没有边，那么可以根据拓扑序在这两个顶点之间添加一条新的有向边。因为这条边是符合拓扑序的，因此添加这条边不会产生环。且新的DAG比原DAG增加了至少一条完整路径，与原“DAG中的完整路径数量是最多的”矛盾。 \(\Box\)
Theorem 8. 对于任意具有\(n(n \ge 2)\)个顶点的DAG，其所包含的完整路径数量最多为\(2^{n-2}\)条。
Proof. 首先，对于一个\(n\ge2\)的DAG，其中至少包含一个源点和一个汇点，否则会出现环。再根据Lemma 7，当DAG中的路径数量达到最大值的时候，这个源点和汇点必然不是同一个点，否则存在不和其他点相连的孤立点。那么所有可能的路径对应的顶点序列，其去除首尾之后对应的序列集合只能是剩余\(n-2\)个点的所有排列或部分排列集合的子集。又根据Lemma 5，将所有可能的路径按照长度进行汇总，得到：
\[\displaystyle \max_{\mathcal{G}中的边}cp(\mathcal{G}) = \sum_{k=1}^{n-1} 长度为k的路径长度数量 \le \sum_{k=1}^{n-1} \begin{pmatrix}n-2\\k-1\end{pmatrix} = \sum_{i=0}^{n-2}\begin{pmatrix}n-2\\i\end{pmatrix} = 2^{n-2}\]而Example 1中的情况恰好取得这个最大值。 \(\Box\)
3. 数值验证
【未完待续】