7.1图的定义和术语 2.完全图 边达到最大的图 无向完全图:边数为n(n-1)2的无向图 有向完全图:弧数为n(n-1)的有向图 权:与图的边或弧相关的数 网:边或弧上带有权值的图
7.1 图的定义和术语 2. 完全图 边达到最大的图 • 无向完全图：边数为n(n-1)/2的无向图 • 有向完全图：弧数为n(n-1)的有向图 权：与图的边或弧相关的数 网：边或弧上带有权值的图
7.1图的定义和术语 3.顶点的度TD(v) 无向图:为依附于顶点V的边数 有向图无向图的度数为依附于顶点v为V的入度,记 的边数;有向图的度数等于以的弧数(称为v 顶点v为弧头的弧数与以顶点v即: 结论:为弧尾的弧数之和 无向图 有向图 e=1/2(∑TD(v) ∑ID(v)=∑0D(v)
7.1 图的定义和术语 3. 顶点的度TD（V） 无向图：为依附于顶点V的边数 有向图：等于以顶点V为弧头的弧数（称为V的入度，记 为ID（V））与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V））之和。即： TD（V）=ID（V）+OD（V） • 无向图 n e= 1/2（∑TD(vi)） i=1 结论： • 有向图 n n e= ∑ID(vi)=∑OD(vi) i=1 i=1 无向图的度数为依附于顶点v 的边数；有向图的度数等于以 顶点v 为弧头的弧数与以顶点v 为弧尾的弧数之和
7.1图的定义和术语 4.路径 无向图:顶点v到v的路径是一个顶点序列(v=VaV,,vmrv) 其中,(w,v)∈E,1<j=m 有向图:顶点v到v的路径是有向的顶点序列(v=vmVm,,iwm=y) 其中,(v、)∈A,1<=j<=m 几个概念: 路径长度:路径上边或弧的数目 回路或环:首尾顶点相同的路径,称为回路或环。即: (v=v0,vil,… 简单路径:路径中不含相同顶点的路径 简单回路:除首尾顶点外,路径中不含相同顶点的回路
7.1 图的定义和术语 4. 路径 无向图：顶点v到v’的路径是一个顶点序列（v=vi0, vi1, … , vim=v’） 其中，（vij-1,vij）∈E, 1<=j<=m 有向图： 顶点v 到v’的路径是有向的顶点序列（v=vi0, vi1, … , vim=v’） 其中，（vij-1,vij）∈A, 1<=j<=m 几个概念： 路径长度：路径上边或弧的数目 回路或环：首尾顶点相同的路径，称为回路或环。即： （v=vi0, vi1, … , vim=v’=v） 简单路径：路径中不含相同顶点的路径 简单回路：除首尾顶点外，路径中不含相同顶点的回路
7.1图的定义和术语 5.连通 顶点连通:若顶点v到顶点v有路径,则称顶点v与v是连通的 连通图:包括无向连通图和有向连通图 无向图:若图中任意两个顶点ⅵv都是连通的,则称该图 是连通图v∞vj) 有向图:若图中任意两个顶点ⅵ,都存在从v到v和从 ⅵ到v的路径,则称该有向图为强连通图<vj) 连通分量: 无向图:无向图中极大连通子图,称为连通分量 有向图:有向图中极大强连通子图,称为强连通分量
7.1 图的定义和术语 5. 连通 顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的 连 通 图 ：包括无向连通图和有向连通图 无向图：若图中任意两个顶点vi,vj都是连通的，则称该图 是连通图(vi<>vj) 有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从 vj到vi的路径，则称该有向图为强连通图(vi<>vj) 连通分量： 无向图：无向图中极大连通子图，称为连通分量 有向图：有向图中极大强连通子图，称为强连通分量
7.1图的定义和术语 5.连通 连通分量: ② G1有两个强连通分量
7.1 图的定义和术语 5. 连通 连通分量： ① ② ③ ④ G1有两个强连通分量 ① ② ③ ④ G1