运筹学(第6章 图与网络分析)

1、，运筹学，演讲者：杨奇鸣，第6章，图形和网络分析。现代图论的历史可以追溯到18世纪的七座桥的问题，它要求每座桥只通过一次。这就是著名的“哥尼斯堡7号桥”问题。欧拉1736在1736年证明了这样的路线不可能存在。图对应于Knigsberg桥，6.1图的基本概念和模型，岛屿，北部地区，东部地区和南部地区，图在图论中是由点和边组成的，它可以反映一些对象之间的关系。通常，反映对象之间的关系并不重要，例如图中各点的相对位置以及点之间连接线的长度和直线度。例如，在人群中，我们可以用一个图表来表达相互理解的关系，图6-1是显示这种关系的图表。图的定义：如果要研究的对象用点来表示，这些对象之间的关系用边来表示

2、，那么图G可以定义为一组点和边，表示为：其中： V点集E边集。当然，图论不仅是为了描述对象之间的关系，也是为了研究具体关系的内在规律。一般来说，图中各点的相对位置以及点之间连接线的长度和曲率对于反映对象之间的关系并不重要。图形和网络的基本概念，如果我们把上面例子中的“相互理解”关系改为“理解”关系，那么很难只用两点之间的连线来描述它们之间的关系，也就是说我们引入了一条带有一个叫做弧的箭头的连线。图6-3是反映这七个人之间“认知”关系的图表。相互理解由两条相反的弧线表示。图的基本概念和模型定义了：图中的点用v表示，边用e表示。每条边可以用它所连接的点表示，表示为e1=v1，v1；e2=v1，v2

3、；端点、相关边和相邻边。如果有边E，它可以表示为e=vi，vj，那么vi和vj是边E的端点，否则，边E是点vi或vj的相关边。如果点vi和vj与同一条边相关联，则点vi和vj被称为相邻；如果边ei和ej有一个公共端点，则称边ei和ej是相邻的。图的基本概念是模型、环、多边、简单图。如果边E的两个端点重叠，这条边称为环。如右图所示，边e1是一个环。如果两点之间有一个以上的点，称为多条边，如右图中的e4和e5，没有循环和多条边的图称为简单图。图的基本概念和模型，度，奇点，偶点，孤立点，与某一点vi相关的边数称为点vi的度，也称为d(vi)。在右图中，d(v1)，d(v3)=5，d(v5)=1。奇数

4、编号的点称为奇点，偶数编号的点称为偶数点，1编号的点称为悬挂点，0编号的点称为孤立点。图形的度数等于每个点的度数之和。图和模型、链、圈、连通图、图中某些点和边的交替序列的基本概念，其中边彼此不同并且与任何vi、t-1和vit相邻，称为链。起点和终点重合的链叫做圆。如果每对顶点之间至少有一条链，这种图称为连通图；否则，图形被称为未连接的。图的基本概念和模型，二部图(偶图)，图的点集V G=(V，E)可分为两个非空子集X，Y，集XY=V，XY=，从而使同一集中的任意两个顶点不相邻。这样的图叫做偶图。(a)、(b)、(c)、(a)显然是二部图，而(b)也是二部图，但它们并不明显，当改成(c)时可以清

5、楚地看到。图、子图、部分图(支持子图)、图G1=V1、E1和图G2=V2、E2的基本概念和模型，如果有的话，G1是G2的子图。(a)，(b)，(G)，如果有，那么G1是G2的部分图(支持子图)。图的基本概念和模型，网络(加权图)，让图G(V，e)，并给每条边(vi，vj)的G的定量指标wij的权重，这叫做边(vi，vj)，而加权图G叫做网络(或加权图)。重量可以代表距离、成本、通行能力等。，9，10，20，15，7，14，19，25，6，端点无序的加权图称为无向网络，端点有序的加权图称为有向网络。图形的基本概念和模型，出现的程度和出现的程度。在有向图中，以vi为起点的边数称为点vi的出现度，用

6、d (vi)表示。以vi为端点的边数称为vi点的进入度，用来表示D-(VI)；在第六点出入的次数之和就是那个点的次数。在有向图中，所有顶点的引入时间之和等于所有顶点的引出时间之和。图形的基本概念和模型，以及图形模型的应用。在例6.1中，来自A、B、C、D和F的六名运动员报名参加了六个项目的比赛。下表列出了运动员报道的项目。询问如何安排六个项目的比赛顺序，这样每个运动员可以不连续参加两个比赛。图形的基本概念和模型，解决方案：用图形建模。以比赛为研究对象，用圆点表示。如果同一个运动员参加了两个项目，在代表这两个项目的点之间连接一条线，得到下图。在图中找到一个点序列，这样依次排列的两个点就不相邻了，

7、这就可以满足要求。例如：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，思考问题，图形的基本概念和模型，思考问题和解决方法：以每门课为顶点，把所有的课程用边连接起来，得到图形。根据问题的含义，相邻顶点对应的课程不能连续测试，而非相邻顶点对应的课程允许连续测试。因此，绘制补充图的问题是在图中找到哈密尔顿道路，例如CEAFDB，这是一个满足要求的测试计划。图、A、F、E、D、C、B、A、F、E、D、C、B、定理2的基本概念和模型在任何图中，都必须有奇数个偶数个顶点。证明了由于每条边

8、必须与两个顶点相关联，所以在计算点的度数时，每条边被计算两次，所以顶点的度数之和等于边数的两倍。证明了V1和V2分别是图G中的奇点和偶点集。根据定理1，2m是偶数，偶数点的第二个和是偶数，所以它必须是偶数，也就是说，奇数点的数量必须是偶数。图形的基本概念和模型，图形的矩阵描述：如何在计算机中存储图形？现在有很多存储方法，但最基本的方法是用矩阵来表示一个图，而图的矩阵表示也包括邻接矩阵、关联矩阵、权重矩阵等。1。图G=(V，E)，| V |=n，| E |=m的邻接矩阵，具有nn阶方阵A=(aij) nn，其中下面示例6.2中所示的图可以如下构造邻接矩阵A，而对于加权图G=(V，E)，其中边被加

9、权，构造矩阵b=(。E)，| V |=n，| E |=m，矩阵同mn阶M=(mij) mn，其中：3。权重矩阵，1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1100010010010000， V1 V2V3V4V5 V7V8，E1 E2 E3 E5E6E7E8E9E10E11E12，实施例6.3下面所示的图可以如下构造邻接

10、矩阵m 3360，m=(mij)=并且下面所示的图可以如下构造权重矩阵：无向图。 有向图：由点和弧组成的图，表示为D=(V，a)。连通图：对于无向图G，如果任意两个不同点之间至少有一条链，则G是连通图。循环：如果道路的第一个点和最后一个点是相同的，那么道路就是一个循环。加权图：对于无向图G的每条边(vi，vj)，都有一个数wij，那么图G称为加权图，wij称为边(vi，vj)上的权。网络：在加权有向图D中，一个点被指定为起点，另一个点被指定为接收点，其他点被称为中间点，D中每个弧的加权数被称为弧容量，D被称为网络。树是图论中的一个重要概念。所谓的树是一个无环的连通图。在图6-11中，(a)是树

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

12、得到一个循环。树和图的最小树，以及图的最小部分树(支持树)。如果G2是G1的部分图和树形图，那么G2就是G1的部分树(或支持树)。树形图的每条边都称为一个分支。通常，图G1包含多个部分树，其中具有最小总分支长度的部分树被称为图的最小部分树(或最小支撑树)。G1、G2、最小树和图树、最小树和图树、最小树和图树、最小树和图树、寻找树的方法：打破圆和避免圆、打破圆、最小树和图树、部分树、最小树和图树、避免圆、树和、v1、v2、v3、v4、v5、v6、4、3、5、2、1、边数n-1=5，得到树和图的最小树，最小树和图、v1、v2、v3、v4、V5、V6、4、3、5、2、1，最小c (t)=15，最小树

13、和图。练习：通过使用破圆法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，最小树和图树、V1，V7，V4 V1，V7，V4，v3，v2树和图的最小树