一些图论的定理

Part 1 公共部分

1.1 定义

  • 补图:
    • 无向图 GG 的补图中存在一条边 (x,y)(x,y) 当且仅当 GG 中不存在边 (x,y)(x,y)
    • 有向图 GG 的补图中存在一条边 xyx\to y 当且仅当 GG 中不存在边 xyx\to y
  • 子图:图中某些点和它们之间的边构成的新图;
  • 链覆盖:把图划分为若干条链的方案;
  • 反链:满足 x,yS\forall x,y\in Sxx 不能到达 yyyy 不能到达 xx 的点集 SS

1.2 定理

  • 最小链覆盖等于最长反链

    证明

    考虑不得不用两条链覆盖的结构,即一个分叉,显然不同分支上的点不能相互到达,那么最长反链中的每个点都可以代表一条链。

    Q.E.D.

  • 最长链等于最小反链覆盖

    证明

    对于一条链,链上的任意两点都不能被放到同一个反链中,所以最小反链覆盖不大于最长链。

    而对于两条链同一个位置的点,显然要么是同一个点,要么可以放到同一个反链中,所以最小反链覆盖等于最长链。

    Q.E.D.

  • 最小链覆盖等于点数减去拆点二分图的最大匹配

    证明

    二分图每匹配一对点,就相当于合并了两条链。

    Q.E.D.

Part 2 无向图

2.1 定义

  • 点的邻点:无向图中,vv 为点 uu 的邻点当且仅当它们有边直接相连,N(u)N(u)uu 的邻点集;
  • 团:无向图中满足点两两之间都有连边的点集;
  • 独立集:无向图中满足点两两之间没有连边的点集;
  • 直径:无向图中所有点对的最短路的最大值;
  • 点覆盖:无向图中所有边两端的点都至少有一个在其中的点集;

2.2 定理

  • 最大团等于补图的最大独立集

    证明

    原图的一个团内的点显然在补图上两两没有连边,所以原图的最大团在补图上一定是独立集。

    反过来即可证明补图的最大独立集在原图上一定是团。

    Q.E.D.

  • 无向图中 11 到其它点最短路的最大值 disdis 和图的直径 dd 满足 d2disd\lceil\frac{d}{2}\rceil\le dis \le d

    证明

    disddis\le d 显然,d2dis\lceil\frac{d}{2}\rceil\le dis​ 则是因为要先走到直径上,再走到直径的两个端点。

    Q.E.D.

2.3 二分图

2.3.1 定义

  • 二分图:无向图,满足可以分成左部点集 SS 和右部点集 TT 使得对于所有边 (u,v)(u,v) 都有 uS,vTu\in S,v\in TuT,vSu\in T,v\in S
  • 拆点二分图:把每个点拆成入点和出点,对于一条边 xyx\to y,在二分图中连一条从 xx 的出点到 yy 的入点的边;
  • kk-正则二分图:所有点的度数都为 kk二分图,易知 kk-正则二分图中 S=T|S|=|T|
  • 匹配:二分图中满足每个点度数都是 11 的子图;
  • 完美匹配:某一部中的点都在其中的匹配;

2.3.2 定理

  • 二分图最小点覆盖等于最大匹配:

    证明

    网络流,源点向每个左部点连流量为 11 的边,左部点向原图中有连边的右部点连流量为 \infin 的边,右部点向汇点连流量为 11​ 的边,最小割等于最大流。

    Q.E.D.

  • 二分图最大独立集等于点数减去最小点覆盖

    证明

    每条边都至少有一个端点在最小点覆盖中,那么把最小点覆盖中的点删掉后就是最大独立集了。

    Q.E.D.

  • kk-正则二分图可以被拆解为 kk 组完美匹配

    证明

    归纳:

    • 11-正则二分图显然满足;
    • kk-正则二分图满足 Hall 定理:AS\forall A\subseteq SAA 连出去的边集 EAEAN(A)N(A) 连出去的边集 EBEB 的子集,所以 EAEB|EA|\le |EB|,那么显然 kAkN(A)k|A|\le k|N(A)|AN(A)|A|\le |N(A)|
    • 由于 kk-二分图满足 S=T|S|=|T|,所以找到 kk-二分图的一组完美后去掉它可以转化为 (k1)(k-1)-正则二分图;

    Q.E.D.

2.3.3 Hall 定理

2.3.3.1 基本形式

对于左部点集为 SS,右部点集为 TT 的二分图 GG,其存在大小为 S|S| 的匹配的充要条件为:

  • AS,uAN(u)A\forall A\subseteq S,|\cup_{u\in A}N(u)|\ge|A|
证明

必要性显然,充分性考虑反证。

若满足了基本 Hall 定理但是不存在大小为 S|S| 的匹配,则一定存在一个 uSu\in S 满足 uu 不在最大匹配中,那么 vN(u)\forall v\in N(u)vv 一定在最大匹配中。

考虑匈牙利算法,对于每一个 vv,都不断找到它匹配的点 bvb_v,把 bvb_v 当作 uu 继续进行这个过程。设遍历过的 uu 的集合为 BB(包含刚开始的那个 uu),则若 uB\forall u\in BN(u)N(u) 中都不存在未被匹配的点,那么一定有 N(B)=B1|N(B)|=|B|-1,即只有刚开始的那个 uu 找不到和它匹配的点。与定理相悖。

Q.E.D.

2.3.3.2 拓展形式

对于左部点集为 SS,右部点集为 TT 的二分图 GG,其最大匹配为:

  • Smax(maxAS{AuAN(u)},0)|S|-\max\left(\max\limits_{A\subseteq S}\{|A|-|\cup_{u\in A}N(u)|\},0\right)

证明是简单的。

对于类似这样的二分网络流图,即源点向左边第 ii 个点连一条流量 aia_i 的边,左边第 ii 个点向右边第 jj 个点连一条流量 ci,jc_{i,j} 的边,右边第 ii 个点向汇点连一条流量 bib_{i} 的边:

它左边的所有点能满流(经过左边第 ii 个点的流量为 aia_i)当且仅当以下条件成立:

  • 设左边点集合为 SS,则 TS,uTauuN(T)min(bu,vTcv,u)\forall T\subseteq S,\sum\limits_{u\in T}a_u\le\sum\limits_{u\in N(T)}\min\left(b_u,\sum\limits_{v\in T} c_{v,u}\right)

即与 TT 相连的右边点集能承受的总流量要至少为 TT 中点输出的总流量。

证明

把基本形式证明中的匈牙利换成 EK(每次暴力找一条增广路)即可。

2.3.3.3 点和区间匹配形

数轴上有 nn 个点和 nn 个区间,一个点能匹配一个区间当且仅当这个点被这个区间包含。

存在大小为 nn 的匹配当且仅当:

  • 把值域离散化到 [1,n][1,n] 后,对于所有区间 [l,r][l,r],被 [l,r][l,r] 完全包含的区间个数 rl+1\le r-l+1
证明

考虑反证。

对于区间集合 SS,若 S>uS[lu,ru]|S|>|\cup_{u\in S} [l_u,r_u]|uS[lu,ru]\cup_{u\in S} [l_u,r_u] 可以分成若干个极长的不交且不相邻区间 [lb1,rb1],[lb2,rb2],,[lbk,rbk][lb_1,rb_1],[lb_2,rb_2],\dots,[lb_k,rb_k],则设 Ai={xxS,[lx,rx][lbi,rbi]}A_i=\{x|x\in S,[l_x,r_x]\subseteq [lb_i,rb_i]\}

注意到对于任意不同的 i,ji,j,必然有 AiAj=A_i\cap A_j=\emptyset,也就是说,对于任意不同的 i,ji,jAiAj=A_i\cap A_j=\emptyset(uAi[lu,ru])(uAj[lu,ru])=(\cup_{u\in A_i} [l_u,r_u])\cap(\cup_{u\in A_j} [l_u,r_u])=\emptyset

所以对于任意不同的 i,ji,jAiA_iAjA_j 独立。

那么必然存在某个 ii 满足 Ai>uAi[lu,ru]|A_i|>|\cup_{u\in A_i} [l_u,r_u]|,此时区间 uAi[lu,ru]\cup_{u\in A_i} [l_u,r_u] 不合法。

Q.E.D.

2.3.3.4 例题

2.4 生成树

2.4.1 定义

  • 生成树:无向图 GG 的一个边集,满足所有点都可以通过该边集联通且该边集的边数最小;
  • 最小生成树:边权和最小的生成树;
  • dfs 树:所有非树边两端的节点都互为祖孙关系的生成树;
  • 本源环:dfs 树中只有一条非树边的环;

2.4.2 定理

  • 所有最小生成树中每种边权的边的条数对应相等:

    证明

    考虑 Kruskal 算法的过程,显然边权小的边会选尽量多条。

    Q.E.D.

    例题:

  • 所有简单环都可以由任意生成树中的若干本源环异或得出:

    证明

    每个简单环都等价于环中非树边对应的本源环异或起来。

    Q.E.D.

    例题:

Part3 有向图

3.1 定义

  • 强连通子图:有向图的满足所有点对都能互相到达的子图;
  • SCC:有向图的极大强连通子图(即加入任意节点都不强连通的强连通子图);

3.2 偏序图

3.2.1 定义

  • 偏序图:有向图,满足若存在边 xyx\to y 和边 yzy\to z 则存在边 xzx\to z

3.2.2 定理

  • 偏序图上的独立集和反链等价

    证明

    考虑反证,设独立集中有两个点 x,yx,y 满足 xx 能到达 yy,由于偏序图满足 xx 能到达 yy 则存在边 xyx\to y,所以 x,yx,y​ 不能同时存在于独立集中。

    Q.E.D.

3.3 竞赛图

3.3.1 定义

  • 竞赛图:有向图,满足可以由点数相同的完全图定向得到;

3.3.2 定理

  • 竞赛图缩点(把每个 SCC 都缩成一个大点)后,满足拓扑序唯一且每个大点向它拓扑序中后面的所有大点都有连边

  • 把竞赛图中的点按出度从小到大排序后,每个 SCC 对应一个区间

    证明

    竞赛图缩点后,满足拓扑序唯一且每个大点向它拓扑序中后面的所有大点都有连边。

    也就是说对于每个 SCC,设拓扑序在它后面的 SCC 共有 mm 个点,则这个 SCC 中的每个点都会向这 mm 个点连一条边。

    而一个大小为 kk 的 SCC 中的点向这个 SCC 内部的其它点最多连 k1k-1 条边。

    所以把所有点按出度从小到大排序相当于把 SCC 按照拓扑序从后往前排序,每个 SCC 对应一个区间。

    Q.E.D.

  • 竞赛图中的 SCC 个数即为其中的点按出度 dud_u 从小到大排序后满足 j=1idj=(i2)\sum\limits_{j=1}^id_j=\binom{i}{2}ii 的个数

    证明

    根据上一条定理的证明,把所有点按出度从小到大排序后相当于把 SCC 按照拓扑序从后往前排序,每个 SCC 对应一个区间。

    那么 j=1idj=(i2)\sum\limits_{j=1}^id_j=\binom{i}{2} 的区间 [1,i][1,i] 与拓扑序的后缀构成双射。

    Q.E.D.

    题外话:不难发现 Sum of SCC 那题的结论和这个本质相同。

    例题: