图(网络版).pptVIP

2000年1月25日 北京理工大学 / 主要内容 图的基本概念 图的遍历 图的连通性与最小生成树 13.1 图的基本概念 图的定义 图(Graph)——图G是由两个集合V(G)和E(G)组成的，记为G=(V，E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。 图的分类 有向图 无向图 有向图与无向图 若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。 完全图 对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1) ，则称其为有向完全图。 邻接顶点 若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（vi,vj）与顶点vi和vj相关联。 13.1 图的基本概念 图的定义 有向图——有向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v，w，v，w是顶点，v为弧尾，w为弧头。 13.1 图的基本概念 例如： G1 = V1，E1 V1 = { A，B，C，D，E } E1 = {A，B，A，E，B，C，C，D，D，B，D，A，E，C } 13.1 图的基本概念 图的定义 无向图——无向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的无序对，记为 (v，w) 或 (w，v)，并且(v，w)=(w，v)。 13.1 图的基本概念 例如： G2 = （V2，E2） V2 = { v0，v1，v2，v3，v4 } E2 = { (v0，v1)，(v0，v3)，(v1，v2)，(v1，v4)，(v2，v3)，(v2，v4) } 13.1 图的基本概念 例如： G2 = V2，E2 V2 = { v0，v1，v2，v3 } E2 = { v0，v1 ，v0，v2 ，v2，v3 ，v3，v0 } 13.1 图的基本概念 图的应用举例 例1、交通图（公路、铁路） 顶点：地点 边：连接地点的路 例2、电路图 顶点：元件 边：连接元件之间的线路 例3、通讯线路图 顶点：地点 边：地点间的连线 例4、各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 13.1 图的基本概念 图的基本术语 1 邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v，u)，则称顶点v、u 关联边为e 2 顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度 = 以V为起点有向边数 顶点V的入度 = 以V为终点有向边数 顶点V的度 = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） 13.1 图的基本概念 路径、回路 无向图 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，则称该序列为回路。 13.1 图的基本概念 例如 在图G1中，V0，V1， V2，V3 是 V0 到 V3 的路径；V0，V1，V2，V3，V0 是回路。 在图G2中，V0，V2，V3 是 V0 到 V3 的路径； V0，V2，V3，V0 是回路。 13.1 图的基本概念 连通图（强连通图） 在无（有）向图 G=（V，E） 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称G是连通图（强连通图） 13.1 图的基本概念 子图 设有两个图 G=（V，E），G1=（V1，E1），若V1? V，E1 ? E，则称 G1 是 G 的子图； 例 (b)、(c) 是 (a) 的子图 13.1 图的基本概念 连通分量（强连通分量） 无向图G的极大连通