点连通度怎么求带图例题

点连通度是《图论》中的一个概念，在《离散数学》这门课中也会出现，那么我们来看一下点连通度要怎么求带图例题，下面将从概念开始介绍。

连通图G的连通度通常称为连通度，有两种连通性，一种是点连通性，另一种是边连通性。通常，图的连通性越好，它所代表的网络就越稳定。

如果图G的连通分支数在删除图G中的节点X后增加，即节点X称为图G的割点。如果图G的连通分支数在删除图G中的边e后增加，即e称为图G的割边或桥。没有切点的非平凡连通图称为块。在G中没有切点的极图称为图块G。如果h是图G的一个块，h本身不包含切点，并且满足以下要求：如果在h上添加了边，但没有添加节点，则h不是G的子图；如果我们在h上添加更多的节点或边，并将h展开成一个更大的连通图，那么h将包含切点。

所以，求图例的时候，只需要对概念够清晰，就能够很快得到答案。

图的点连通度边连通度总结：

一、点连通度的定义：

一个具有N个点的图G中，在去掉任意k-1个顶点后（1<=k<=N）,所得的子图仍然连通，去掉K个顶点后不连通，则称G是K连通图，K称作图G的连通度，记作K（G）。 

二、独立轨：

A，B是图G（有向无向均可）的两个顶点，我们称为从A到B的两两无公共内顶点的轨为独立轨，其最大的条数记作p(A,B)。  

在上图中有一个具有7个定点的连通图，从顶点1到顶点3有3条独立轨，即p(1,3)=31—2—3,1—7—3,1—6—5—4—3。

如果分别从这3条独立轨中，每条轨抽出一个内点，在G图中删掉，则图不连通。若连通图G的两两不相邻顶点间的最大独立轨数最小的P（A，B）值即为K（G）。

若G为完全图（两两点可达），则K（G）=n-1，即完全把某个点的所有边删掉后才不连通。既然独立轨是只能经过一次的边，那么可以构造网络流模型，其中每条边的容量为1，就可以限制只经过一次。

三、构建网络流模型：  

1、若G为无向图： 原G图中的每个顶点V变成N网中的两个顶点V`和V``,顶点V`至V``有一条弧容量为1； 原图G中的每条边e=UV，在N网中有两条弧e`=U``V`,e``=V``U`与之对应，e`与e``容量均为无穷； 以A``为源点，B`为汇点，求最大流。  

2、若G为有向图：原G图中的每个顶点V变成N网中的两个顶点V`和V``,顶点V`至V``有一条容量为1的弧； 原G图中的每条弧e=UV变成一条有向轨U`U``V`V``,其中轨上的弧U``V`的容量为无穷； 以A``为源点，B`为汇点求最大流。

四、构建一个网络N：

1、若G为无向图： 原G图中的每条边e=UV变成两条边e`=UV,e``=VU,容量都为1；固定一个点为源点，枚举与源点不相邻的为汇点，求最大流max_flow，保留最小的max_flow即为图的边连通度。 

2、若G为有向图：原G图中每条有向边容量为1；此步骤与无向图的步骤2相同。求出的残余网络中，流量为1的弧e`=(u,v),则e`就是桥。 

五、求边连通度总结： 

1、G是K的连通图，k>=2,则任意K个顶点共圈。同样引入独立轨的概念，只是在这里叫弱独立轨，同样在每条弱独立轨中。

2、只有去掉某一条边就可以使起点到终点不连通，现在整个图G的边连通度就是要找出任意两点的弱独立轨的最小值。如果图G为完全图，则K`(G)为n-1。

3、A是有向图G的一个顶点，如果A与G的其他所有点V间的最小值为K，则G中存在以A为根的K棵无公共边的生成树； 

4、设G是有向图，0<k<=K`(G),L是0至k之间任意一个整数，对于图G的任意一对顶点(u,v)来说，存在U到V的L条弱独立有向轨，同时存在从V到U的L-k条弱独立有向轨。

---