图论学习笔记——连通度

图的联通程度
(1)左图是最“脆弱的连通图”丢去任何一条边或任何一个非悬挂点都会是他称为非连通图 。
【图论学习笔记——连通度】(2)右图中虽然删去任何一条边后仍连通 , 但存在一个顶点

图论学习笔记——连通度

文章插图
 , 去掉后所得到的图非联通 。
(3)左图中丢去任何一条边或一个顶点都不能使它称为给联通图 , 但去掉两个不相邻的顶点或边就成为非连通 。
(4)右图连通性最强 , 任意去掉顶点和边后仍然是连通的 。
点割集
设联通图