图的概念 第七章图 图常用来解决的九类主要问题 1.模拟计算机与通信网络的联接 2表示一张地图的一组坐标以及坐标之间的距离,以 一求得最短路径; 3.模拟交通网络的流量 4寻找从开始状态到目标状态的路径,如人工智能间 题求解; 5.模拟计算机算法,显示程序状态的变化; 6.为复杂活动各子任务的完成寻找顺序,如大型建筑 的建造; 第6页
第七章 图 第6页 图常用来解决的几类主要问题 1. 模拟计算机与通信网络的联接； 2. 表示一张地图的一组坐标以及坐标之间的距离，以 求得最短路径； 3. 模拟交通网络的流量； 4. 寻找从开始状态到目标状态的路径，如人工智能问 题求解； 5. 模拟计算机算法，显示程序状态的变化； 6. 为复杂活动各子任务的完成寻找顺序，如大型建筑 的建造； … … … … ⚫ 图的概念
0图的定义 第七章图 定义:图是一种数据结构,它的形式化定义为 Graph=(V,R 其中 V={xx∈ dataobject} RVR VR={<xyxP(xy)∧(x,y∈V)} 可以简记为 G=(V, E 其中V是顶点的有穷非空集合,E是中顶点的偶 对(称为边)的有穷集。 通常亦可将图G的顶点集和边集分别记作V(G)和 E(G)。 若E(G)为空集,则表示图G仅有顶点而没有边 第7页
第七章 图 第7页 定义： 图是一种数据结构，它的形式化定义为 Graph=(V,R) 其中 V={x|x∈dataobject} R={VR} VR={＜x,y＞| P(x,y)∧(x,y ∈V)} 可以简记为 G=（V，E） 其中V是顶点的有穷非空集合，E是V中顶点的偶 对（称为边）的有穷集。 通常亦可将图G的顶点集和边集分别记作V(G)和 E(G)。 若E(G)为空集，则表示图G仅有顶点而没有边。 ⚫ 图的定义
图的定义 第七章图 示例1有向图G1和无向图G2 V2 V( G1)={v12V2V32V4} G EG1)={ 3>,V3,Y4>V4,V1 V(G2)={v1,v2V3,V42v5} E(G2)={(V1V2)v1,V4)2(V2V3),(V2vs)(v3V4)、(v3,V3)} 第8页
第七章 图 第8页 示例1 有向图G1和无向图G2 G1 G2 ⚫ 图的定义 V(G1 )={v1 ,v2 ,v3 ,v4} E(G1 )={<v1 ,v2>,<v1 ,v3>, <v3 ,v4>,<v4 ,v1>} V(G2 )={v1 ,v2 ,v3 ,v4 ,v5} E(G2 )={(v1 ,v2 ),(v1 ,v4 ), (v2 ,v3 ),(v2 ,v5 ),(v3 ,v4 ),(v3 ,v5 )} V1 V2 V3 V4 V1 V2 V4 V5 V3
图的术语 第七章图 顶点:图中的数据元素。 弧:有向边,用以尖括号括起来的有序对<v,y>表示 弧尾:有向边vy>的始点v 弧头:有向边<vy>的终点v 有向图:图G中每条边都是有向边(弧) 无向图:图G中每条边都是没有方向的,这些边用以二 vY)形式的无序对表示 第9页
第七章 图 第9页 顶点：图中的数据元素。 弧：有向边，用以尖括号括起来的有序对<vi ,vj>表示。 弧尾：有向边<vi ,vj>的始点vi。 弧头：有向边<vi ,vj>的终点vj。 有向图：图G中每条边都是有向边（弧）。 无向图：图G中每条边都是没有方向的，这些边用以 (vi ,vj )形式的无序对表示。 ⚫ 图的术语 V1 V2 V3 V4 V1 V2 V4 V5 V3
图的术语 第七章图 图的顶点数n和边数e的关系:对有向图,0≤e≤m(n-1);对无 向图,0≤c5mm 有向完全图:恰有n(n-1)条有向边(即弧)的有向图 无向完全图:恰有2mn-1)条无向边的无向图 稀疏图:图中边或弧的数目e<<n?2 稠密图:图中边或弧的数目e~n2(准确地说,无向图的e接近 于2(m-1)有向图的e接近于n(m-1) 第10页
第七章 图 第10页 图的顶点数n和边数e的关系：对有向图，0≤e≤n(n-1)；对无 向图， 。 有向完全图：恰有n(n-1)条有向边（即弧）的有向图。 无向完全图：恰有 条无向边的无向图。 稀疏图：图中边或弧的数目e<<n2 。 稠密图：图中边或弧的数目e≈n2（准确地说，无向图的e 接近 于 ，有向图的e接近于n(n-1)。 ( 1) 2 1 0 e n n − ( 1) 2 1 n n − ( 1) 2 1 n n − ⚫ 图的术语 V1 V2 V3 V4 V1 V2 V4 V5 V3