7.回路或环 若一条路径上的开始点与结束 点为同一个顶点,则此路径被称为 回路或环。开始点与结束点相同的 简单路径被称为简单回路或简单环。 例如,右图中,(0,2,1,0就 是一条简单回路,其长度为3
7 . 回路或环 若一条路径上的开始点与结束 点为同一个顶点 ，则此路径被称为 回路或环 。开始点与结束点相同的 简单路径被称为简单回路 或简单环 。 例如 ，右图中 ， ( 0 ， 2 ， 1 ， 0 ) 就 是一条简单回路 ，其长度为 3 。 1 2 0 3
8.连通、连通图和连通分量 在无向图G中,若从顶点i 到顶点有路径,则称顶点和(2 (0)(a) 是连通的。 3 若图G中任意两个顶点都 连通,则称G为连通图,否则 称为非连通图。 无向图G中的极大连通子 称为G的连通分量。显然 任何连通图的连通分量只有 3 个,即本身,而非连通图有多 个连通分量
8 . 连通 、连通图和连通分量 在无向图 G 中 ，若从顶点 i 到顶点j有路径 ，则称顶点 i 和j 是连通 的 。 若图 G中任意两个顶点都 连通 ，则称 G 为连通图 ，否则 称为非连通图 。 无向图 G中的极大连通子 图称为 G的连通分量 。显然 ， 任何连通图的连通分量只有一 个，即本身，而非连通图有多 个连通分量。 1 2 0 3 1 2 0 (b) (a) 3
9.强连通图和强连通分量 在有向图G中,若从顶点倒 顶点有路径,则称从顶点倒是 连通的。 若图G中的任意两个顶点和 都连通,即从顶点到和从顶忘 到都存在路径,则称图G是强连 通图。 有向图G中的极大强连通子图 称为G的强连通分量。显然,强 连通图只有一个强连通分量,即 (b) 本身,非强连通图有多个强连通 分量。 3
9. 强连通图和强连通分量 在有向图 G中，若从顶点 i 到 顶点j有路径，则称从顶点 i 到j 是 连通的。 若图 G中的任意两个顶点 i和j 都连通，即从顶点 i 到j和从顶点j 到 i都存在路径，则称图 G是强连 通图 。 有向图 G中的极大强连通子图 称为 G 的强连通分量。显然，强 连通图只有一个强连通分量，即 本身，非强连通图有多个强连通 分量。 1 2 0 3 (b) (a) 1 2 0 3
10.权和网 图中每一条边都可以附有一个对应的数值,这种与 边相关的数值称为权。权可以表示从一个顶点到另一个 顶点的距离或花费的代价。边上带有权的图称为带权图, 也称作网
10. 权和网 图中每一条边都可以附有一个对应的数值，这种与 边相关的数值称为权。权可以表示从一个顶点到另一个 顶点的距离或花费的代价。边上带有权的图称为带权图， 也称作网
例72有个顶点的有向强连通图最多需要多少条边? 最少需要多少条边? 解:有n个顶点的有向强连通图最多有m(n-1)条边 (构成一个有向完全图的情况);最少有hm条边(n个 顶点依次首尾相接构成一个环的情况) 2
例7.2 有n个顶点的有向强连通图最多需要多少条边？ 最少需要多 少条边？ 解：有n个顶点的有向强连通图最多有n(n-1)条边 （构成一个有向完全图的情况）；最少有n条边（n个 顶点依次首尾相接构成一个环的情况）。 0 1 n-2 2 n-1 …