离散数学 --- 图论基础 --- 无向图的连通性和有向图的连通性

第一部分 ---- 无向图的连通性

1.完全图：任意两个结点之间都有边

2.零图：所有结点都是孤立结点

3.平凡图：仅有一个结点的图

1.等价类：R是集合上的一个等价关系，选定集合中的任意一个元素a，所有于a满足等价关系R的元素组成的集合就是等价类 --- [a]R ---- 等价类的其它性质如果需要的话可以自己去查

2.无向图的两点之间只要有边连接在一起那么这两点就是可达的，如果没有的话那就是不可达的

接下来我们要研究的是删除图中的结点 或 边 对图的影响（要注意的是当我们删除结点的时候还需要将与结点相关联的边给删除掉）

 1.集合的属于符号下面没有多一横的话表示左边是右边的真子集，如果有多一横的话则表示左边是右边的子集

 1.给集合套上绝对值表示的是这个集合的基数 --- 即这个集合中的元素个数 

 1.k是一个大于等于1的正整数

 

---

第二部分 --- 有向图的连通性

1.单向连通图就是任意两个结点之间至少从其中一个结点出发能够到达另一个结点

2.强连通图就是任意两个结点之间从其中任何一个结点出发都能到达另一个结点

3.弱连通图是去掉所有边的方向性后任意两个结点之间能够连通则称为弱连通图

 

 

 

1.第三点中的 A‘ 其实就是有向图略去了边的方向之后得到的无向图的邻接矩阵

 

1.一个结点入度为0，或者出度为0的话，这个结点导出的子图是强连通分支

2.图中最大的回路是一个强连通分支（所谓最大的回路就是只要再加一个结点就不是回路）

3.单向连通分支往往是强连通分支取并集的结果

4.如果一个结点与其邻接点（和结点具有邻接关系的其它结点）之间无法构成回路的话，这个结点导出的子图也是一个强连通分支