【水】几个网络流图论模型的记录

DAG相关

最小路径覆盖

定义：最少不重路径覆盖DAG

初始时每个点是独立的

之后每次加一条边把两个点连到一起 因为只能用一次，所以是个最大匹配

$$\text{最小路径覆盖=N-拆点后最大匹配}$$

最小链覆盖

定义：最少可重路径覆盖DAG

感性理解，某个流到了下面发现堵住了，也就是匹配过了

大概就是这样

由于顶点可以重复，这个时候小红红可以往外面跑

所以每个点反着往自己连边，从头开始匹配

最长反链

定义：DAG选最多的点不能互相到达

$$\text{Dilworth定理：最长反链=最小链覆盖}$$

二分图相关

$$\text{最小顶点覆盖=最大匹配=N-最大独立集}$$

懒得证了

总结

以上是生活随笔为你收集整理的【水】几个网络流图论模型的记录的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。