图与网络分析(4课时)起讫点不同最短路最大流问题

1、运筹学，第六章图论和网络分析，图和模型树的基本概念和图的最短路径问题网络的最大流，本章的主要内容：现代图论的历史可以追溯到18世纪的七座桥的问题在克尼斯堡市通过七座桥需要每座桥通过一次，而且只能通过一次。这就是著名的“哥尼斯堡7号桥”问题。欧拉1736在1736年证明了这样的路线不可能存在。图的基本概念和模型，图对应于Knigsberg桥，图论中的图是由点和边组成的，它能反映一些对象之间的关系。通常，反映对象之间的关系并不重要，例如图中各点的相对位置以及点之间连接线的长度和直线度。图形定义：如果研究对象用点表示，这些对象之间的关系用边表示，那么图形g可以定义为一组点和边，表示为：其中：V335

2、4点集E边集，在这里，我们只关心图中有多少点以及哪些点有联系。图的基本概念和模型，可以看出图论中的图不同于几何图和工程图。例如，在人群中，我们可以用图片来表达相互了解的关系。图的基本概念和模型定义了：图中的点用v表示，边用e表示。每条边可以用它所连接的点表示，表示为e1=v1，v1；e2=v1，v2；端点、关联边和相邻边。如果有一条边E，它可以表示为e=vi，vj，那么vi和vj是边E的端点，反之，边E是点vi或vj的相关边。如果点vi和vj与同一条边相关联，则点vi和vj被称为相邻；如果边ei和ej有一个公共端点，则称边ei和ej是相邻的。图的基本概念是模型、环、多边、简单图。如果边E的两个

3、端点重叠，这条边称为环。如右图所示，边e1是一个环。如果两点之间有一个以上的点，称为多条边，如右图中的e4和e5，没有循环和多条边的图称为简单图。图的基本概念和模型，度，奇点，偶点，孤立点，与某一点vi相关的边数称为点vi的度，也称为d(vi)。在右图中，d (v1)=4，d (v3)=5，d (V5)=1。奇数编号的点称为奇点，偶数编号的点称为偶数点，1编号的点称为悬挂点，0编号的点称为孤立点。图形的度数等于每个点的度数之和。图和模型、链、圈、连通图、图中某些点和边的交替序列的基本概念，其中边彼此不同并且与任何vi、t-1和vit相邻，称为链。对于，起点和终点重合的链称为圆。如果每对顶点之间

4、至少有一条链，这种图称为连通图；否则，图形被称为未连接的。图、子图、部分图(支持子图)、图G1=V1，E1和图G2=V2，E2的基本概念和模型。如果是这样，G1是G2的部分图(支持子图)。(a)，(b)，(G图)，图的基本概念和模型，网络(加权图)，让图g=(v，e)，给G的每条边(vi，vj)一个相应的定量指标wij，它被称为边(vi，vj)，而加权图G被称为网络(或权重可以表示距离，成本，通过能力(capacity)等)。端点无序的加权图称为无向网络，端点有序的加权图称为有向网络。图形的基本概念和模型，出现的程度和出现的程度。在有向图中，以vi为起点的边数称为点vi的出现度，用d (vi)

5、表示。以vi为端点的边数称为vi点的进入度，用来表示D-(VI)；在第六点出入的次数之和就是那个点的次数。在有向图中，所有顶点的引入时间之和等于所有顶点的引出时间之和。图形的基本概念和模型，以及图形模型的应用。在例6.1中，来自A、B、C、D和F的六名运动员报名参加了比赛如果同一个运动员参加了两个项目，在代表这两个项目的点之间连接一条线，得到下图。在图中找到一个点序列，这样依次排列的两个点就不相邻了，这就可以满足要求。例如：1)A，C，B，F，E，D的基本概念和模型2) D，E，F，B，C，A，一个班的学生选修六门课程，A，B，C，D，E和F，其中一些同时选修D，C和A，而另一些同时选修B和A

6、。思考问题，图形的基本概念和模型，以及思考问题：以每门课程为顶点，把所有的课程用边连接起来，得到图形。根据问题的含义，相邻顶点对应的课程不能连续测试，而非相邻顶点对应的课程允许连续测试。因此，画一个补图的问题是在图中找到一条哈密尔顿路，如C-E-A-F-D-B。图、A、F、E、D、C、B、A、F、E、D、C、B、定理2的基本概念和模型在任何图中，都必须有奇数个偶数个顶点。证明了由于每条边必须与两个顶点相关联，所以在计算点的度数时，每条边被计算两次，所以顶点的度数之和等于边数的两倍。证明了V1和V2分别是图G中的奇点和偶点集。根据定理1，2m是偶数，偶数点的第二个和是偶数，所以它必须是偶数，也就

7、是说，奇数点的数量必须是偶数。图形的基本概念和模型，图形的矩阵描述：如何在计算机中存储图形？现在有很多存储方法，但最基本的方法是用矩阵来表示一个图形。图的矩阵表示还包括邻接矩阵、关联矩阵、权重矩阵等。1。对于图G=(V，E)，| V |=n，| E |=m的邻接矩阵，有一个平方矩阵a=(AIJ) nn的阶nn，其中图的基本概念和模型，例6.2，下图所示的图可以如下构造邻接矩阵a，而对于加权图G=(V，E)，其中边是加权的。2.对于图G=(V，E)，| V |=n，| E |=m，存在Mn阶矩阵M=(mij) Mn，其中：3。权重矩阵，图形的基本概念和模型， 1 0 1 0 0 0 0 0 0

8、0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 000011 10001001 10000， v1v2 v3 v4 vv6 V7 V8，E1 e2e 3e 4e E6 e 7 E8 e9 e 10 e 11 e 12，例6.3下图所示的图可以如下构造邻接矩阵M:M=(mij)=图的基本概念和模型，例6.4下图所示的图可以如下构造权重矩阵B:最小的树和图，

9、树是图论中最简单但最重要的图。 它广泛应用于自然和社会领域。在为乒乓球单打比赛抽签之后，我们可以用图片来展示如下图所示的会议情况。运动员，树和最小的图表树。例6.3企业的组织结构图也可以用树形图来表示。树和图中最小的树。树：没有圈的连通图就是树。属性1:任何树中都必须有一个1度的点。属性2:有n个顶点的树必须有n-1条边。属性3:树中任意两个顶点之间都有一条链。属性4:树是连接的，但是如果任何边被移除，它将变得断开。属性5:树没有循环，但是在两个不相邻的点之间添加了一条边来得到一个循环。树和图的最小树，以及图的最小部分树(支持树)。如果G2是G1的部分图和树形图，那么G2就是G1的部分树(或支

10、持树)。树形图的每条边都称为一个分支。通常，图G1包含多个部分树，其中具有最小总分支长度的部分树被称为图的最小部分树(或最小支撑树)。、G1、G2、最小树和图树、最小树和图树、最小树和图树、最小树和图树、寻找树的方法：打破圆和避免圆、打破圆、最小树和图树、部分树、最小树和图树、避免圆、树和、v1、v2、v3、v4、v5、v6、4、3、5、2、1、边数=n-1=5，树和图的最小树得到最小树添加边的原则是：从最短的边开始添加，在添加边的过程中，直到点连接(即：n-1条边)才能形成圆。最小树和图、v1、v2、v3、v4、V5、V6、4、3、5、2、1，最小c (t)=15，最小树和图。练习：通过使用

11、破圆法3，28，17，4，1，23，最小树和图树、V1、V7、v4、v3、V2、V5、V6、20、15、9、16、25、3 28、17、4、1、23，最小树和图树、v1、V7、V4、V3、v2、V5、V6、15、9、16、25、3、23找到最小的树、树和图最小的树和图树、v1、v7、v4、v3、v2、v5、V6、9、25、3、28、17、4、1、23，最小的树和图树、v1、V7、 V6，9，3，28，17，4，1，23，最小树和图树、v1，v7，v4，v3，v2，V5，V6，9，3，17，4，1，23，最小V2，V5，V6，20，15，9，16，25，3，28，17，4，1，23，36，最小树

12、和图树、V1，V7，V4 V1，V7，V4，v3，v2树和图的最小树、v1、V7、v4、v3、v2、V5、V6、20、15、9、16、25、3、28、17、4、1、23、1、23树和图的最小树、3、4、1、2、2、3、2、3、3、2、4、2、最小c (t)=12、最小c (t)=18，最短路径问题，如何用最短线路连接三部电话？这个问题可以抽象为ABC是一个等边三角形，而这条路线连接三个顶点(称为网络)。这样的网络有很多，其中最短路径显然是两边的总和(如ABAC)。A，B，C，A，B，C，P，但如果增加一个换装站(新的点P)，在四个点连接新网络的最短路线是PA PB PC。最短新路径的长度n比只

13、有三个点的原始最短路径o短。这样得到的网络不仅节省材料，而且具有较好的稳定性。最短路径问题，问题描述：它是在给定的网络图中寻找从一点到每一点或任意两点的最短路径。一些问题，如选址、管道铺设过程中的路径选择、设备更新、投资、一些整数规划和动态规划，也可以归结为最短路径问题。因此，这种问题在生产实践中被广泛应用。找到最短路径有两种算法：Dijkstra标记算法逐次逼近算法，最短路径问题，Dijkstra标记算法的基本思想：如果序列vs，v1.vn-1，VN是从vs到vt的最短路径，然后是序列vs，v1.假设v1v2 v3 v4是v1和v4之间的最短路径，v1v2 v3必须是v1和v3之间的最短路径，v2 v3 v4也必须是v2和v4之间的最短