运筹学课件第八章图与网络分析.ppt

总结:图的基本概念 1.思考题 子图与生成子图的区别是什么？ 2.讨论题 中国邮路问题的解题步骤？ 小结: 1.图的基本知识。 2.图的矩阵表示。 3.欧拉道路与欧拉回路。 v1 v3 v2 v4 v6 v5 e1 e3 e5 e6 e4 e8 e7 e2 V= （ v1， v2，…... v6） E= （ e1， e2，…... e8） （e1）= （v1， v2） （e2）= （v1， v2） （e7）= （v3， v5） （e8）= （v4， v4） (e8)= (v4， v4),称为自回路(环)； v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为4，顶点v4的次为4。 定理1 在一个图中，所有顶点次的和等于边的两倍。 定理2 在任意一个图中，次为奇数的顶点必为偶数个。 定义6：有向图中，以vi为始点的边数称为点vi的出次，d+(vi); 以vi为终点的边数称为点vi的入次，d-(vi); 所有顶点的入次之和=所有顶点的出次之和； 3、子图 定义：设G=（V，E）和G1=（V1，E1）。 如果V1 ? V， E1 ? E则称G1为G的子图； 如果G1 =（ V1，E1 ）是G=（V，E）子图，并且V1 = V，则称G1为G的生成子图； v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 v1 v5 v4 v2 e1 e5 e3 （a）的子图 v1 v5 v4 v2 v3 e8 e6 e5 e2 （a）的生成子图 二、连通图 定义8:如果图中的某些点、边可以排列成点和边的交错序列(v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,…,vn-1 , en ， vn ） ，ei=(vi-1,vi)，则称此为一条链。 由两两相邻的点及其相关联边构成的点边序列。 初等链：链中无重复的点和边； 定义9：无向图中，如一条链中起点和终点重合，则称此链为圈。 初等圈：圈中无重复的点和边； 有向图中，当链（圈）上的边方向相同时，为道路（回路）。 道路 道路 回路 链 初等链 初等圈 链、初等链、初等圈 道路、回路 连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 链 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 圈 三、图的矩阵表示 一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。 1、邻接矩阵 邻接矩阵A表示图G的顶点之间的邻接关系，它是一个nxn的矩阵，如果两个顶点之间有边相联时，记为1，否则为0。 定义12：对于G=(V,E)，构造矩阵A=(aij)nxn aij= 1, （vi,vj） E 0 矩阵A为邻接矩阵。 V1 V3 V5 V6 V4 V2 v1 v2 v3 v4 v5 v6 2、权矩阵 在图的各边上一个数量指标，具体表示这条边的权（距离，单价，通过能力等），以边长代替邻接矩阵中的元素得到边长邻接矩阵。 定义11：赋权图G=(V,E)，其边（vi,vj）有权wij,构造矩阵A=(aij)nxn aij= wij, （vi,vj） E 0 矩阵A为权矩阵。 v1 v2 v5 v4 v3 9 2 4 3 8 6 7 4 5 v1 v2 v3 v4 v5 四、欧拉回路与中国邮政问题 1、欧拉回路与道路 定义13：连通图G，如果存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路； 如果存在一条回路，经过每边一次且仅一次，则称这条路为欧拉回路； 具有欧拉回路的图为欧拉图。 定理3：无向连接图G是欧拉图，当且仅当G中无奇 点。 推论