我加的概念

• 匹配：边集，任两边无公共vertex。
• 最大：含边数最多的匹配。
• 完美：若一个图的某匹配，所有点都是匹配点。
• 完美定是最大，并非每个图都有完美。

积和式模2和行列式

• $$Des(A)=|A|=\sum _{\pi \in S_n}(-1{)}^{ϵ(\pi )}\prod _{j=1}^n{A}_{j,\pi (j)}$$
• poly可计算
• $$Permanent(A)=|A|=\sum _{\pi \in S_n}\prod _{j=1}^n{A}_{j,\pi (j)}$$
• 同奇偶

积和式模2^k

Permanent:偶图(二部图)的带权完美匹配数目

• $$Permanent(A)=|A|=\sum _{\pi \in S_n}\prod _{j=1}^n{A}_{j,\pi (j)}$$
• $n$个点的有向图，$2n$个点的偶图
• 有向中，有向边的权重$W(j,k)=A_{j,k}$
  • Permanent(A)是有向图的什么呢？Cyclecover呀！
  • 置换可以分解为轮换的乘积，轮换就对应一个圈啊。
• 无向偶中，边$W(j,k^{\prime })=A_{j,k}$
  • Permanent(A)是无向偶图的什么呢？
  • 对应这个矩阵$\left(\begin{array}{cc}O& A\\ A^{\prime }& O\end{array}\right)$完美匹配哦

行列式：带符号的图覆盖于带符号的偶图完美匹配

• $$\pi =(1)(23)(456)=\left(\begin{array}{c}123456\\ 1^{\prime }{3}^{\prime }{2}^{\prime }{5}^{\prime }{6}^{\prime }{4}^{\prime }\end{array}\right)$$
• 圈覆盖怎么看符号？
  
• 偶图完美匹配怎么看符号？
  

Pfaffian：带符号的完美匹配

• $G$是边权重的，$2n$点的无向图
• $$Pfaffian(G)=\sum _{M是G的完配}(-1{)}^{M交叉数}(M权重)$$
• 交换匹配中两个边的匹配对象，交叉数目变1。
• 还有一个规则，太简单了，就是将7个9交换，然后奇偶性不变，这谁看不出来？
  

反对称矩阵的Pfaffian

• $M_{j,k}=-M_{k,j}$
• 奇数大小的反对称矩阵的$Pfaffian=0$
• 如果是偶数$2n$
  
• Pfaffian有类似高斯消元算法
• $Pf(A{)}^2=Det(A)$

一般图的pfaffian${\le }_T$平面图的完美匹配

• 下面这个图的完美匹配是3，带符号的话应该是1+1-1=1，这就是pfaffian，如何将这个归约到平面图的不带符号的完美匹配呢？
• 需要模拟交叉。
• 我们只需要保证插入的$C$函数在4个地方上有数值，其他为零就ok，想想为什么？
• 注意4个值里面需要有-1去模拟交叉
• 具体是啥见下一页哦
  

匹配门

• 完美匹配就是$[0,1,0,...0]$构成的张量网络

• 权重$w$的边，是在边的中点加上$[1,0,w]$
  
  

• 不信你可以算一下，过程如下。
  

• 实际已经归约了完成了。

用平面图模拟一般图

• 第四点实际上是实现不了的，

匹配门等式

• 一个$\#planarPM$生成的张量网络一定满足下面函数
• $e_{p_j}是单位向量，$只在$p_j$位置是1

用封闭性证明

• 第一个是说如果$P$和$Q$是满足等式，那么俩乘积也是的

Juxtaposition

• 如果$P$满足，$Q$满足，那么俩个乘积记为$F$
• $I(F,\alpha ,\beta )$表示作用在哪个函数啊
  • 那么$I(P,\alpha ,\beta )=0$,$I(Q,{\alpha }^{\prime },{\beta }^{\prime })=0$
    
• 结合上面的图，你就知道了为什么$I(F,\alpha {\alpha }^{\prime },\beta {\beta }^{\prime })$等于什么了

jumper

最后

以上就是拼搏人生为你收集整理的完美匹配我加的概念积和式模2和行列式积和式模2^kPermanent:偶图(二部图)的带权完美匹配数目行列式：带符号的图覆盖于带符号的偶图完美匹配Pfaffian：带符号的完美匹配反对称矩阵的Pfaffian一般图的pfaffian ≤ T \le_T 的全部内容，希望文章能够帮你解决完美匹配我加的概念积和式模2和行列式积和式模2^kPermanent:偶图(二部图)的带权完美匹配数目行列式：带符号的图覆盖于带符号的偶图完美匹配Pfaffian：带符号的完美匹配反对称矩阵的Pfaffian一般图的pfaffian ≤ T \le_T 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。