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