离散数学 第四篇 图论02 图的连通性

离散数学

通路与回路

用邻接矩阵的幂来求通路数（回路）
设$A^m = (a^m_(n*n))$
ABO$_3^2$

距离

$v_i$到$v_j$的距离，对应在邻接矩阵的幂中$a_ij$的值，值均为0则不可达，距离为无穷，值大于0，则去值最小元素所在的邻接矩阵幂的幂次为距离。
邻接矩阵的幂最高不可超过图的结点总数

零图的距离

一阶零图

相应的定理、推论

1、如果$v_i$到$v_j$存在通路，则通路中存在长度不大于$n-1$的通路（基本回路）
2、如果存在经过结点的$v_i$的回路，则存在长度不大于$n$的回路（基本回路）

可达矩阵

设矩阵为$B$,该图结点总数为4

无向图的连通性

任何两个结点都是可达，则该无向图为连通的，连通图。
反之则为，非连通图或分离图
连通关系实质上是等价关系

连通分支

实质上是等价关系上的一个等价类
无向图是连通的等价于 $p(G)=1$，非连通图等价于 $p(G)>1$

割集

点割集
边割集

有向图的连通性

连通分支

本质：
关系的闭包

通路、回路的应用

1、Dijkstra算法求无向赋权图的最短路

2、Floyd算法求任意两结点的最短路