2020-2021:teams:i_dont_know_png:potassium:lgv_lemma

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:potassium:lgv_lemma [2020/05/15 04:41]
potassium 创建
+++ 2020-2021:teams:i_dont_know_png:potassium:lgv_lemma [2020/05/22 20:09] (当前版本)
potassium fix typos
@@ 行 1: / 行 1: @@
-.
+====== LGV Lemma ======
+更完整的定义见[[https://oi-wiki.org/graph/lgv/|OI-wiki]]，这里给出一个应用较多的狭义定义（即 $\omega(P)=1$ 的情况）。
+设起始点集合为 $A=\{a_1,a_2,\ldots,a_n\}$ ，终止点集合为 $B=\{b_1,b_2,\ldots,b_n\}$ ，在一个起止点有唯一确定排列路径集的 DAG 上， $A\rightarrow B$ 的不相交路径集 $S$ 的个数可以用行列式 $\det(M)$ 表示，其中矩阵 $M$ 为
+$${\begin{pmatrix}e(a_{1},b_{1})&e(a_{1},b_{2})&\cdots &e(a_{1},b_{n})\\e(a_{2},b_{1})&e(a_{2},b_{2})&\cdots &e(a_{2},b_{n})\\\vdots &\vdots &\ddots &\vdots \\e(a_{n},b_{1})&e(a_{n},b_{2})&\cdots &e(a_{n},b_{n})\end{pmatrix}}$$
+===== 证明 =====
+[[https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma%5D(https://en.wikipedia.org/wiki/Lindström–Gessel–Viennot_lemma)|wikipedia]]
+===== 感性理解 =====
+我们以 $n=2$ 的情况为例：
+$$\det(M)=e(a_1,b_1)e(a_2,b_2)-e(a_1,b_2)e(a_2,b_1)$$
+即，不相交路径集的个数等于所有路径集个数减去交换终点后的所有路径集个数。
+设交换终点前，有一相交路径集 $S$ ，设两路径最后的交点位置为 $p$ ，交换终点前， $p$ 到两终点的路径分别为 $p\rightarrow b_1$ 和 $p\rightarrow b_2$ ，则存在交换终点后的路径，分别为 $p\rightarrow b_2$ 和 $p\rightarrow b_1$ ，这对应一个交换终点后的路径集 $S'$ 。这说明，所有**交换终点后有交点的路径集**都是**交换终点前有交点的原路径集**的**一一映射**。同时，由于交换终点后的路径必然相交，即**交换终点后的路径集**是**交换终点前有交点的原路径集**的**一一映射**。
+{{ 2020-2021:teams:i_dont_know_png:potassium:lgv_lemma:pic_1.png?600 }}
+类似的，$n$ 更大的时候可以通过改变终点排列进行容斥，容斥的系数是逆序对个数。然后发现这很契合行列式的定义，于是它其实就是这个矩阵的行列式。同时，这也说明：只有起止点之间唯一确定排列的路径集才可以通过这个行列式进行简化运算。
+===== 应用 =====
+由于单纯容斥求和的复杂度是指数级，而求行列式可以用高斯消元 $O(n^3)$ 算出，因此可以使用此引理快速计算从起点集合到终点集合不相交路径个数。
+模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=5852|HDU5852]]

2020-2021/teams/i_dont_know_png/potassium/lgv_lemma.1589488905.txt.gz · 最后更改: 2020/05/15 04:41 由 potassium