|
连通图和连通分量 顶点间的连通性 在无向图G中若从顶点v i 到顶点v j 有路径(当然从v j 到v i 也一定有路径)则称v i 和v j 是连通的 连通图 若V(G)中任意两个不同的顶点v i 和v j 都连通(即有路径)则称G为连通图(Connected Graph) 【例】图G 和G 是连通图 连通分量 无向图G的极大连通子图称为G的连通分量(Connected Component) 注意 ① 任何连通图的连通分量只有一个即是其自身 ② 非连通的无向图有多个连通分量 【例】下图中的G 是非连通图它有两个连通分量H 和H 强连通图和强连通分量 强连通图 有向图G中若对于V(G)中任意两个不同的顶点v i 和v j 都存在从v i 到v j 以及从v j 到v i 的路径则称G是强连通图 强连通分量 有向图的极大强连通子图称为G的强连通分量 注意 ① 强连通图只有一个强连通分量即是其自身 ② 非强连通的有向图有多个强连分量 【例】下图中的G 不是强连通图因为v 到v 没有路径但它有两个强连通分量如右图所示 网络(Network) 若将图的每条边都赋上一个权则称这种带权图为网络(Network) 注意 权是表示两个顶点之间的距离耗费等具有某种意义的数 【例】下图就是一个网络的例子 |
