91图的基本概念的基本术语 端点獲接点,项点的度入度出度 对于无向图G=(V,E) 端点,接点:若存在边(v,v) ∈E,则称v和v为该边的两个端点, 并称他们互为新点。 边(vy则依附于顶点v和y,或者说 (vy)和顶点v和v相关联。 质点的度:和顶点相关联的边的数目, 记为d
启迪管理课程 6 9.1 图的基本概念－－图的基本术语 端点、邻接点；顶点的度、入度和出度 对于无向图G=(V,E), 端点、邻接点：若存在边（vi ,vj） ∈E,则称vi和vj为该边的两个端点， 并称他们互为邻接点。 边（vi ,vj )则依附于顶点vi和vj ,或者说 （vi ,vj ) 和顶点vi和vj 相关联。 顶点的度：和顶点相关联的边的数目， 记为d(V) 。 v1 v2 v4 v5 v3 G1
91图的基本概念的基本术语 对手有向图G=(VA),如果弧<vv>∈A, 则称顶点V邻接到顶点v,顶点v邻接自v。 入度:以顶点v为弧头的弧的数目,记为 id(v)。 出度:以顶点为孤尾的孤的数目,记为父 od (v)o ●顶点的度d=入度id+出度od 图的边与顶点的度的关系: e=2(m)
启迪管理课程 7 9.1 图的基本概念－－图的基本术语 对于有向图G=(V,A)，如果弧<v,v’>∈A， 则称顶点v邻接到顶点v’，顶点v’邻接自v。 ⚫ 入度：以顶点v为弧头的弧 的数目，记为 id(v)。 ⚫ 出度：以顶点v为弧尾的弧的数目，记为 od(v)。 ⚫ 顶点的度d=入度id+出度od ⚫ 图的边与顶点的度的关系： v1 v2 v3 v4 G1 = = n i i e d v 1 ( ) 2 1
91图的基本概念的基本术语 △°权和网 ●权( weight:与图的边或弧相关的数称之为权 ●网( Networκ):带权的图 △°子图 ●子图( Subgraph):假设有两个图G=(V,E和 2 G=(V,E),如果V≌V,E'≌E,则称G为G的子图。 ④ G (b) 8
启迪管理课程 8 9.1 图的基本概念－－图的基本术语 权和网 子图 ⚫ 权（weight) ：与图的边或弧相关的数称之为权 ⚫ 网（Nerwork）：带权的图 v1 v2 v3 5 1 2 ⚫子图（Subgraph)：假设有两个图G=(V,E)和 G’=(V’,E’), 如果V’V，E’ E，则称G’为G的子图。 3 5 6 2 4 5 1 3 6 2 1 2 4 G (a) (b) (c)
91图的基本概念的基本术语 席经和路经长度 路经:在无向图中,着存在一个顶点序列(v1v10, v1,v12…,MmY)其中v1,)∈E,1sm,则称页 点v到v存在一条路径。如果G是有向图,则路径也是 有向的,顶点序列应满足≮v1V1∈E,1≤m。 ●路经长度:路径上的边或弧的数目
启迪管理课程 9 9.1 图的基本概念－－图的基本术语 路径和路径长度 ⚫ 路径：在无向图中，若存在一个顶点序列(vi ,vi,0, vi,1,vi,2,…,vi,m,vj ),其中(vi,j-1 ,vi,j)∈E，1≤j≤m,则称顶 点v到v’存在一条路径。如果G是有向图，则路径也是 有向的，顶点序列应满足<vi,j-1 ,vi,j>∈E, 1≤j≤m 。 ⚫ 路径长度：路径上的边或弧的数目。 v1 v2 v4 v5 v3 G2 v1 v2 v3 v4 G1
91图的基本概念的基本术语 回路豆环 ●回路(环):第一个顶点和最后一个(y 顶点相同的路径。 篇单路经:若一条路径上除开始点和 结束点可以相同外,其余顶点均不相同,(v 则称此路径为简单路径。 G 简单回路(环):除了第一个顶点和 最后一个顶点之外,其余顶点不重复出 现的回路。 10
启迪管理课程 10 9.1 图的基本概念－－图的基本术语 回路或环 ⚫ 回路（环）：第一个顶点和最后一个 顶点相同的路径。 ⚫ 简单路径：若一条路径上除开始点和 结束点可以相同外，其余顶点均不相同， 则称此路径为简单路径。 ⚫ 简单回路（环）：除了第一个顶点和 最后一个顶点之外，其余顶点不重复出 现的回路。 v1 v2 v4 v5 v3 G2 v1 v2 v3 v4 G1