update: 2023/12/12 fixed pictures
update: 2025/02/12 fixed KaTeX
内容大纲#
|- 二分图
| |- 二分图的判定
| | |- 染色法
| | |- 不存在奇环（长为奇数的环）
| |- 二分图最大匹配（匈牙利算法）
| |- 二分图最小点覆盖（König定理二分：二分图中，最小点覆盖=最大匹配）
| |- 二分图最大独立集（二分图中，最大独立集=n-最小点覆盖）
| |- 例题（关于建边）
|- 图的联通
| |- 定义（只有概念，详细定义见下）
| | |- 无向图中的定义
| | | |- 连通图
| | | |- 子图
| | | |- 连通子图
| | | |- 连通分量（最大联通子图）
| | |- 有向图中的定义
| | | |- 强连通图
| | | |- 强连通子图
| | | |- 强连通分量
| | | |- k连通图（双连通图）
| | | |- 割点
| | | |- 桥
| | | |- 双连通分量
| | | |- 点双连通分量
| | | |- 边双连通分量
| |- 算法
| | |- 如何求强连通分量（SCC）= 如何缩点
| | | |- Kosaraju算法
| | | |- Tarjan算法
| | | |- Gabow算法（略）
| | |- 如何求桥/割点
| | | |- Tarjan算法（对还是它）
| | |- 如何求点/边双连通分量
| | | |- Tarjan算法（啊？）
学习内容——各种定义#
强连通/连通图#
在无向图中，任意两点都直接或间接连通，则称该图为 连通图(connected).
相应的，有向图中任意一点都存在路径到达任意另一点，则称该有向图为 强连通图(strong connected) .
子图#
在一个图 \(H\) 中， \(H\) 的所有边属于图 \(G\) 的所有边， \(H\) 的所有点属于图 \(G\) 的所有点，则称图 \(H\) 是图 \(G\) 的 子图(subgraph) .
连通分量#
无向图 \(G\) 的最大连通子图称为 \(G\) 的 连通分量(connected components) .
何为最大连通子图？这个子图是 \(G\) 的连通子图，将 \(G\) 的任何一个不在这张子图中的点加入这张子图后，该子图不再连通.
强连通分量（SCC）#
在任意有向图中能够实现强连通的部分我们称其为 强连通分量(Strongly connected component)，如下图，蓝色框内的分别是一个强连通分量.
如果把每个强连通分量收缩为单个顶点，得到的是一个 有向无环图(DAG)，于是我们可以在这个图的基础上进行拓扑排序，详见此例题.
而求这个强连通分量，我们可以使用两个算法：Kosaraju算法，Tarjan算法.
Kosaraju算法的流程如下：
- 重复寻找图 \(G\) 中未被讨论的点，从它开始DFS后序遍历图 \(G\) ，遍历到的点置为已讨论，用数组记录每个点到达的先后次序，直到找不到没有讨论的点.
- 将图 \(G\) 反向得到图 \(G^\prime\) ，重置所有点为未讨论.
- 一直从数组中未讨论的最后一个点出发，DFS后序遍历图 \(G^\prime\) ，DFS每完成一次，就说明找到了一个强连通分量，直到数组中没有未讨论的点.
这是一道使用Kosaraju算法的题目：Transitive Graph
接下来我们来说说Tarjan算法，这个算法相对于上个算法理解起来要困难些.
在Tarjan算法中，最为重要的两个数组是 dfn[] 和 low[] ， dfn[i] 记录的是编号为i的节点在DFS的整个过程的顺序，它会在第一次访问到
\(i\) 节点时更改，此后将不会变化；low[i] 表示的是 i 与其之后遍历到的节点所能到达的节点中 dfn 最小的 dfn ，在初始化时 dfn[i]=low[i] .
Tarjan算法在运行时会生成一棵搜索树，但是我们知道，图!=树，因为图中有一些边会使得“树”有环，自然，在生成树后，有一些边会直接指向已遍历的节点，没遍历的节点会在下一步当作自己的孩子进行遍历，而指向已遍历节点的边就是导致“树”有环的罪魁祸首.按照定义，当发现有这种边的存在时，需要更新当前节点的 low[] 值，需要更新为 min(dfn[这些边指向的节点]) .而理所当然地，我们也要被孩子节点更新 low 值为 min(low[孩子节点]) .
现在我们聚焦某一个点
\(i\)，观察 dfn[i] 与 low[i] 的关系，以下是两种情况：
dfn[i]>low[i]，这说明 \(i\) 或其子孙节点存在边连到 \(i\) 上方的节点.dfn[i]=low[i]，这说明 \(i\) 以及其子孙节点无法连到 \(i\) 上方的节点，那么这个点 \(i\) 就是一个强连通分量在这颗搜索树的根.
但是， \(i\) 的子孙节点有可能会组成另一个强连通分量，这意味着 \(i\) 的子树的节点不一定和 \(i\) 处在同一个强连通分量内，我们需要 栈 来解决这个问题.
现在，我们用一张图看一下 dfn[] 与 low[] 的关系。
在这张图中，有 (3,4,5,6) ，7 ，8 ，1 ，2 这四个强连通块.
下图是Tarjan算法的运行过程.
因为SCC模板就是Tarjan算法，所以在这里不放代码.
二分图的最大匹配#
何为二分图？二分图是一种特殊的无向图，它的顶点可以被分为两个互斥的独立集 \(U\) 和 \(V\) 的图，使得所有边都是连结一个 \(U\) 中的点和一个 \(V\) 中的点（如下图所示）.
何为匹配？一个图的匹配是这个图中一些边所形成的集合，满足任意集合中的两条边都没有公共顶点.
解决这个问题的算法之一是匈牙利算法.在了解这个算法之前，我们先要了解一下何为增广路（增广轨/交错轨）.
增广路：若 \(P\) 是图 \(G\) 中一条连通两个未匹配顶点的路径，并且已匹配和未匹配的边（也就是属匹配边集 \(M\) 的边和不属 \(M\) 的边）在 \(P\) 上交替出现，则称 \(P\) 为相对于 \(M\) 的一条增广路径.
不难发现，如果我们把 \(P\) 中原来属于 \(M\) 边从 \(M\) 中删除，把 \(P\) 中原来不属于 \(M\) 边加入到 \(M\) 中，变化后得到的新的匹配 \(M^\prime\) 恰好比原匹配多一条边.
而匈牙利算法就是不断寻找增广路 \(P\) ，通过取反操作得到更大的匹配 \(M^\prime\) 来代替 \(M\).
代码如模板所示.
割点#
是无向连通图中一个顶点 \(v\) , 如果删除它以及它关联的边后，得到的新图至少包含两个连通分量.
这里同样使用Tarjan算法.
思路和求SCC的Tarjan算法类似，这里直接给出结论：
一个顶点 \(u\) 是割点，当且仅当满足条件 \(1\) 或 \(2\).
- \(u\) 为树根，且 \(u\) 有两棵及以上的子树（这很好理解吧）.
- \(u\) 不为树根，且满足存在一条
\((u,v)\) 为树枝边使得
dfn[u] <= low[v]，即 \(u\) 有一个孩子无法到达 \(u\) 以上的点.
代码如模板所示.
桥#
是无向连通图中的一条边，如果删除它，得到的新图包含两个连通分量.
求桥和求割点差不多，可以直接从代码看出差别，而且判断条件的理解也和求割点差不多，此处不过多赘述.
双连通图#
不含割点的无向连通图.
双连通分量#
无向连通图的最大双连通子图.
点双连通分量#
通过找割点获得的双连通分量（层层递进.jpg
边双连通分量#
通过找桥获得的双连通分量.
后记#
本来这里有个模板合集的，但是因为太占空间就删掉了.
以上基本算法在洛谷几乎都有原题.