91图的基本概念的基本术语 △°连通、连通图和连通分星 在无向图中,如果从顶点V到顶点v有路经,则称和v 是连通的。 ●连通图:任意两个顶点都是连通的图 ●连分量:无向图中的极大连通子图。 B ① 顶点集极大 E=HIK G3 2 11
启迪管理课程 11 9.1 图的基本概念－－图的基本术语 连通、连通图和连通分量 在无向图中，如果从顶点v到顶点v′有路径，则称v和v′ 是连通的。 ⚫ 连通图：任意两个顶点都是连通的图。 ⚫ 连通分量：无向图中的极大连通子图。 v1 v2 v4 v5 v3 G2 A B L M C F D E G H I J K G3 顶点集极大
91图的基本概念的基本术语 △°强连通图和强连通分星 ●强连通图:在有向图G中,如果对于每一对v1,v∈V, V判,从v到v和从v到v都存在路径,则称G是强连通 ●强连通分量:有向图中的极大强连通子图。 12
启迪管理课程 12 9.1 图的基本概念－－图的基本术语 强连通图和强连通分量 ⚫ 强连通图：在有向图G中，如果对于每一对vi ,vj∈V, vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通 图。 ⚫ 强连通分量：有向图中的极大强连通子图。 v1 v2 v3 v4 G1 3 5 6
91图的基本概念的基本术语 例1有n个顶点的有向强连通图最多需要多少条弧? 最少需要多少条弧?这样的有向图是什么形状? 答:有n个顶点的有向强连通图最多有n(m-1) 条边(构成一个有向完全图的情况);最少有m条边 (n个顶点依次首尾相接构成一个环的情况)。 13
启迪管理课程 13 9.1 图的基本概念－－图的基本术语 例9.1 有n个顶点的有向强连通图最多需要多少条弧？ 最少需要多 少条弧？ 这样的有向图是什么形状？ 答：有n个顶点的有向强连通图最多有n(n-1) 条边(构成一个有向完全图的情况)；最少有n条边 (n个顶点依次首尾相接构成一个环的情况)
92图的存储结构邻接矩阵表示法 图的存结除了要存储图中各个顶点本身的信息 外,同时还要存储顶点与顶点之间的所有关系。常用 的图的存储结构有邻接短阵、邻接表、十字邻接表和 邻接多重表。 921数组表示法(邻接矩阵表示法) ●物接矩阵( Adjacency Matrix)是表示顶点之间 相邻关系的矩阵。设G=(VE是具有n个顶点的图 则G的邻接矩阵是具有如下性质的n阶方阵: ,若(v,v减或<v,v,>是F(G)中的边 4U10,若(男,)v,>不是FG)中的边 14
启迪管理课程 14 9.2.1数组表示法（邻接矩阵表示法） 9.2 图的存储结构－－邻接矩阵表示法 ⚫ 邻接矩阵（Adjacency Matrix):是表示顶点之间 相邻关系的矩阵。设G=(V,E)是具有n个顶点的图， 则G的邻接矩阵是具有如下性质的n阶方阵： = ，若（ 或 不是 中的边 若（ 或 是 中的边 0 , ) v , E(G) 1 , , ) v , E(G) [ ][ ] i j i j i j i j v v v v v v A i j 图的存储结构除了要存储图中各个顶点本身的信息 外，同时还要存储顶点与顶点之间的所有关系。常用 的图的存储结构有邻接矩阵、邻接表、十字邻接表和 邻接多重表
92图的存储结构邻接矩阵表示法 01234 01010 10101 G2 0101 01 00|对称矩阵 401100 第列元素的值:表示顶点v与图中所有顶点是否存 在边的关系,有则相应位置上的值为1,否则为0。 令无向图中顶点v的度d(Vi= 邻接矩阵A中第例元素之和 15
启迪管理课程 15 9.2 图的存储结构－－邻接矩阵表示法 v0 v1 v3 v4 v2 G2 对称矩阵 = 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 AG2 0 1 2 3 4 0 1 2 3 4 ❖无向图中顶点Vi的度d(Vi)=邻接矩阵A中第i行/列元素之和 第i行/列元素的值：表示顶点Vi与图中所有顶点是否存 在边的关系，有则相应位置上的值为1，否则为0