2、>,,,,,}EACBD第4页7.1图的术语与定义图的定义无向图——无向图G是由两个集合V(G)和E(G)组成的。其中:V(G)是顶点的非空有限集。E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)。第5页7.1图的术语与定义例如:G2=V2={v0,v1,v2,v3,v4}E2={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}V0V4V3V1V2第6页7.1图的术语与定义例如:G2=3、2,E2>V2={v0,v1,v2,v3}E2={,,,}例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>}V0V1V2V3第7页7.1图的术语与定义图的应用举例例1、交通图(公路、铁路)顶点:地点边:连接地点的路例2、电路图顶点:元件边:连接元件之间的线路例3、通讯线路图顶点:地点边:地点间的连线例4、各种流程图如产品的生产流程图。顶点:工序边:各道工序之间的顺序关系第8页7.1图
4、的术语与定义图的基本术语1邻接点及关联边邻接点:边的两个顶点关联边:若边e=(v,u),则称顶点v、u关连边e2顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中:顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n,边数为e图的所有顶点的度数和=2*e(每条边对图的所有顶点的度数和“贡献”2度)V0V4V3V1V2eV0V1V2V3第9页7.1图的术语与定义路径、回路无向图G=(V,E)中的顶点序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1
5、,u=vk,则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。有向图D=(V,E)中的顶点序列v1,v2,…,vk,若E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。第10页7.1图的术语与定义例如在图G1中,V0,V1,V2,V3是V0到V3的路径;V0,V1,V2,V3,V0是回路。在图G2中,V0,V2,V3是V0到V3的路径;V0,V2,V3,V0是回路。无向图G1有向图G2V0V4V3V1V2V0V1V2V3第11页7.1图的术语与定义连通图(
6、强连通图)在无(有)向图G=中,若对任何两个顶点v、u都存在从v到u的路径,则称G是连通图(强连通图)非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4第12页7.1图的术语与定义子图设有两个图G=(V,E),G1=(V1,E1),若V1V,E1E,E1关联的顶点都在V1中,则称G1是G的子图;例(b)、(c)是(a)的子图(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2第13页7.1图的术语与定义连通分图(强连通分量)无向图G的极大连通子图称为G的
7、连通分量。极大连通子图意思是:该子图是G连通子图,将G的任何不在该子图中的顶点加入,子图不再连通。连通分图非连通图V0V2V3V1V5V4第14页7.1图的术语与定义连通分图(强连通分量)有向图D的极大强连通子图称为D的强连通分量。极大强连通子图意思是:该子图是D强连通子图,将D的任何不在该子图中的顶点加入,子图不再是强连通的。强连通分量V0V1V2V3V0V2V3V1第15页7.1图的术语与定义生成树包含无向图G所有顶点的极小连通子图称为G生成树。极小连通子图意思是:该子图是G的连通子图,在该子图中删除任何一条边,子图不再连通,若T是G的生成树当且
8、仅当T满足如下条件:T是G的连通子图T包含G的所有顶点T中无回路连通图G1G1的生成树V0V4V3V1V2V