数学建模第九章

精选文库第九章图论方法建模9.1图论课程简介一基本概念1.哥尼斯堡七桥问题：居民从某处出发，试图发现这样的路线，经过所有的桥，且对每一座桥只经过一次，并最终回到原处。有人请教了当时的大数学家欧拉，欧拉将之转化为如下的一副“图”，仅包含“点”、“线”的一类拓扑结构：1.图：称由若干个点以及以这些点为端点的若干条边形成的一种拓扑结构为图。记之为，其中为顶点集，为边集，为边集到“顶点集与顶点集自身的笛卡儿积集”上的一个映射，称之为关联关系。简记为边与顶点的关系有如下几种典型情况：2.简单图：无自回环，无重边的图。无向图：边没有指向，.此时称边与顶点、关联，称顶点与顶点邻接。有向图：边有指向，顶点的度：与一个顶点关联的边的个数；若是有向图，则分为顶点的出度和入度。（以上，左图为一无向图，右图为一有向图，它们均为简单图；七桥问题对应的图为一无向图，但由于存在重边，故不是简单图）3.图的关联矩阵，若为无向图，；若为有向图，4.图的邻接矩阵，若为无向图，； 若为有向图，。例如、，分别为下图的关联矩阵和邻接矩阵。l无向图的邻接矩阵为一对称矩阵。5.欧拉回路与欧拉定理：l欧拉回路：若存在序列满足：，对，均有，且对不同的数对应图中的边不同；，则称图存在欧拉回路，称序列为图的欧拉回路。l欧拉定理：无向图存在欧拉回路图是一顶点的度均为偶数的连通图。l边遍历问题；“欧拉回路”与“中国邮递员问题”。二几个简单的应用例子问题一：消防设施的设置若干条街道构成一个居民小区，居民楼分布在街道两侧，现计划在某些路口安置消防设施，使得每一街道的居民在必要时都可在该街道的某一路口得到设施利用。问题：如何利用尽可能少的设施达到以上目标？问题二：监狱看守的设置一座监狱的几间牢室有通道相连，监狱的看守要设在通过道路能直接监视到所有牢室的地方。问题，如何设置尽可能少的哨岗达到以上目标？9.2循环比赛的排名问题问题：支球队参加循环比赛，两两交锋，一场决胜，不容平局，“0、1”打分。如何排名？1竞赛图：每对顶点之间有且只有一条有向边相连的有向图；有向边指向负方。2路径与完全路径：称有向图的一个顶点序列为图的一条步长为的路径，若满足：对，均有；若还满足，则称之为图的一条步长为的回（或闭）路径。而若顶点集的一个全排列构成图的一条路径，也称之为图的一条完全路径。l图1中：、l子路径、闭的完全路径3定理：任一阶竞赛图都存在完全路径。证明（数学归纳法）：时，如图3-0，命题真；：设时命题真；：当时，设为顶点集，记，为图关于的生成子图；由归纳假设，在中存在完全路径，不失一般性，设为中的一条完全路径，考虑顶点与的邻接关系，有如下三种情形：图3-1：为中的一条完全路径；图3-2：为中的一条完全路径图3-3：为中的一条完全路径。4定理：存在唯一完全路径的阶竞赛图在同构的意义下唯一。进一步讲，若设为中的唯一的一条完全路径，则。证明（数学归纳法）：时，如图3-1，命题真；：设时命题真；：当时，设为顶点集，不妨设为中的唯一的一条完全路径；记，为图关于的生成子图；此时为中的唯一的一条完全路径，否则，由（3.定理）的论证可得不同于的中的另一条完全路径，这与题设矛盾；以下只须证明负于任意：（反证）设胜某，如下图，可以找到一条不同于的中的另一条完全路径，这同样与题设矛盾。l这一性质表明，利用完全路径法进行竞赛图排名是不可行（完善）的。5简单积分法：简单积分法与完全路径法排名在完全路径唯一的情形下二者是一致的。以下试图通过低阶的竞赛图说明简单积分法的缺陷：l在以上组图的每一幅图的下方所标示向量既表示该图各顶点的简单积分，同时，对于3、4阶竞赛图，在同构的意义下可以作为该类图的标识。我们通过简单分析发现图按照简单积分的方法对各顶点排序是不合适的：假设不然（即简单积分是适用的），、，同时；这时看，按照简单积分法二者均只得1分，但其份量不同，所得1分为其胜，按照简单积分法，为一弱队；但所得1分为其胜，按照简单积分法，为一强队因此，通常认为强于。类似分析，可以得出强于。l尽管在以上组图中，除了图外，我们看不出简单积分法的缺陷，但随着竞赛图阶数的增加，简单积分的局限将尤为凸显。6双向连通图：称有向图为双向连通的，若对任意两个不同顶点，在该有向图中既有从顶点到顶点的有向路径，也有从顶点到顶点的有向路径。7双向连通图的邻接矩阵为素阵：即存在整数，使得。8Perron-Frobenius定理：素阵的最大特征根为正单根，对应正特征向量，且有（为所有分量均为1的维向量，也可以被表示为）。l对以上定理的理解可以参见层次分析法一章中对正互反矩阵性质的讨论。9对于双向连通的竞赛图，可以计算其邻接矩阵的最大特征根以及相应的正特征向量，按照该特征向量分量的数值大小对各个顶点（参赛队）排名。下面是一个双向连通的四阶竞赛图，通过前面的讨论，该算例不论完全路径法还是简单积分法均不适宜，我们分别采用与对之进行分析考察不难发现，的分量表示以相应顶点为起点产生的步长为的路径数，而的分量则表示以相应顶点为起点产生的步长不超过的路径数。如下图，从不同顶点（作为最底层）出发，只要存在以该顶点为起点的有向边，则向上生长出枝杈，将响应边的终点画在第二层，在以第二层上的点为基点向第三层生长，如此直到无穷，将最终得到四棵“参天大树”，直观上，的分量为表示相应顶点生长出的“树”介于第层与第层之间的枝杈数，而的分量为表示相应顶点生长出的“树”在第层下方部分的枝杈数。显然，一个“有实力的顶点（参赛队）”对应的“树”应当更为粗壮。按照Perron-Frobenius定理，只要足够大，可以将作为实力向量来对各个顶点排序，通过具体计算，事实上反映出完全相同的结果这正是Perron-Frobenius定理在竞赛图排名中的应用。10从直观上讲，以作为一个实力向量用于竞赛图排名将更为适宜，当然我们在这里愿意强调具有如下的优点：l它并不只局限于双向连通的竞赛图；l从对竞赛图的分析看，计算需要一直计算到，之后从排名的角度讲，的值才算稳定下来；而的计算在时就具备如上提及的特点。l你能从中发掘有关值更多的优点吗？尝试着准确表述你的发现或猜想，能从理论上加以论证吗？9.3红绿灯调节问题：图1所示的十字路口共有六条车道，其中是4条直道，是2条左转弯道，每条车道设有红绿灯，制定其调节方案。1相容图与区间图相容图：用图中的顶点表示交通流，当两条交通流相容时将代表交通流的两顶点连接而得到的图。区间图：称图G=（V，E）为区间图，若存在从顶点到区间的对应关系，使得对于任意的，有。2可行调节：通过删除（非）区间图某些边，构造一个区间图子图。3有效性调节：对于给定的子图所对应的交通流，设计有效的红绿灯调节程序（比方使在一个红绿灯调节周期中总的绿灯时间最长），尽可能利于路口的车辆通行。4在要求满足条件1）一个红绿灯调节周期=60秒；2）四个时段；3）六个车流流量；4）每一车流连续通行时间不少于10秒，可得如下线性规划模型：1l满足约束条件的任一均为其解；5改进的线性规划模型：一个合理的调节方案应当使为每一车流分配的有效通行时间与它的实际流量相适应，简言之，那些相对繁忙的车流应当有更为充足的通行时间，不妨设表示六个车流在单位时间内的车流量，则得如下的改进模型：11l适当选取，使得，不难得到是相应的最优解；但若进一步设想，适当选取的另外一组值，使得，不难得到依旧是改变了的问题的解这一现象事实上暴露了线性模型在处理红绿灯调节问题的缺陷，即尽管在改进模型是在考虑了各个交通流流量的差异，但由于线性模型的特点使得这一改进模型更为周全的考虑几乎没有发挥任何作用。它是在以满足大多数车流最低通行时间要求为代价，将剩余的时间极端的满足车流最繁