エドモンズ行列

グラフ理論において、頂点集合を持つ均衡二部グラフのエドモンズ行列は 次のように定義される 。 ${\displaystyle A}$ ${\displaystyle G=(U,V,E)}$ ${\displaystyle U=\{u_{1},u_{2},\dots ,u_{n}\}}$ ${\displaystyle V=\{v_{1},v_{2},\dots ,v_{n}\}}$

${\displaystyle A_{ij}=\left\{{\begin{array}{ll}x_{ij}&(u_{i},v_{j})\in E\\0&(u_{i},v_{j})\notin E\end{array}}\right.}$

ここで、x _ijは不定値 である。二部グラフのエドモンズ行列の応用の一つは、グラフが完全マッチングを許容する場合、かつその場合において、x _ijの多項式det( A )が常にゼロではないということである。さらに、完全マッチングの数は多項式 det( A ) の単項式の数に等しく、のパーマネントにも等しい。さらに、の階数は の最大マッチングサイズに等しい。 ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle G}$

エドモンズ行列はジャック・エドモンズにちなんで名付けられました。タット行列は非二部グラフへの一般化です。

参考文献

• R. モトワニ、P. ラガヴァン (1995). ランダム化アルゴリズム. ケンブリッジ大学出版局. p. 167. ISBN 9780521474658。
• Allen B. Tucker (2004).コンピュータサイエンスハンドブック. CRC Press. p. 12.19. ISBN 1-58488-360-X。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Edmonds_matrix&oldid=1286053926"