Memo_Proposition - RogerRordo/ACM GitHub Wiki

#Propositions

• 树中任一点为源的最大距离点为A，A为源的最大距离点为B，则A、B为树的直径两点

• Lucas定理：

• 二分图中，最大匹配（边独立集）=最小点覆盖=点-最小边覆盖=点-最大点独立集；一般图中，最大匹配（边独立集）=点-最小边覆盖，求最小点覆盖和最大点独立集为NPC

• DAG A的最小路径覆盖=A点-二分图B的最大匹配，其中B是A的拆点二分图，A中(i,j)即B中(i左,j右)

• 最大权闭合图可以以此转化成最大流：在原图上，所有边为∞；S到正权点连容量为权值的边；负权点到T连容量为权值相反数的边

• 格雷码

• 差分表法