图与网络分析精选PPT演示文稿

第八章图与网络 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 第一节图与网络的基本知识第二节树第三节最短路问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 第四节最大流问题第五节最小费用流问题（一）哥尼斯堡七桥难题1736年瑞士数学家欧拉（E.Euler）在求解七桥一笔画难题时，就用了点线图来分析论证：每个点均有奇数条边时，一笔画问题无解。（要求不重边）（二）“环球旅行”问题1857年，英国数学家哈密尔顿(Hamilton)发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。（要求不重点）（三）“中国邮路问题”一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个问题就与欧拉回路有密切的关系。第一节图与网络的基本知识一、图与网络的基本概念（一）图及其分类5家企业业务往来关系由上面的例子可以看出，这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。工人与需要完成的工作电路网络城市 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 交通运输、信息传递、物资调配定义1一个图是由点集V={vi}和V中元素的无序对的一个集合E＝{ek}所构成的二元组，记为G＝(V,E)，V中的元素vi叫做顶点，E中的元素ek叫做边。当V,E为有限集合时，G称为有限图，否则，称为无限图。两个点u,v属于V，如果边(u,v)属于E，则称u,v两点相邻。u,v称为边(u,v)的端点。两条边ei,ej属于E，如果它们有一个公共端点u，则称ei,ej相邻。边ei,ej称为点u的关联边。用m(G)＝|E|表示图G中的边数，用n(G)＝|V|表示图G的顶点个数。在不引起混淆情况下简记为m,n。对于任一条边(vi,vj)属于E，如果边(vi,vj)端点无序，则它是无向边，此时图G称为无向图。如果边(vi,vj)的端点有序，即它表示以vi为始点，vj为终点的有向边(或称弧)，这时图G称为有向图一条边的两个端点如果相同．称此边为环(自回路)。两个点之间多于一条边的，称为多重边。定义2不含环和多重边的图称为简单图，含有多重边的图称为多重图。定义3每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作Kn。有向完全图则是指每一对顶点间有且仅有一条有向边的简单图。定义4图G＝(V,E)的点集V可以分为两个非空子集X,Y，即XUY＝V，XY＝，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y．则称G为二部图(偶图、二分图)，有时记作G＝(X,Y,E)。（二）顶点的次（度）定义5以点v为端点的边数叫做点v的次。记作deg(v)，简记为d(v).次为1的点称为悬挂点。连结悬挂点的边称为悬挂边。次为零的点称为孤立点。次为奇数的点称为奇点。次为偶数的点称为偶点。定理1任何图中，顶点次数的总和等于边数的2倍。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所顶点次数的总和等于边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：设V1和V2分别为图G中奇点与偶点的集合(V1∪V2=V)。由定理1知：偶数偶数偶数定义6有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示，以vi为终点的边数称为点vi的入次，用d-(vi)表示。vi点的出次与入次之和就是该点的次。容易证明有向图中，所有顶点的入次之和等于所有顶点的出次之和。（三）子图定义7图G＝(V,E)，若E'是E的子集，V'是V的子集，且E'中的边仅与V'中的顶点相关联，则称G'＝(V',E')是G的一个子图。特别地，若V'＝V,则G'称为G的生成子图(支撑子图)。（四）网络在实际问题中，往往只用图来描述所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，我们常称之为“权”，权可以代表如距离、费用、通过能力(容量)等等。这种点或边带有某种数量指标的图你为网络(赋权间)。点边列中没有重复的点和重复的边者为初等链。定义9无向图G中,连结与的一条链,当与是同一个点时,称此链为圈。圈中既无重复点也无重复边者为初等圈。（1）对于有向图可以类似于无向图定义链和圈、初等链，此时不考虑边的方向。而当链(圈)上的边方向相同时,称为道路(回路)。（2）对于无向图来说，道路与链、回路与圈意义相同。定义10一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为一个分图。三、图的矩阵表示图的矩阵表示 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 有权矩阵、邻接矩阵、关联矩阵、回路矩阵、割集矩阵等。定义11网络（赋权图）G=（V，E），其中边(vi,vj)有权wij,构造矩阵A=(aij)nn,其中则称A为网络G的权矩阵例：写出上图的权矩阵。定义12对于图G=（V，E），|V|=n，构造一个矩阵A=(aij)nn，其中：则称A为图G的邻接矩阵例：邻接矩阵表示上图。v5四、欧拉回路与中国邮路问题（一）欧拉回路与道路定义13连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次则称这条回路为欧拉回路。欧拉图含有欧拉回路。定理3无向连通图G是欧拉图，当且仅当G中无奇点。推论1无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。定理4连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。（二）中国邮路问题一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？这个问题是我国管梅谷教授在1962年首先提出的。因此国际上通称为中国邮路问题。用图论的语言描述：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。第二节树一、树的概念和性质（一）几个树的例子（1）乒乓球单打比赛抽签后，可用图来表示。（2）某企业的组织结构。（二）定义14：连通且不含圈的图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。（三）树的性质定理6图T=（V，E），|V|=n，|E|=m，则下列关于树的说法是等价的。（1）T是一个树。（2）T无圈，且m=n-1。（3）T连通，且m=n-1。（4）T无圈，但每加一新边即得惟一一个圈。（5）T连通，但任舍去一个边就不连通。（6）T中任意两点，有惟一链相连。树的性质①任何树必有树叶(即次数为1的节点)。②树中任意两点之间有且仅有一条链连接相通。任意去掉一条树枝，该树就被分割成两互不连通的子图。③树的任意两个顶点间添加一条边（称为连枝），就构成一个回路。仅用一条连枝构成的回路称为单连枝回路，也称为基本回路④一连通图可能具有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。⑤连枝的集合是原连通图相应的余树，或称补树。余树可能是树，也可能不是树，甚至是非连通图。二、图的生成树定义15若图G的生成子图是一棵树，则称该树为G的生成树(支撑树)。或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边际为弦。定理7图G＝(V，E)有生成树的充分必要条件为G是连通图。寻找生成树的方法（1）深探法步骤如下（用标号法）①在点集V中任取—点v。给v以标号0。②若某u点已得标号i，检查一端点为u的各边，另一端点是否均已标号。若有(u，w)边之w未标号，则结w以标号i十1，记下边(u，w)。今w代u，重复②。若这样的边的另一端点均已有标号，就退到标号为i-1的r点，以r代u，重复②。直到全部点得到标号为止。例：试用深探法求下图中的一棵生成树012345678910111213（2）广探法步骤如下：①在点集V中任取一点v，给v以标号0。②令所有标号为i的点集为Vi，检测查[Vi，V＼Vi]中的边端点是否均已标号。对所有未标号之点均标以i+1，记下这些边。③对标号i+1的点重复步骤②，直到全部点得到标号为止。例：用广探法求上图中的一棵生成树。三、最小生成树问题定义16连通图G＝(V，E)、每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树(最小支撑树)简称最小树。算法1(Kruskal算法)（1）将所有的边按从小到大的顺序排列（2）将每条边加入到生成子图中，如构成圈则舍去。（3）重复（2）过程，直到所有的边试验完毕。将边按权从小到大排序(v2,v3),(v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4),(v3,v6),(v3,v4),(v1,v3),(v1,v2)将边加入到新图中,如不构成回路则保留;否则,去掉.例：求下图的一棵最小支撑树(v2,v3),(v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4),(v3,v6),(v3,v4),(v1,v3),(v1,v2)其权为：19定理8用Kruskal算法得到的子图T*＝(e1,e2,…,en-1)是一棵最小树。算法2（破圈法）（1）从图G中任选一棵树T1。（2）加上一条弦e1，T1+e1中立即生成一个圈。去掉此圈中最大权边，得到新树T2。以T2代T1，重复（2）再检查剩余的弦，直到全部弦检查完毕为止。例：用破圈法求上图中的一棵最小生成树。定理9图G的生成树T为最小树，当且仅当对任一e来说，e是T+e中与之对应的圈e中的最大权边。四、根树及其应用定义17若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。定义18有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树（又称外向树）。根树中入次为0的点称为根。根树中出次为0的点称为叶，其他顶点称为分枝点。由根到某一顶点vi的道路长度（设每边长度为1），称为点vi的层次。定义19在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。在实际问题中常讨论叶子上带权的二叉树。令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i＝1，…，s)，这样二叉树T的总权数满足总权最小的二叉树称为最优二叉树。霍夫曼(DAHuffman)给出了一个求最优二叉树的算法，所以又称霍夫曼树。算法步骤为：（1）将s个叶子按权由小至大排序，不失一般性，设p1≤p2≤…≤ps。（2）将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2，将新的分枝点作为一个叶子。令ss-1，若s＝1停止，否则转（1）例8S=6，其权分别为4,3,3,2,2,1，求最优二叉树。例9最优检索问题。使用计算机进行图书分类。现有五类图书共l00万册，其中有A类50万册，B类20万册，C类5万册，D类l0万册，E类15万册。问如何安排分检过程，可使总的运算（比较）次数最小?