定理 推论在无向图G中,如果从结点v到结点v 存在一条路,则必存在一条从到v长度 小于n的通路。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定理 推论 G中，如果从结点vj到结点vk 存在一条路，则必存在一条从vj到vk而长度 小于n的通路
二、无向图的连通性 定义设G元<,E>是一个图,对vvev,从v到y 如存在一条路,则称结点v和v是连通的。 定义设G=<V,E>是一个无向图,若G中任意两个结 点之间都是连通的,则称该无向图G是一个无向连通 图,否则,则称G是一个非连通图(或分离图)。 定义设G=<V,E>是一个无向图,该无向图G中的每 个连通的划分块称为G的一个连通分支,用WG)表示G 中的连通分支数。无向图G=<V,E>是连通图当且仅 当W(G)=1。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 二、无向图的连通性 定义 设G＝<V，E>是一个图，对vi，vjV，从vi到vj 如存在一条路，则称结点vi和vj是连通的。 定义 设G＝<V，E>是一个无向图，若G中任意两个结 点之间都是连通的，则称该无向图G是一个无向连通 图，否则，则称G是一个非连通图(或分离图)。 定义 设G＝<V，E>是一个无向图，该无向图G中的每 个连通的划分块称为G的一个连通分支，用W(G)表示G 中的连通分支数。无向图G＝<V，E>是连通图当且仅 当W(G)＝1
例 k G1 G2 G1是连通图,WG1)=1; G是非连通图,且W(G2)=4 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn G1是连通图，W(G1 )＝1； G2是非连通图，且W(G2 )＝4。 例： 例：
割点 定义设无向图G=〈VE〉为连通的,若有结点集 v1是v的真子集,使得图G删除了v所有结点后, 所得的子图是不连通的,而删除了V的任意真子 集后,所得的子图仍然是连通图。则称集合V为 图G的点割集。若某一结点就构成点割集,则称 该结点为割点。 这样,一个连通图,删除它的一个点割集后,将分 成两个或多于两个连通分支 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定义设无向图G=〈V,E〉为连通的，若有结点集 V1是V的真子集，使得图G删除了V1所有结点后， 所得的子图是不连通的，而删除了V1的任意真子 集后，所得的子图仍然是连通图。则称集合V1为 图G的点割集。若某一结点就构成点割集，则称 该结点为割点。 这样，一个连通图，删除它的一个点割集后，将分 成两个或多于两个连通分支。 割点
割点 若G不是完全图,我们定义KG=min{V1 V1是G的点割集}为G的点连通度(或连通度) 连通度k(G)是为了产生一个不连通图需要删去 的点的最少数目。于是,一个不连通图的连通 度等于0,存在着割点的连通图的连通数为1 完全图K中删去任何m个(m<p-1)点后仍然连通, 但是删去了P-1个结点后产生一个平凡图,故定 义k(Kn)p-1 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 若G不是完全图，我们定义k(G)=min{| V1 | |V1是G的点割集}为G的点连通度(或连通度)。 连通度k(G)是为了产生一个不连通图需要删去 的点的最少数目。于是，一个不连通图的连通 度等于0，存在着割点的连通图的连通数为1。 完全图Kp中删去任何m个(m＜p-1)点后仍然连通， 但是删去了p-1个结点后产生一个平凡图，故定 义k(Kp )= p-1。 割点