定理7-2.1在一个具有n个结点的图中,如果从结 点v到结点v存在一条路,则从结点v到结点v必存在 条不多于n-1条边的路。 口证明思路:多于n-1条边的路中必有重复出现的结 点,反复删去夹在两个重复结点之间的边之后,剩余 的边数不会超过n-1条边 定理7-2.1的推论在一个具有n个结点的图中, 如果从结点v到结点v存在一条路,则从结点v到结点 v必存在一条边数小于n的通路
定理7-2.1 在一个具有n个结点的图中，如果从结 点vj到结点vk存在一条路，则从结点vj到结点vk必存在 一条不多于n-1条边的路。 证明思路：多于n-1条边的路中必有重复出现的结 点，反复删去夹在两个重复结点之间的边之后，剩余 的边数不会超过n-1条边。 定理7-2.1的推论 在一个具有n个结点的图中， 如果从结点vj到结点vk存在一条路，则从结点vj到结点 vk必存在一条边数小于n的通路
定理721的证明 如果从结点v到vk存在一条路,该路上的结 点序列是vy1Yk,如果在这条中有条边,则 序列中必有|+1个结点,若>n-1,则必有结点vs, 它在序列中不止出现一次,即必有结点序列 sys.vk,在路中去掉从vs到vs的这些边, 仍是v到vk的一条路,但此路比原来的路边数要 少,如此重复进行下去,必可得到一条从v到vk 的不多于n-1条边的路
定理7-2.1的证明 如果从结点vj到vk存在一条路，该路上的结 点序列是vj…vi…vk，如果在这条中有l条边，则 序列中必有 l+1个结点，若l>n-1，则必有结点vs， 它在序列中不止出现一次，即必有结点序列 vj…vs…vs…vk，在路中去掉从vs到vs的这些边， 仍是vj到vk的一条路，但此路比原来的路边数要 少，如此重复进行下去，必可得到一条从vj到vk 的不多于n-1条边的路
2 e 2 e31e2 2 20 2 eA eA e5 e了 e5 el e5 e/ 60v5 如在图721中有5个结点。v1到v3的一条路为: V1e2vRe3v2e3v3eav2ekVse7V 73 此路中有6条边,去掉e3有路 23e4v2e65e 有4条边。 v1到v3最短的路为v1e2V3
如在图7-2.1中有5个结点。 v1到v3的一条路为： v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有6条边，去掉e3有路 v1e2v3e4v2e6v5e7v3 有4条边。 v1到v3最短的路为v1e2v3
无向图的连通性 1、连通 定义7-2.2在无向图G中,如果从结点u和结点v 之间若存在一条路,则称结点u和结点v是连通的 (connected) 结点之间的连通性是结点集V上的等价关系,对 应该等价关系,必可将作出一个划分,把Ⅴ分成非空 子集V,V2,…,Vm,使得两个结点v和v是连通的,当 且仅当它们属于同一个V。把子图G(V1),G(V2),…, G(Vn)称为图G的连通分支( connected components), 图G的连通分支数记为w(G)。 见281页图7-22
二、无向图的连通性： 1、连通 见281页图7-2.2 定义7-2.2 在无向图G中，如果从结点u和结点v 之间若存在一条路，则称结点u和结点v是连通的 （connected） 。 结点之间的连通性是结点集V上的等价关系，对 应该等价关系，必可将作出一个划分，把V分成非空 子集V1 , V2 , …, Vm,使得两个结点vj和vk是连通的，当 且仅当它们属于同一个Vi 。把子图G(V1 ) , G(V2 ) , …, G(Vm)称为图G的连通分支（connected components）, 图G的连通分支数记为W(G)