图论基础

仙人掌(+简单回路)

仙人掌图是强连通的(有向图或无向图),任意一条边至多只出现在一条简单回路,简单回路就是指在图上不重复经过任何一个顶点的回路。

比如这就是仙人掌

这不是仙人掌

(可以顺便结合两个图理解什么是简单回路)

桥(割边)

在一个

无向连通图

中删除一条边后,该图被分成两个或者更多的连通分量,那么这条边就被称为割边,也被称为

边双联通

如果一个无向连通图
没有割边,那么就称该图为边双连通图。无向图的极大边双连通子图被称为边双连通分量。

割点(关节点)

在一个

无向连通图

中删除一个结点及与它相关的边之后,该图被分成两个或者更多的连通分量,那么这个点就被称为割点,也被称为关节点

点双联通

如果一个无向连通图没有割点,那么就称该图为点双连通图。无向图的极大点双连通子图被称为点双连通分量。

原文地址:https://www.cnblogs.com/Doingdong/p/10780521.html