顶点的度:顶点的度TD(v)=ID(v)+OD(v)。 6路径:无向图G=(V,中从顶点v到顶点v的路径(path 是一个顶点序列(v,vi,O,v,1,vi,2……vi,m,y),其中(vi,j 1,Vi,j)∈E,1sj≤m;如果G是有向图,则路径也是有向的 顶点序列,应满足<Vi2j-1,ⅵij∈E,1≤j≤m。 路径的长度:路径上的边或弧的数目。 回路或环:第一个顶点和最后一个顶点相同的路径。 简单路径:序列中顶点不重复出现的路径。 简单回路:一条简单路径,其长度≥2,且路径的起始点和 终止点是同一顶点的路径。 连通图:在无向图中,从顶点v到顶点v有路径,则称v和 v是连通的;如果图中任意两个顶点ⅵ,vj∈V,ⅵ和ⅵ都 是连通的,则称G是连通图
顶点的度：顶点的度TD（v）=ID（v）+OD（v）。 路径：无向图G = (V , E)中从顶点v到顶点v的路径(path) 是一个顶点序列(v,vi,0,vi,1,vi,2vi,m,v)，其中(vi,j- 1,vi,j)E，1jm；如果G是有向图，则路径也是有向的 顶点序列，应满足vi,j-1,vi,jE，1jm。 路径的长度：路径上的边或弧的数目。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路：一条简单路径，其长度2，且路径的起始点和 终止点是同一顶点的路径。 连通图：在无向图中，从顶点v到顶点v有路径，则称v和 v是连通的；如果图中任意两个顶点vi ，vjV，vi和vj都 是连通的，则称G是连通图
连通分量:无向图中极大连通子图。 6强连通图:有向图G中,如果对于每一对vⅵi,vj∈V, ⅵA,从ⅵ到ⅵ和从v倒到ⅵ都存在路径,则称G是强连 通图 强连通分量:有向图中的极大连通子图称为有向图的强 连通分量 实例: 3 G1 (a)无向图G5 (b)G5的三个连通分量
连通分量：无向图中极大连通子图。 强连通图：有向图G中，如果对于每一对vi,vjV， vivj ，从vi到vj和从vj到vi都存在路径，则称G是强连 通图。 强连通分量：有向图中的极大连通子图称为有向图的强 连通分量。 实例： (a) 无向图G5 (b)G5的三个连通分量
生成树:为一个极小连通子图,含有图中的全部顶点, 只有足以构成一棵树的n-1条边 实例:@ 有向树:一个有向图恰好有一个顶点入度为0,其余顶 点入度为1,则为有向树。 生成森林:有向图的生成森林由若干棵有向树组成,含 有图中全部顶点,只含有足以构成若干棵不相交的有向 树的弧
生成树：为一个极小连通子图，含有图中的全部顶点， 只有足以构成一棵树的n-1条边。 实例： 有向树：一个有向图恰好有一个顶点入度为0，其余顶 点入度为1，则为有向树。 生成森林：有向图的生成森林由若干棵有向树组成，含 有图中全部顶点，只含有足以构成若干棵不相交的有向 树的弧
图的存储结构 邻接矩阵 邻接表
图的存储结构 邻接矩阵 邻接表
邻接矩阵表示法 概念:用二维数组存储图中顶点的信息,用矩阵表示图 中各个顶点(数据元素)之间的关系(边或弧)的信息; 设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是 具有如下性质的n阶方阵: 1若(,V或<ⅵ,>是E中的边; A[]= 0若(,可或<V1,>不是E中的边 网的邻接矩阵:网G=(V,E含有n1)个顶点V (v1,V2,),则元素为: 4ii=W若(v,)《是E中的 若(,V或<v1,>不是E中的边
邻接矩阵表示法 概念：用二维数组存储图中顶点的信息，用矩阵表示图 中各个顶点（数据元素）之间的关系（边或弧）的信息； 设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是 具有如下性质的n阶方阵 ： 网的邻接矩阵：网G=(V，E)含有n(1)个顶点V= （v1,v2,vn），则元素为：