图论 笔记
有些东西不知道有什么用...但既然dls讲了就记记吧。很多东西来自国庆正睿 dls课件。
把以前的写的合并到一篇了。
也可以看这儿。
度数序列
对于无向图,(d_1,d_2,...,d_n)为每个点的度数。
有(d_1+d_2+...+d_n=2e)(每条边被计算两次)。
有偶数个度数为奇数的点。
Havel–Hakimi算法
给定一个由有限多个非负整数组成的度数序列,是否存在一个简单图使得其度数序列恰为这个序列。
令(S=(d_1,d_2,...,d_n))为有限多个非负整数组成的非递增序列。
(S)可简单图化当且仅当有穷序列(S’=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n))只含有非负整数且是可简单图化的。
序列(S)可简单图化是指存在一个无向图(无重边无自环),使得其度数序列恰为(S)。
(这个其实就是很显然的东西。。主要是一个定义)
Erdős–Gallai定理
令(S=(d_1,d_2,...,d_n))为有限多个非负整数组成的非递增序列。
(S)可简单图化当且仅当这些数字的和为偶数,且$$sum_{i=1}^kd_ileq k(k-1)+sum_{i=k+1}^nmin(d_i,k)$$
对于任意(1leq kleq n)都成立。
也不难理解。对前(k)个点分配度数,除了两两能连(frac{k(k-1)}{2})条边外,剩下的度数由后面点的度数补。
因为(d_i)非递增,从小到大枚举(k),维护(d_i)后缀与(k)取(min)的和((d_i,k)都是单调的,维护从哪开始(min(d_i,k))的结果是(d_i))。就可以(O(n))判断了。
例题:Good Bye 2018 E(竟然真的遇到了),NEERC2013 K.Kids in a Friendly Class。
欧拉路与欧拉回路
给定一张无向/有向图,求一条经过所有边恰好一次的回路。
有解当且仅当所有点 度数为偶数(无向)/入度等于出度(有向)。
任选一点开始dfs,每条边只经过一次。回溯时将回溯的边加入队列,最后队列的逆序就是答案。
时间复杂度 (O(m)).
欧拉路径也可以用一样的方法求出(找度数为奇数的点进行DFS)。
欧拉回路:有向图:所有点的出度入度都相等;从任意一点都可实现。
无向图:所有点度数都为偶数。
欧拉路:有向图:有两个点可以入度出度不相等(差不大于一),即起点终点;起点入度小于出度,终点入度大于出度 。
无向图:仅有两个点度数为奇数。
注:必须为连通图(用并查集判断)。
两笔画问题:
有解当且仅当入度为奇数的点不超过四个。
将其中两个点加一条边后求欧拉路径,然后在这条边处断开成两条欧拉路即可。
时间复杂度 (O(m)).
题目
Prufer序列
这个很全啊,可以看这儿。
Defination:
Prufer序列是一种无根树的编码表示。
对于一棵(n)个点的无根树,对应唯一一串长度为(n-2)的(Prufer)序列。
无根树转(Prufer)序列
定义无根树中度数为(1)的节点是叶子节点,每次找到编号最小的叶节点删除,在序列中添加与之相邻的点。如此重复直到剩下最后两个节点。
上图对应无根树的(Prufer)序列为(3,5,1,3)。
(Prufer)序列转有根树
给定点集(G={1,2,ldots,n}),(Prufer)序列([a_1,a_2,ldots,a_{n-2}])。
每次取出(Prufer)序列中的第一个元素(x_i),在(G)中找在当前(Prufer)序列中没有出现的第一个元素(y_i),在(x_i)和(y_i)间连一条边;将(x_i)从(Prufer)序列中删除,(y_i)从(G)中删除。
最后(G)中还剩下(2)个元素,在这(2)个元素间连一条边。
生成树计数
Cayley定理:完全图的生成树个数为(n^{n-2})。
如果每个点的度数为(d_i),那么生成树个数为(frac{(n-2)!}{(d_1-1)!(d_2-1)!...(d_n-1)!})。
每个连通块大小为(a_i),那么添加一些边将这些连通块连通的生成树个数为(a_1 imes a_2 imes... imes a_n imes(a_1+a_2+...+a_n)^{n-2})。
题目
题集。
Matrix-Tree定理
无向图生成树计数:令(G=D-A)(基尔霍夫矩阵=度数矩阵-边矩阵),然后去除(G)的任意一行一列得到(G’),(G’)的行列式即生成树个数。
有向图生成树计数:与无向图不同的是,(D)矩阵为入度/出度矩阵分别对应外向树/内向树。且删掉第(i)行第(i)列表示以(i)为根节点的生成树个数。
题目
题集。
最小生成树 Borůvka算法
一开始每个连通分量是一个点本身。
每轮枚举所有属于不同连通分量的边,每个连通分量选择和其他连通分量相连的最小的边,然后合并。
每轮连通块个数至少减半,所以最多进行(log V)轮。时间复杂度(O(Elog V))。
具体实现直接用并查集即可。代码可以看这里。
题目
一般用来做边权与点权相关,还是个完全图,求MST的题?
- 有(n)个点的完全图,每个点的权值为(a_i),两个点之间的边权为((a_i+a_j) mod M)。求这张图的最小生成树。
(Nleq10^5,0leq M,a_ileq10^9)
具体怎么做忘了。。你们结合下面的题脑补一下。 - CF888G。
有一张(n)个点的完全图,每个点的权值为(a_i),两个点之间的边权为(a_i ext{xor} a_j)。求该图的最小生成树。
(nleq2*10^5,0leq ai<2^{30})。
最小瓶颈生成树
使得生成树树上最大边权值最小。
方法1:最小生成树一定是最小瓶颈生成树。
方法2:二分答案,看点是否连通。
方法3:
类比找第k大值的方法(nth_element
),首先随机一个边权(w)。然后将不超过这个边权的边加入,遍历这张图。
如果图连通,那么瓶颈不超过(w),于是只需考虑边权不超过(w)的边;否则将这些连通点缩起来,考虑边权大于(w)的边。
每次将问题的规模缩小至一半。期望时间复杂度(T(m)=T(frac m2)+O(m)=O(m))。
单源最短路(SSSP)
(Dijkstra)(贪心)或者(Bellman Ford)(动态规划)。
时间复杂度(O(mlog n))或者(O(nm))。
一些变种
边权是(0/1):双端队列,如果是(0)在头部插入,否则在尾部插入。
最长路径不超过(W), 正权图:使用(0...W)的桶+链表维护这些点(代替堆),时间复杂度(O(m+W))。
关于判负环
复杂度(O(nm))。代码实现可以记录最短路树上的深度来判环,而不是入队次数,这样会有优化。
if(dis[v]>dis[u]+w)
dis[v]=dis[u]+w
dep[v]=dep[u]+1
if(dep[v]>n) return;
差分约束
大体过程:http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
考虑最短路中的松弛操作:if(dis[v]>dis[x]+w) dis[v]=dis[x]+w
,也就是强制使得(dis[v])满足(dis[v]leq dis[x]+wRightarrow dis[v]-dis[x]leq w)。
所以对于(x_j-x_ileq w)的限制,可以连一条边((i o j,w))。这样求(x_n-x_0)的最大值,就是求(0 o n)的最短路。
如果限制是(x_j-x_igeq w),同理连边((i o j,w))。(x_n-x_0)的最小值就是求(0 o n)的最长路。
如果两种限制都有,就把(geq)变成(leq)。
解的存在性:
比如求(x_n-x_0)的最大值:若图中存在负环,则(0 o n)的最短路无穷小,则不存在最大值(无解)。
若(0)和(n)就不在同一连通块,则(0 o n)的最短路无穷大,最大值无穷大(或者存在无数多解)。
否则有解。
PS:
(SPFA)可以根据入队次数判负环,也可以据此判正环。虽然效率都不高就是了。
(Dijkstra)不能求最长路(本质是贪心)。
如何判断解唯一:
对原图求一遍最短路。将原图取反,边权取反,求一遍最长路。
一个标号对应的是能取到的最小值,一个是最大值。
如果相同则解唯一。(没什么用)
题目
题集。
多源最短路(APSP)
(Floyd):(O(n^3))
(Johnson)算法(可用于负权图):(O(nmlog n))
(Johnson)算法
原理:首先给图中每个点一个权值(h(u)), 把每条边的边权(w(u,v))改成(w(u,v)+h(u)-h(v))。
对于(s o t)的一条路径(p),权值为
=
所以这么做不会改变最短路。(也可以看这儿)
实现:第一次SPFA预处理(1)到每个点的距离(dis),记(h(v)=dis(v))。然后把边权(w(u,v))改为(w(u,v)+h(u)-h(v))。
其中(h(u))为给每个点设定的权值,(h(u)=dis[u])。
由不等式可以得到(dis(u)+w(u,v)geq dis(v)),也就是改完之后所有边权非负。
之后可以每个点用(Dijkstra)跑。就是(O(nmlog n))啦。
这样也可以实现(Dijkstra)跑费用流。
半径 直径 (正权图)
(后面就直接抄dls课件了QAQ)
(u)的偏心距 (ecc(u)=max{dis(u,v)})
直径 (d=max{ecc(u)})
半径 (r=min{ecc(u)} (d
eq2r))
中心 (arg min{ecc(u)})(要求定义在点上)
绝对中心(可以定义在边上)
绝对中心
相关:求最小直径生成树(差不多)。
实现:固定一条((u,v)),考虑上面的点(p)的偏心距。
假设第三个点是(w), (dis(p,u)=x)。
那么对应的折线为(min{x+dis(u,w), w(u,v)-x+dis(v,w)})。
那么偏心距为(n)条折线的最大值形成的折线。
按左端点排序维护一下。时间复杂度(O(nmlog n))
最小直径生成树
即绝对中心的最短路树。
如何证明?
注意一棵树(T)的直径为半径的两倍(对绝对中心来说)。如果最小直径生成树(T’)不包含绝对中心,那么取(T’)的绝对中心(v),显然矛盾。
拓扑排序
每次去掉图中入度为(0)的点。
时间复杂度(O(n+m))。
如果最后不为空集,那么这个图不为DAG。(否则每个点入度不为0,即每个点可以选择一个前趋,沿着前趋走根据抽屉原理一定能找到相同点,也就是一个环。)
按照反图DFS,出栈序列就是一个合法的拓扑序列。
scc缩点顺序也是一个合法拓扑序。
求字典序最小的拓扑序
每个点有不同的标号,要使得拓扑序最小。
将拓扑排序的队列改成优先队列即可。
最小拓扑序的一个变种
使得最后的拓扑序中1的位置尽量靠前,如果相同比较2的位置,依次类推。
首先考虑如何求1最早出现的位置,可以将原图反向,然后每次弹除了1之外的元素,直到队列只剩下1为止。
这是反图中1的最晚的出现的位置,也就是原图中最早的。
根据是否在队列里,这个图被分成两部分,在对应的图中用同样的方法处理2,依次类推。
容易发现每次找尽量大的元素出队,能完成上述的过程。
所以等价于反图最大字典序。
题目
题集。
二分图匹配
Hall's marriage theorem(霍尔定理)
对于一个二分图(G=(X,Y,E)),记(S)为(X)的一个子集,(N(S))为所有(S)中所有点的相邻点的并集。
一个图有完备匹配当且仅当(X)的所有子集(S)都有(|S|leq|N(S)|)。
对一般图的推广:
推论: 每个正则二分图都有完备匹配。
Kőnig's theorem
最小点覆盖=最大匹配 (与最大流最小割定理等价)
最大独立集=点数-最大匹配 (独立集为点覆盖的补集)
最小边覆盖=最大独立集 (独立集中每个点需要一条边去覆盖)
DAG最小路径覆盖
覆盖所有的边:每条边下界设为1, 然后求最小流。
覆盖所有的点:建立二分图,对于(u o v)的边,看做二分图中的((u,v’)),然后答案为点数-最大匹配。
(Dilworth)定理: 最大反链=最小链覆盖;最短的最长链=最小反链划分数-1(?存疑。见BZOJ4160)。(当然这个不应该只放在二分图部分的)
题目
题集。
连通分量
强连通分量
(Tarjan)。
将一个图的所有强联通分量缩起来会得到一个DAG。
双联通分量
点连通度: 最小的点集使得删去之后图不连通
边连通度: 最小的边集使得删去之后图不连通
如果一个图的点连通度大于1,那么是点双连通的,边连通同理。
双联通分量为图中的极大双联通子图。
割点和桥
考虑DFS树,每条非树边对应着一个点到祖先的路径。对于一条非树边只要把对应的边打上标记即可。
比如对于((u,v))这条非树边,只要在(u)点打上(+1)的标记,(v)点打上(-1)的标记。
(x)到(fa[x])的树边的覆盖次数为子树内所有标记的和。
割点同理(注意特判根节点和叶节点)。
(没看懂下面要干嘛)
题目
题集。
2-SAT
一堆变量的二元限制。
问是否存在合法的赋值。
题目
曼哈顿距离与切比雪夫距离
将原坐标系每个点的坐标((x,y))变为((x+y,x-y)),则原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
反过来,将原坐标系每个点的坐标((x,y))变为((frac{x+y}{2},frac{x-y}{2})),则原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。
例题:BZOJ3170 松鼠聚会。