LGV引理可以用于在DAG上求解不相交路徑方案數(shù)問題，下面我們簡單介紹一下。
一、簡介
LGV引理英文全稱是Lindstr?m–Gessel–Viennot lemma，可以用來處理有向無環(huán)圖上不相交路徑計數(shù)等問題。在此之前，大家要先了解圖論相關概念、矩陣、高斯消元求行列式等知識，能幫助大家更快理解和學習LGV引理。
LGV 引理僅適用于有向無環(huán)圖。
二、定義
ω(P) 表示P這條路徑上所有邊的邊權(quán)之積。（路徑計數(shù)時，可以將邊權(quán)都設為 1）（事實上，邊權(quán)可以為生成函數(shù)）
e(u,v)表示u到v的每一條路徑P上的ω(P)值之和，即
起點集合A，是有向無環(huán)圖點集的一個子集，大小為 n。
終點集合B，也是有向無環(huán)圖點集的一個子集，大小也為 n。
一組A→B的不相交路徑S：
是一條從
到
的路徑（σ(S)是一個排列），對于任何
，
和
沒有公共頂點。
N(σ)表示排列 σ 的逆序?qū)€數(shù)。
三、引理
其中
表示滿足上文要求的A→B的每一組不相交路徑 S。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習題和答疑，點擊了解：
一點編程也不會寫的：零基礎C語言學練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個編程真題的編程百練課程
信息學奧賽或C++選手的 必學C++課程
藍橋杯ACM、信息學奧賽的必學課程：算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導課程