图论:树,图的生成树

树的定义:
如果一个无向简单图G满足以下相互等价的条件之一,那么G是一棵树:
1. G是没有回路的连通图。
2. G没有回路,但是在G内添加任意一条边,就会形成一个回路。
3. G是连通的,但是如果去掉任意一条边,就不再连通。
4. G内的任意两个顶点能被唯一路径所连通。 继续阅读图论:树,图的生成树

图论:连通,连通图,强连通图,连通分量,强连通分量概念及解析

概念:
1. 连通:在一个无向图G中,若从顶点v_i到顶点v_j有路径相连(当然从v_j到v_i也一定有路径),则称v_i和v_j是连通的。如果G是有向图,那么连接v_i和v_j的路径中所有的边都必须同向。
2. 连通图:如果图中任意两点都是连通的,那么图被称作连通图。
3. 强连通图:有向图G = (V,E)中,若对于V中任意两个不同的顶点x和y,都存在从x到y以及从y到x的路径,则称G是强连通图。
4. 连通分量:无向图G的一个极大连通子图称为G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

解析:
对于一个无向图,说强联通没有意义,因为此时强连通就是连通。

而对于一个有向图,它不一定是强连通的,但可以分为几个极大的强连通子图(“极大”的意思是再加入任何一个顶点就不满足强连通了)。这些子图叫做这个有向图的强连通分量。

强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连通分量,且多个强连通分量之间没有共享边及共享节点。

任意一个强连通分量都至少包含一个有向环。