割点和割边
割点定义
割点的一个定理
如果点v是简单图G的一个割点，则边集
连通图中割点的等价定义
- v是G的割点
- G-v不连通
- 存在
的一个划分： , ,使得对 和 ,v在每条u-w路上 - 存在
,使得u,w异于v，且v在每条u-w路上
割边定义
割边的等价定义
- e是G的割边
- e不在G的任何圈中
连通图中割边的等价定义
- e是G的割边
- 存在
的一个划分： , ,使得对 和 ,e在每条u-w路上 - 存在
,使得e在每条u-v路上
连通度和边连通度
点割集
极小点割集
任何真子集都不是点割集
最小点割集
图中含顶点数最少的点割集
连通度
- G不是完全图：最小点割集的势
- G是完全图：v-1
- G不连通：0
- G是零图或平凡图：不讨论
连通度性质（
- 没有势为k-1或更小的点割集
- 任意去掉k-1或更少的点，仍然连通
k-连通
即
边割集
极小边割集
任何真子集都不是边割集
最小边割集
图中含边数最少的边割集
边连通度
- 最小边割集的势
- G不连通：0
- G是零图或平凡图：不讨论
连通度性质（
- 没有势为k-1或更小的边割集
- 任意去掉k-1或更少条边，仍然连通
k-边连通
即
一个重要的定理
G是3-正则图
