图论的

· · 个人记录

二分图

二分图的最小顶点覆盖

选一个点等于覆盖所有该点的连边

将图作最大匹配。对于右侧的每一个非匹配点沿着→(非匹配边→匹配边)→的方式遍历,标记经过的点。

令S={左侧的标记点+右侧的未标记点},显然|S|正是最大匹配数。考虑每一类边关于S的覆盖情况:

  1. 左边被标记,右边被标记。(左S)
  2. 左边被标记,右边未标记。(左右S)
  3. 左边未标记,右边被标记。(不存在)
  4. 左边未标记,右边未标记。(不存在)

故 S是一个顶点覆盖集。显然任一个顶点覆盖集大小≥最大匹配(考虑匹配边),故 S时一个最小的顶点覆盖。

二分图的最大独立集

对于任一个顶点覆盖集 S,由于 S覆盖了所有的边,那么 I=V-S中任一个点都被孤立,即 I是一个独立集。 进一步,最大的独立集=V-最小顶点覆盖。

弦图与区间图

见另一篇blog

一般图

最大权闭合子图

闭合子图:给定一个有向图,从中选择一些点组成一个点集V。 对于V中任意一个点,其后续节点都仍然在V中。

转化网络:首先建立源点s和汇点t,将源点s与所有权值为正的点相连,容量为权值; 将所有权值为负的点与汇点t相连,容量为权值的绝对值; 权值为0的点不做处理; 同时将原来的边容量设置为无穷大。

简单割:割(S,T)中每一条割边都与s或者t关联,这样的割叫做简单割。显然任意(u,v)属于简单割(S,T)满足C(u,v)!=inf,即不包含原有的图上的边。

推论:

  1. 最小割是简单割。
    证明:
    不与ST关联的边容量为inf,最小割容量不可能为inf,所以最小割中只包含与S或T关联的边。得证。

  2. 简单割与原图中的闭合子图一一对应(子图V和源点s构成S集,其余点和汇点t构成T集。)
    证明:
    若闭合子图子图对应的个(S,T)不是简单割,则存在边(x,y),x∈S,y∈T且c(x,y)=inf, 即y不属于S,矛盾。 任意c(u,v)=inf都不在简单割C(S,T)中,因此S除s外所有点向外扩展,必然不会经过割边; 而最终扩展出的整个图正是一个闭合子图。 得证。

  3. 最大权闭合子图=所有正点权值之和-最小割(最大流)
    证明:
    由简单割概念,C(S,T)=S中负权点的权值绝对值之和+T中正权点的权值之和。
    闭合子图的权值W=S中所有正权点的权值之和-S中负权点的权值绝对值之和。
    (S、T的权值认为为0)
    则C(S,T)+W=所有正权值之和。
    因为C(S,T)与W一一对应,故C最小时,W最大。
    得证。

练习题 P3410 P2762

最小不相交路径覆盖

定义 在一个DAG中,找出最少的路径使得路径 不重复 地经过了所有点。特别地,单独一个点也可以被称为一条路径。

算法: 把原图上的每个点拆为A,B两点,若存在边x\rightarrow y,则新图中建边A_x\rightarrow B_y。将新图视为二分图,则原图的最小不相交路径覆盖=原图的节点数-新图的最大匹配数。

证明:初态下,共有n独立的路径;通过适当的方式将一些边(或者初态的点)连接起来,每连接一次,独立的路径数-1。由于路径上不能有公共边,故每个点最多被连两次。于是我们将每个点分为入点、出点两部分来分别表示被连的两种情况(由于有向图的路径必然方向一致,故一为入、一为出),连接的次数就是新图的最大匹配。

例题:P2764 最小路径覆盖问题 P2469 [SDOI2010]星际竞速

最小可相交路径覆盖 (最小链覆盖)

定义 在一个DAG中,找出最少的路径使得路径经过了所有点。特别地,单独一个点也可以被称为一条路径。

算法1:使用Floyd求出原图的传递闭包,转化为最小不相交路径覆盖。

证明:对于两条相交的路径,让一条“跳过”交点,就变为了不相交路径,这就是新图中的解的本质。故新图的最优解即为原图最优解。(请注意最后两个最优解含义)

算法2:转化为带下界的网络流(最小流)问题。见上下界网络流

update 2019/5/28 ,一道例题 NOI2015 小园丁与老司机

Dilworth定理

最小链覆盖数 = 最长反链长度。 证明参考, 对偶定理: 最长链长度 = 最小反链覆盖数。