图论

101_k91 · 2020-01-21 10:36:44 · 个人记录

1、拓扑排序

逐个删去入度为0的点

区间操作：

设u,v为两个区间,若 Sv < Eu && Su < Ev 则两区间相交;

2、差分约束

#### _**$More$:**_ - 其他形式的不等式可以尝试移项来做，注意$c_i$可以是负数。 - $d_v + d_u \leq w$可以考虑$d_u' = -d_u$替换，要求$\{v\}\cap\{u\}=\empty$。 - 视情况选择最短路/最长路。 - Floyd看对角判定负环/正环。 - $Bellman-Ford$或$SPFA$通用判定负环/正环方法：某点被更新超过$n$次。 ### 3、二分图 $V = A \oplus B , E \subseteq A \times B

无奇环。

黑白染色，邻点异色。

棋盘是二分图

4、匹配

匹配：选取⼀些边，使得任意两条边没有公共点（每个点⾄多属于⼀条边）
最⼤匹配：选取边数尽可能多
完美匹配：所有点都在匹配中（每个点恰好属于⼀条匹配边）
匹配边，⾮匹配边，匹配点，⾮匹配点
交错路：从⾮匹配点出发，依次经过⾮匹配边、匹配边、⾮匹配边...
增⼴路：从⾮匹配点出发，结束于⾮匹配点的交错路

求最大匹配：匈牙利算法

增⼴路定理：任意⼀个⾮最⼤匹配的匹配⼀定存在增⼴路
初始没有选中的边
寻找增⼴路
找到增⼴路则将路径中匹配边和⾮匹配边对换
找不到增⼴路则当前为最⼤匹配

网络流算法

取额外的两个点作为源点和汇点
源点向左边⼀列每个点连流量为1的边
右边⼀列每个点向汇点连流量为1的边
⼆分图中每条边从左向右连流量为1的边
求最⼤流即可

二分图最大点覆盖

⽤尽可能少的点覆盖所有边。
König定理：⼆分图的最⼩点覆盖在数值上等于最⼤匹配。
构造：从右部⾮匹配点出发寻找所有可能的交错路，标记路径上经过的点。左部标记过的点和右部没有标记过的点构成了最⼩点覆盖。
证明：这样选出来的点数恰好等于最⼤匹配数。右部⾮孤⽴的未标记点⼀定是匹配点且匹配边的另⼀点未标记；左部标记点⼀定是匹配点且匹配边的另⼀点被标记。每条匹配边恰有⼀点被选⼊覆盖点集。选出来的点可以覆盖所有边。不存在左边点未标记⽽右边点被标记的边。这是最⼩的点覆盖，因为覆盖最⼤匹配中的边就⾄少需要这么多个点。

5、欧拉路

欧拉路径：恰好经过图中所有边⼀次且仅一次 (一笔画)。

欧拉回路：回到出发点的欧拉路径。

存在性⼤前提：图连通 (废话)

有向图：

欧拉路径存在性：

所有点的⼊度=出度
⼀个点⼊度-出度=1，⼀个点出度-⼊度=1，其余点⼊度=出度
欧拉回路存在性：所有点⼊度=出度

无向图：

欧拉路径存在性：⾄多两个点度数为奇数
欧拉回路存在性：所有点度数为偶数

欧拉路的dfs构造：

void dfs(int u) {
    for (int v = 1; v <= n; ++v)
        if (G[u][v] == 1)
        {
            G[u][v] = 0;
            dfs(v);
        }
        ans.push_back(u);
}

reverse(begin(ans), end(ans));

Continued...