2024-06-26 07:00| 来源: 网络整理| 查看: 265
通路 —— 点边点边……点（点边可以重复） 注意 长度 的概念——边数 回路 —— 最后又回到自己，如其字面意思 简单 —— 边互异（边不可重复） 初级 —— 点互异（点不可重复，除了起点终点） 注意路径 和圈 所指代的 复杂通路 应该不是很重要，先不看 注意是在无向图 的条件下
最长圈的长度是周长，最短圈的长度是围长
通路最大为n-1，而回路最大为n（因为比通路多了一条从次终点回到起点【终点】） 关于注：
比较简单，浅看一下即可
这个定义看看就行了，暂时想不到简单的解释，但是对于扩大路径法、极大路径目前是会的
注意是在无向图中 有通路就是连通的，图是连通的即——任意两个结点都是连通的 这个不用细看了
在有向图中 基图 —— 有向图去掉方向后的无向图 强连通是对于任何
注意一下p的含义——更加不连通的程度
简而言之——去掉一些点（在相应的情况下是最少的，但不代表是所有集合最少的，具体看例子）使图不连通，那么点组成的集合为点割集
割点——点割集只有一个元素（去掉这一个割点后，图就变得不连通了）
同点割集，只不过割集元素为边
割边也叫桥（熟悉这个说法）
所有点割集中最小的那个
同理
看看例
K2 3
通路 —— 点边点边……点（点边可以重复） 注意 长度 的概念——边数 回路 —— 最后又回到自己，如其字面意思 简单 —— 边互异（边不可重复） 初级 —— 点互异（点不可重复，除了起点终点） 注意路径 和圈 所指代的 复杂通路 应该不是很重要，先不看 注意是在无向图 的条件下
最长圈的长度是周长，最短圈的长度是围长
通路最大为n-1，而回路最大为n（因为比通路多了一条从次终点回到起点【终点】） 关于注：
比较简单，浅看一下即可
这个定义看看就行了，暂时想不到简单的解释，但是对于扩大路径法、极大路径目前是会的
注意是在无向图中 有通路就是连通的，图是连通的即——任意两个结点都是连通的 这个不用细看了
在有向图中 基图 —— 有向图去掉方向后的无向图 强连通是对于任何
注意一下p的含义——更加不连通的程度
简而言之——去掉一些点（在相应的情况下是最少的，但不代表是所有集合最少的，具体看例子）使图不连通，那么点组成的集合为点割集 
割点——点割集只有一个元素（去掉这一个割点后，图就变得不连通了） 
同点割集，只不过割集元素为边 
割边也叫桥（熟悉这个说法） 
所有点割集中最小的那个
同理
看看例
K2 3