二分图 and 网络流

发表于 更新于

一些简单的关于图论的定义和胡扯…

总览

二分图最大匹配

  • \(O(n m)\)
  • Dinic: \(O(m \sqrt(n))\)

二分图最大带权匹配

  • KM算法 \(O(N^3)\)

定义

  • 最大独立集：在图里选最多的点，使得不存在两个选了的点之间有边。
  • 最小点覆盖：在图里选最少的点，使得每个边连接的两个点至少一个点被选。
  • 最长反链：点集 G 中一个极大的子集 W ， 使得 W 中的点互不可到达。
  • 传递闭包：定义有向图 \(G\) 的传递闭包为 \(\text{A[i, j]} = \text{[点 i 和 点 j 有通路]}\)

定理

  • \(\text{最长反链} = \text{最小链覆盖}\) （dilworth 定理）
  • \(\text{二分图最小点覆盖} = \text{最大匹配}\)
  • \(\text{最小点覆盖} + \text{最大独立集} = \text{点数}\),最小覆盖集 与 最大独立集 互为补集, 其并集为点集
  • Hall定理： 设一个二分图的左右部分分别为 X、Y, 且 |X| = |Y|
  • 矩阵树定理证明：有向图矩阵树定理的一个简单组合证明

小问题

  • 求 DAG 最小链覆盖（最长反链）：传递闭包 + 拆点二分图匹配

栗题

4.2（LOJ）

给出一个保证左部满匹配的二分图，保证左部每个点的度数不超过2，边有边权。 支持： - 修改边权 - 查询最大带权匹配 (强制保证任意时刻左侧满匹配)

对左侧点分类： - 度数为 1 ：这条边必须成为匹配边，可直接删除这个点和对应的右边点 - 度数为 2 ：左侧点 u 可直接删掉，在右侧对应的两个点之间直接连两条有向边，给这条边定向，只想哪个点就相当与选哪个点与点 u 相连的边。 - 不难发现这样形成的一张图应该是，若干个 树 和 基环树 组成的森林。根据查询给边定向，其中要求一个点入度数最多为一。树仅需选择一个边定向，在同一个树上的其他边都能被强制定向。对于基环树，环上边需要决定是顺时针还是逆时针，环外的边要指出环