图论2(连通分量+割点+欧拉回路)
一、强连通分量(针对有向图,可用Kosaraju算法+Tarjan算法)
1、强连通:有向图G中,如果两个点u和v之间存在u到v和v到u的路径,则称点u和v之间是强连通的。
2、强连通图:有向图G的任意两个顶点都是强连通的,则称G是强连通图
3、强连通分量:有向强连通图的极大强连通子图称为强连通分量。
4、极大强连通子图:G是一个极大强连通子图,当且仅当G是一个强连通子图且不存在另一个强连通子图G’使得G属于G’;
二、Dfs过程遇到的边的分类
1、树枝边:Dfs经过的边,即Dfs搜索树上的边;
2、前向边:与Dfs方向一致,从某个节点指向某个子孙的边;
3、反向边:与Dfs方向相反,从某个子孙指向某个节点的边;
4、横向边:从某个节点指向搜索树中另一子树中的某节点的边;
5、时间截:(在Tarjan算法中)DFN(u)为节点的搜索次序边号;
6、Low(u):(在Tarjan算法中)u或者Low(u)的子树能回溯到的最早栈中的DFN的值;
三、割点和桥(无向图)
1、割点:一个无相连通图中,如果删除一个点后,这个图变得不连通,则称这个点为割点;
2、割点集合:一个无相连通图中,如果删除一个定点集合V,删除定点集合以及与定点集合相连的边后,
原图不连通,就成这个点集V是割点集合;
3、割边:一个无相连通图中,如果删除一个边,这个图变得不连通,责成这个变是割边;
4、割边集合:一个无相连通图中,如果山区一个边集合,这个图变得不连通,则称这个边集合为割边集合;
5、点连通度:最小割点集合中的顶点数;
6、边连通度:最小割边集合中的边数;
7、双连通图:
(1)点双联通:一个无相连通图中的点的连通度大于1,则称这个点是双连通的
(2)边双连通:一个无相连通图中的边的连通度大于1,则称这条边是双联通的
(简称双联通或重连通)
8、桥:当且仅当一个图的边连通度为1时,割边集合的为唯一元素被称为桥(即删去桥原图不连通)。
9、双连通分量:双联通分量是图中的极大双联通子图;
10、双联通子图:在图G中的所有子图G’中,如果G’是双联通的,则称G’为双联通子图
(极大双连通子图:如果G是图的一个双联通子图,且图中没有另一个子图G’使得G属于G’,则称G是一个双联通子图)
(块:特殊的点双联通子图)
辩证概念:
1、有割点的图不一定有割边
eg:
2、一个图可能有多个割点(割点是割边的一个元素)
3、一个图可能有多个桥
4、错误:
(1)两个割点之间一定是割边;
(2)割边的两个割点一定是割点;
反例:
5、边双联通分量一定是点双联通分量,但点双联通分量不一定是边双联通分量
eg:
四、欧拉回路(欧拉图可以是有向图,也可以是无向图)
设图G=(V,E);
1、欧拉回路:图G中经过每条边一次,并且仅一次的回路称为欧拉回路;
2、欧拉路径:图G中经过每条边一次且仅一次的路径称为欧拉路径;
3、欧拉图:存在欧拉回路的图称为欧拉图
4、半欧拉图:存在欧拉路径但不存在欧拉回路的图;
欧拉图性质:
1、对无向图G,
(1)当且仅当图G中的所有顶点的度数为偶数;
(2)无向图G为半欧拉图,当且仅当G为连通图,且所有顶点的入度等于出度
2、对有向图G
(1)有向图G是欧拉图,当且仅当G的基图连通,且所有顶点的入度等于出度,
(2)有向图G是半欧拉图,当且仅当G的基图连通,且存在顶点的入度比出度大1(只能是入度大于出度,因为是指向
单节点,不是单节点指向图)
ps:基图:忽略有向图的所有方向得到的图。
3、设C是欧拉回路G的一个简单回路,将C的边从图G中删去得到一个新的图G’,则G’的每一个极大联通子图都有
一条欧拉回路。
(证明:若C为无向图,则图G’中各个顶点的度数为偶数,若C为有向图,则图G’的个顶点的入度等于出度)
4、设C1、C2是图G的两个没有公共边,但有公共点的简单回路,我们可以将他们合并成一个简单的新回路C’。
证明: