假如在无向图中删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或者多个连通分量,则称顶点v为该图的一个关节点.
一个没有关节点的连通图叫做重连通图,即任意两点之间至少存在两条路径.
至少删除k个顶点才能破坏图的连通性,则称此图的连通度为k.
附：极大连通子图(连通分量)：
设(1)S为无向图G的子图,S连通,(2)如果S"也是G的连通子图,且S是S"的子图时必有S=S",则称S是G的极大连通子图.
假如在无向图中删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或者多个连通分量,则称顶点v为该图的一个关节点.
一个没有关节点的连通图叫做重连通图,即任意两点之间至少存在两条路径.
至少删除k个顶点才能破坏图的连通性,则称此图的连通度为k.
附：极大连通子图(连通分量)：
设(1)S为无向图G的子图,S连通,(2)如果S"也是G的连通子图,且S是S"的子图时必有S=S",则称S是G的极大连通子图.