通路、回路和连通性

用点、边交错的序列表示 通路

如果起点和终点相同，称为 回路

通路的长度指边的个数

---

简单通路、简单回路：边不相同 就是一笔画里面的限制

基本通路、基本回路：点不相同 在边的基础上加上的对结点的限制

---

邻接矩阵 m 次幂：

• $a_{ij}$ 表示 i 到 j 的通路的数目（回路）
• ${\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{ij}$ 为 G 中长度为 m 的通路的总数

注意这里无向图一条边算了两次（当成有向图的两个边）

---

如果存在通路，称为 可达

长度最小的通路称为 短程线，长度称为 距离，不可达距离记为无穷

---

通路上界定理

用邻接矩阵判断可达

---

连通图

图的删除操作

点割集 边割集

连通度

---

有向图的连通性