运筹学__八章__图与网络分析.ppt

第八章 图与网络分析 8.1图与网络的基本知识 8.2 树 8.3最短路径问题 8.4网络最大流问题 8.5最小费用最大流问题 图论的产生：1736年的“哥尼斯堡七桥问题”——十八世纪的东普鲁士哥尼斯堡城 哥尼斯堡七桥问题的网络分析 分类： 无向图：G（V，E）点集+边集 弧：点与点之间有方向的边，叫做弧。弧集：A={a1,a1,…,am} 有向图：由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。 环：某一条孤起点=终点，称为环。 基础图：给定一个有向图D=(V,A) ，从D中去掉所有弧上的箭头，所得到的无向图。记之为G(D)。 链：设(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。 路：如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一条链，并且对t=1,2,…,k-1，均有ait=(vit,vit+1)，称之为从vi1到vik的一条路。 回路：若路的第一个点和最后一点相同，则称之为回路。 2、顶点的次 次：图中的点V，以V为端点的边的个数，称为V的次，记为d(V)。 定理1：图G=(V,E)中，所有点的次之和是边数的两倍，即设边数为q ，则Σd(vi)=2q ，其中vi?V 奇点：次为奇数的点。否则称为偶点。 任一图中，奇点的个数为偶数。 一笔划： 可以一笔划：没有或仅有两个奇次点的图形 如没有奇次点：任取一点，它既是起点又是终点。 两个奇次点：分别选为起点和终点。 二、连通图 1、链：给定一个图G=(V,E)，一个点边的交错序列(vi1, ei1, vi2, ei2,…,vik-1,eik-1,vik)，如果满足eit=[vit,vit+1] (t=1,2,…,k-1)，则称为一条联结vi1和vik的链，称点vi2, vi3,…,vik-1为链的中间点。 2、圈：链(vi1,vi2,…,vik)中，若vi1=vik,，则称之为一个圈。 3、简单链：若链(vi1,vi2,…,vik)中，点vi1,vi2,…,vik都是不同的，则称之为简单链。 4、连通图：图G中，若任何两个点之间，至少有一条链。否则为不连通图。 三、图的矩阵表示 1、赋权图：给图G=(V,E) ，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图G为赋权图，wij称为边[vi,vj]上的权。 2、网络（赋权图）G=（V，E），其边（vi,vj）有权wij, 构造矩阵A=（aij）n×n,其中： aij= wij（vi,vj）∈E 0 其他 称矩阵A为网络G的权矩阵。如P239，例2 3、对于图G=（V，E）， ∣V ∣=n,构造一个矩阵A=（aij）n×n,其中： aij= 1（vi,vj）∈E 0 其他 称矩阵A为图G的邻接矩阵。如P239，例3 四、欧拉回路与中国邮路问题 1、欧拉回路与道路：连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路，具有欧拉回路的图也称欧拉图。 仅当无向连通图G中无奇点时是欧拉图，仅当恰有两个奇点时为欧拉道路； 仅当有向连通图G中每个顶点的出次等于入次时是欧拉图，仅当两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点出次多1，另一个顶点入次多1时为欧拉道路； 2、中国邮路问题：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。 8.2 树（是最简单又十分重要的图）例如：比赛中的相遇情况、组织结构图、家庭树 3、生成树：设图T=(V,E’) 是图G（V，E）的子图，如果图T=(V, E’) 是一个树，则称T是G的一个支撑树。 4、寻找生成树的方法 1）破圈法：在图中任取一个圈，从圈中去掉任一边，对余下的图重复上述操作，即可得到一个支撑树。 2）避圈法：每一步选取与已选的边构不成圈的边，直到不能继续为止。（深探法＋广探法－阅读内容） 2）求最小树的方法： 方法一(避圈法) 开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。 方法二(破圈法) 任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。 6、根树及其应用 定义17：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。 定义18：有向树T，恰有一个结点入次为