离散数学--连通性和矩阵
目录
0.关系的运算和性质
1.通路和回路
2.连通关系
3.割点（边）和点（边）割集
4.强（弱）连通&单向连通
0.关系的运算和性质
（1）这个运算包括了矩阵的运算，包括这个幂运算，关系的合成，关系的逆运算，求解幂集等等；
（2）性质包括自反性，反自反性,对称性，反对称性，传递性；
（3）对于一个普通的集合，有多少种关系？就是2的m次方种，m就是集合里面的元素个数的平方，E就是一个集合里面的完全关系，I就是一个集合里面的等价关系，L就是一个集合里面的小于等于关系，D就是一个集合里面的整除关系；
对称性就是要求对于这个集合里面的每一个元素，都有自己到自己的关系，反对称性就是要求这个集合里面的元素都没有环，不同的节点之间的关系对于这个反自反性没有影响；
对称性要求如果两个节点之间有这个关系，那么这个关系必须是双向的，或者是没有关系，环对于这个对称性没有影响；反对称性就是要求这个节点之间的关系是单向的，环对于反对称性也是没有影响的；
传递性就是如果第一个节点有到第二个节点的关系，第二个节点有到第三个节点的关系，那么第一个节点也应该是有第三个节点的关系，这样的关系性质我们称为传递性；
1.通路和回路
（1）初级回路和简单回路
如果这个回路里面经过的所有的顶点都不一样，这个时候就叫做初级回路，也叫做圈；
如果这个回路里面经过的所有的边都不一样，这个时候的回路叫做简单回路，初级回路一定是简单回路，因为经过的顶点不一样的时候，这个经过的边一定不会重复，符合简单回路的定义，但是简单回路不一定是初级回路；
（2）说明
环是长度是1的圈，两条平行边构成的就是长度是2的圈；因为自己是可以和自己成为一个环的；
无向简单图里面圈的长度至少是3，因为至少需要三个顶点才可以构成一个圈，在有向简单图（简单图就是无重边无环）里面，两个顶点之间来回的通路就可以构成圈，所以至少是2；
（3）两种意义
2.连通关系
（1）连通图就是每两个顶点之间形成通路的图，连通关系R就是两个点之间形成的集合（这两个点之间不一定是直接相连的，只要两者之间存在通路就可以）；
（2）连通图的生成子图就是这个连通图的连通分支，有几个生成子图，就会有几个连通分支；
3.割点（边）和点（边）割集
（1）我们的这个割点和点割集主要就是在这个网络结构里面体现出来的，例如对于一个简单的网络结构，我们想要攻击他，使之系统崩溃，如果我们攻击一个点就可以是这个系统崩溃，我们就把这个点叫做割点，攻击一些点可以让这个网络结构崩溃，我们把这些点的集合叫做点割集；
（2）通过建模，我们就可以把这个网络模型抽象为一个图，这个图里面有很多个顶点和边，我们去掉某一个顶点之后，这个图就不再连通，我们就把这个点叫做割点；
去掉某些顶点之后破坏这个图的连通性，这些点我们就叫做点割集，需要注意的是，这些点需要恰到好处，怎么理解呢，就是对于一个简单的连通图而言，如果割掉v1 v3两个顶点就可以破坏这个图的连通性，那么v1 v2 v3割掉这三个顶点一定也可以破会这个图的连通性，但是v1 v2 v3就不是恰到好处的，因为我们去掉两个顶点就可以破坏这个图的连通性了，为什么还要多此一举呢？
（3）实际上，我们的实际应用里面也可以发现，攻击两个点就可以让这个网络结构崩溃掉，为什么要共计三个点来增加我们自己被暴露的风险呢？通过这一点运用就可以让我们更加深刻的理解点割集的定义要求；
（4）下面的就是一个连通图，我们找出这个图的点割集和割点，割点就是v5v6因为只要去掉这两个点里面的任意一个，都会破坏这个图的连通性；
对于点割集而言，v5 v6自身都是可以作为一个点割集存在的，只不过这个集合里面只有一个节点元素，v1v4也是可以作为一个点割集的，去掉这三个点也是可以破坏这个图的连通性的；
而且是恰到好处的，因为我们如果只写一个v1或者v4都不能破坏这个连通性，如果多写就没必要呢，因为这样就多此一举了；
（5）割边也叫做桥，割边就是去掉边，割掉的边也需要刚刚好；上面的图里面，e7e8都可以是单独的边割集，e5e6e9也是一个边割集的序列，e1e3e9也是一个边割集的序列，e2e4e6也是一个边割集的序列，去掉这些边之后这个图就不联通了，出现了孤立的点；
（6）随堂演练
对于一个连通图，去掉边割集之后，这个图的连通分支数就是2，因为去掉边割集之后把这个图分成了两个部分，去掉边割集之后，连通分支数就会大于等于2，例如这个大风车的图，去掉中间的这个连接点之后就可以把这个图分为多个连通分支；
完全图没有点割集，n阶零图没有点割集也没有边割集；
4.强（弱）连通&单向连通
（1）下面介绍的就是强连通和弱连通的概念。弱连通就是一个有向图的基图是连通图，就是去掉方向之后这个图是连通的，我们就把这个图叫做弱连通图；
单向连通讲的就是对于任意的两个顶点，顶点之间是单向可达，比如12两个顶点，1到2是可达的，或者2到1是可达的，而且是对于我们任意选择的两个顶点，都存在这样的关系，我们就把这个图叫做单向连通的；
对于强连通，就是任意的两个顶点之间都是可以相互抵达的，我可以到达你，你也可以到达我，对于任意选择的两个顶点都有这样的关系，我们就把这个有向图叫做强连通图；
（2）强连通，弱连通的判定
强连通判定：这个图里面存在一条经过每个顶点至少一次的回路；
单向连通判定：这个图里面存在经过每个顶点至少一次的回路；
（3）无向图的关联矩阵
关联矩阵表示的就是这个点和边之间的关系，里面矩阵元素就是和这个点相互关联的边的条数；
这个关联矩阵，我们可以得到下面这些有用的信息：
每一列的和都是2，表明这个和每一条边相互关联的顶点数量是2，每一行的和表示的就是这个顶点的度数，出现2表示这个地方是环，e2,e3这两列相同表示这个就是平行边；
（4）有向图的关联矩阵（无环）
如果这个图里面边关联的顶点是起点矩阵里面就写1，终点就写-1，不关联就写0，如果是环，这个顶点既是顶点也是重点 ，那么这个地方就会有歧义，因此我们讨论这个有向图的连通性的时候，不考虑带环的情况；
（5）邻接矩阵和可达矩阵
邻接矩阵就是用来表示这个点和点之间的通路数数量，我们可以通过这个矩阵的乘法判断这个图上面不同长度的通路的数量；
可达矩阵就是两个点之间可以到达就是1，不可以到达就是0，我们规定任意的一个顶点到达自己都是可达的，因此这个矩阵上面的对角线上面的元素都是1，而且对于强连通图，这个矩阵的所有的元素都是1；