文档介绍：图的术语与定义?图的定义?图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)?其中:V(G)是顶点的非空有限集? E(G)是边的有限集合,边是顶点的无序对或有序对。?图的分类?有向图? 图的术语与定义?图的定义?有向图——有向图G是由两个集合V(G)和E(G)组成的。?其中:V(G)是顶点的非空有限集。? E(G)是有向边(也称弧)(的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为弧尾,w为弧头。图的术语与定义?例如:? G1 = <V2,E2>? V1 = { A, B, C, D, E }? E1 = {<A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> } 图的术语与定义?图的定义?无向图——无向图G是由两个集合V(G)和E(G)组成的。?其中:V(G)是顶点的非空有限集。? E(G)是边的有限集合,边是顶点的无序对,记为(v,w) 或(w,v),并且(v,w)=(w,v)。图的术语与定义?例如:? G2 = <V1,E1>? V2 = { v0 ,v1,v2,v3,v4 } ?E2 = { (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) } 图的术语与定义?例如:? G2 = <V2,E2>? V2 = { v0,v1,v2,v3 }? E2 = { <v0,v1 >, <v0,v2 >, <v2,v3 >, <v3,v0 > }?例245136G1图G1中:V(G1) = { 1 , 2 , 3 , 4 , 5, 6 } E(G1) = { <1,2> , <2,1> , <2,3> , <2,4> , <3,5> , <5,6> , <6,3> } 图的术语与定义?图的应用举例?例1、交通图(公路、铁路)?顶点:地点边:连接地点的路?例2、电路图?顶点:元件边:连接元件之间的线路?例3、通讯线路图?顶点:地点边:地点间的连线?例4、各种流程图?如产品的生产流程图。?顶点:工序边: 图的术语与定义?图的基本术语?1 邻接点及关联边?邻接点:边的两个顶点?关联边:若边e= (v, u), 则称顶点v、u 关连边e?2 顶点的度、入度、出度顶点V的度= 与V相关联的边的数目?在有向图中:?顶点V的出度= 以V为起点有向边数?顶点V的入度= 以V为终点有向边数?顶点V的度= V的出度+V的入度?设图G 的顶点数为 n,边数为 e?图的所有顶点的度数和= 2*e?(每条边对图的所有顶点的度数和“贡献”2度) 图的术语与定义?路径、回路?无向图 G =(V,E)中的顶点序列v1, v2, …,vk,若(vi,vi+1)?E ( i=1, 2 ,… k-1), v=v1, u=vk,则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。?有向图 D =(V,E)中的顶点序列v1, v2, …, vk,若<vi,vi+1>?E (i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。