03图论
图论
§1 动态规划模型
【例1】如图所示，给定一个线路网络，两点之间连线上的数字表示两点间距离，试求一条从A到E的路线，使总距离为最短。
Mattlab求解：
首先自编写好函数程序：dongtaigh.m
function [distance,path]=dongtaigh(edge,n)
d=edge;
for i=1:n
for j=i+1:n
if d(i,j)<99999
d(j,i)=d(i,j);
end
end
end
p=zeros(n,n);
for i=1:n
for j=1:n
if i==j
p(i,j)=99999;
else
p(i,j)=i;
end
end
end
for k=1:n
for i=1:n
for j=1:n
if i~=j
if d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j); p(i,j)=k; end end end end end distance=d(1,n); path=zeros(1,n); count=9; i=1; while count>1 path(i)=p(1,count); i=i+1; count=p(1,count); end 然后利用Excel建立工作表edge存储图的上三角阵。其中edge= 99999 5 2 99999 99999 99999 99999 99999 99999 99999 99999 99999 3 7 99999 99999 99999 99999 99999 99999 99999 99999 6 3 99999 99999 99999 99999 99999 99999 99999 99999 99999 6 99999 99999 99999 99999 99999 99999 99999 99999 3 8 99999 99999 99999 99999 99999 99999 99999 99999 1 99999 99999 99999 99999 99999 99999 99999 99999 99999 3 99999 99999 99999 99999 99999 99999 99999 99999 7 99999 99999 99999 99999 99999 99999 99999 99999 99999 然后在Matlab调入以上数据；同时将调用自编的动态规划程序函数“dongtaigh.m”，即在 Matlab命令窗口输入： n=9; [distance,path]=dongtaigh(edge,n) ,回车后则在窗口显示出路径path和距离distance §2 最小生成树 【例2】某工厂要架设局域网联通工厂各个部门。已知工厂有7个部门，各个部门间铺设网线的距离如上图所示，计算出铺设网线的最短距离。 Matlab的算法： 首先自编写好函数程序：shengcs.m function result=shengcs(G,N) result=zeros(N-1,2); count=1; lowcost=zeros(N,1); closest=zeros(N,1); for i=1:N lowcost(i)=G(1,i); closest(i)=1; end closest(1)=0; for i=2:N min=inf; k=i; for j=1:N if lowcost(j) if closest(j)~=0 min=lowcost(j); k=j; end end 7 2 5 3 1 4 6 50 60 45 65 52 40 50 70 30 42 end result(count,1)=closest(k); result(count,2)=k; count=count+1; closest(k)=0; for j=1:N if G(k,j) if closest(j)~=0 lowcost(j)=G(k,j); closest(j)=k; end end end end 然后，将上图的邻接矩阵存储为G；即：G= 99999 50 60 99999 99999 99999 99999 50 99999 99999 65 40 99999 99999 60 99999 99999 52 99999 99999 45 99999 65 52 99999 50 30 42 99999 40 99999 50 99999 70 99999 99999 99999 99999 30 70 99999 99999 99999 99999 45 42 99999 99999 99999 然后调入到Matlab命令窗口中，另外将调用自编程序shengcs.m，即: n=7; result=shengcs(G,n) 即可看见最小生成树的连接方式。 【例3】某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。 §3 最短路 【例4】 如下图所示的交通网络，边上的权重代表城市之间的距离，求城市1到其他城市的最短路径。 Matlab 的算法： function path=zuiduanlu(G,N) okset=zeros(N,1); dis=zeros(N,1); path=zeros(N-1,N); for i=1:N-1 path(i,1)=1; v 5 v 6 v 2 v 4 6 2 7 5 3 5 4 4 1 V v 3 path(i,2)=i+1; end for i=1:N dis(i)=G(1,i); okset(i)=0; end okset(1)=1; for i=1:N temp=inf; for j=2:N if okset(j)==0 if dis(j) temp=dis(j); w=j; end end end okset(w)=1; for v=2:N if okset(v)==0 sum=dis(w)+G(w,v); if dis(v)>sum dis(v)=sum; k=1; while path(w-1,k)~=0 path(v-1,k)=path(w-1,k); k=k+1; end path(v-1,k)=v; end end end end for i=1:N-1 path(i,N)=dis(i+1); end 然后，将上图的邻接矩阵存储为H；即：H= 99999 10 99999 30 100 99999 99999 50 99999 99999 99999 99999 99999 99999 10 99999 99999 20 99999 99999 99999 99999 99999 60 99999 然后调入到Matlab命令窗口中，另外将调用自编程序zuiduanlu.m,即： v 6 v 4 v 8 9 1 V 1 v 5 n=5; path=zuiduanlu(H,n) 即可看见最最短路的连接方式。 【例5】: 如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。 §4 网络最大流 如上图所示，每条弧相关的括号中，第一个数据表示该条弧的容量，第二个表示该弧流量，最大流量必须满足以下条件的限制： 1.可行性条件： xi>=0, x1<=3, x2<=5, x3<=1, x4<=4, x5<=1, x6<=2, x7<=5, x8<=2 2.始点Vs和收点Vt容量的要求： x1+x2<=8, x7+x8<=7 3.流量平衡要求 总流入量和总流出量相同： x1+x2-x7-x8=0 4.内节点流入量和流出量相同： x1+x5-x3-x4=0 x2+x3-x6=0 x6-x5-x8=0 x4-x7=0 目标函数为：max z=x1+x2 软件求解：Matlab函数：linprog(线性规划), ip（整数规划） Lindo软件求解结果如下： OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.000000 0.000000 X3 0.000000 1.000000 X4 3.000000 0.000000 X5 0.000000 0.000000 X6 2.000000 0.000000 X7 3.000000 0.000000 X8 2.000000 0.000000 【例6】.如下图所示为一城市水管网络流量图，试求一条从始点Vs到收点Vt的最大流 §5最小费用最大流问题 网络最大流只考虑了流量的问题，实际在运用时还有“费用”因素存在。人们总是希望在得到最大流的同时，使费用最少，这就是最小费用最大流问题 【例7】如上图所示：括号里第一个数字表示最大容量，第二个数字表示单位流量的费用，第三个表示待求实际流量。 从前面可知，网络的最大流问题的解不唯一，我们可以分别计算两次线性规划求出最小费用最大流，求解过程如下： （1） 建立求解最大流的线性规划模型，求出最大流 （2） 将求出的最大流作为已知限制条件，构建求解最小费用最大流的线性规划模型。 由前面已经求出最大流为5，则将x1+x2=5作为增加的约束条件，另将目标函数改为： Min z=2x1+3x2+x3+5x4+2x5+4x6+x7+2x8 即线性模型如下： Min 2x1+3x2+x3+5x4+2x5+4x6+x7+2x8 st x1<=3 x2<=5 v t 24v s x3<=1 x4<=4 x5<=1 x6<=2 x7<=5 x8<=2 x1+x2<=8 x7+x8<=7 x1+x2-x7-x8=0 x1+x5-x3-x4=0 x2+x3-x6=0 x6-x5-x8=0 x4-x7=0 x1+x2=5 运用Lindo求解，可得结果如下： OBJECTIVE FUNCTION VALUE 1) 42.00000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.000000 0.000000 X3 0.000000 1.000000 X4 3.000000 0.000000 X5 0.000000 6.000000 X6 2.000000 0.000000 X7 3.000000 0.000000 X8 2.000000 0.000000 1、略 2、计算有向无圈图的根 输入一个有向无圈图DAG，计算和输出DAG的根r（即r到其他任何顶点都有一条路。若图中没有根，则输出“not found”）。 输入：顶点数n和边数e;以下为e行，每行为一条有向边的两个端点 输出：根r或者“not found” 算法分析 设 const mx=100;{顶点数的上限} var n,e,i,j,k,a,b:integer;{ 顶点数n、边数e} g:array[1..mx,1..mx]of boolean;{传递闭包} bn:boolean;{根存在标志} 1、输入信息，计算传递闭包 readln(n,e);{输入顶点数和边数} fillchar(g,sizeof(g),0);{ 有向无圈图初始化} for i:=1 to e do{输入信息，构造传递闭包的初始值} begin readln(a,b);g[a,b]:=true end; for k:=1 to n do{计算传递闭包} for i:=1 to n do for j:=1 to n do if g[i,j] or g[i,k] and g[k,j]then g[i,j]:=true; 2、计算DAG的根 然后枚举每一个顶点。根据传递闭包的信息，若当前顶点至其它所有顶点有路，则判定该顶点即为根。若没有一个顶点可作为DAG的根，则输出失败信息 for i:=1 to n do{枚举每一个可能的根} begin bn:=true;{设定I至其他所有顶点有路的标志} for j:=1 to n do{若I至任一个顶点无路，则返回bn为false} if (i<>j) and not g[i,j] then begin bn:=false; break end; if bn then break{若I至其他所有顶点有路，则输出根i} end; if bn then writeln(i) else writeln('not found'){若不存在根，则输出失败信息} 图论法用于供水管网水力计算的研究 图论法用于供水管网水力计算的研究 摘要：图论理论是网络分析的主要工具，现用于管网的水力平衡计算，既充分发挥了图论理论的优势，使计算变得简便、迅捷，又可将管网附件加入计算，使结果更准确、更符合实际。文中采用峰阵输入管网结构，使输入数据的工作量大大减少，易于编制程序，计算大型的复杂管网。 关键词：供水管网水力计算图论法 前言 供水管网的水力平衡计算是供水系统规划设计、经济评价和运行管理的基础。水力平衡计算的目的就是在确定管径的情况下求出满足连续方程和能量方程的各节点压力水头和各管段流量。目前常用的水力平衡计算方法有哈代-克罗斯法(Hardy-Cross)，牛顿-莱福逊法(New ton-Raphson)，线性理论法(Linear-Theory)，有限元法(Finite Element)等等。所有这些方法各有所长，适用范围各不相同，有的还需人工假设管段流量，使输入数据工作量增大，且未考虑管网附件的影响。本文介绍的图论法将复杂的管网处理为相应的“网络图”，并建立相应的数学模型，用峰阵输入原始数据来描述管网结构，输入的数据量最少，不易出错，易于计算大型的复杂管网。其计算过程可同 时考虑管网附件，如控制阀、加压泵、逆止阀、减压阀等，使计算结果更符合实际。 1 图论原理 将供水管网中的管段概化成一条线段(即图中的边)，将有附件的管段看成图中的特殊管段，边与边由节点相连。这样，一个供水系统的管网图就转化为图论中的网络图。而且管道中的水流是有方向的，所以管网图是有向图。 根据以上所述原则，可将图1所示管网系统，转化为图2所示的网络图。 图1 图2 图1中有一水库A，三个给水点B、C、D，Q1表示水库节点供水量，Q2\,Q3\,Q4分别表示B、C、D节点的用水量。管段视为网络图中的对应边，管段的直径、管长、管道流量、摩损系数等作为管段对应边的权。至此，与管网同构的网络图生成了。图中箭头表示各条边的方向，即管段中水流方向。 网络图中节点与边的关联函数可以用完全关联矩阵I4×5表示如式(1)所示。 顶点边的编号 图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j) 离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝ 离散数学图论与系中有图题目 ————————————————————————————————作者：————————————————————————————————日期： 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1) 介绍几个图论和复杂网络的程序库 刚加入复杂网络圈子，暂时还没有成熟的研究内容，先发个资料性的东西占坑：） 作复杂网络研究离不开对各种实际或模拟网络的统计、计算、绘图等工作。对于一般性的工作，我们可以用Pajek、Netdraw和Ucinet等软件完成。但对一些特殊应用（比如自己开发了一个新模型），现有的软件不能提供相应的建模或计算功能，这时就必须要通过编程的办法来解决问题了。 在这篇文章中，向大家介绍我使用过的4个面向图论及复杂网络分析的程序库，它们可以（分别或同时）用C、C++、C#和Python等语言调用。同时这些库都是开源的，可以通过研读它们的源代码提高编程水平。 好，下边开始介绍，第一位出场的是： 一、Boost Graph Library ——“准”C++标准库 Boost Graph Library（BGL）是C++ Boost库的成员之一。Boost是一个经过千锤百炼的C++库，作为标准模板库STL的后备，是C++标准化进程的发动机之一。Boost库由C++标准委员会库工作组成员发起，在C++社区中影响甚大，是不折不扣的“准”标准库。 BGL的特点是灵活性和高运行效率。BGL是以模板的形式提供的，这意味着你可以在模板的基础上创建自己的类型，比如自定义的节点类。BGL的开发者是世界上最顶尖的C++专家，这个库中实现的各种图算法具有非常高的执行效率，而且BGL本身具有工业强度，你可以放心的使用它。此外，BGL的代码结构良好，是非常值得研读的精品，对于学习算法与数据结构会有很大的帮助。 从我的角度来看，BGL的缺点是没有提供复杂网络分析的算法，所以在实际中我使用的还不多。建议对于分析大规模的网络问题时使用这个库，利用它良好的图数据结构，开发自己的复杂网络分析算法，将会获得很高的执行效率。 参考资源： BGL官方网站：https://www.wendangku.net/doc/d811840189.html,/doc/libs/1_42_0/libs/graph/ 技术书籍《The Boost Graph Library》，作者: Jeremy G. Siek，Lie-Quan Lee，Andrew Lumsdaine，见：https://www.wendangku.net/doc/d811840189.html,/subject/1463103/ 《使用Boost Graph library》，一个简短的BGL使用介绍，适合快速上手，见：https://www.wendangku.net/doc/d811840189.html,/2009/0408/100.html 《Boost Graph Library 学习笔记》，讨论学习BGL中遇到的问题，见：https://www.wendangku.net/doc/d811840189.html,/magicblue/archive/2009/05/22/4208976.aspx 二、QuickGraph —— .NET平台下的BGL QuickGraph是一个用C#语言编写的.NET组件库，所提供的算法与BGL类似，可以看作是Boost Graph Library在.NET平台下的实现。目前QuickGraph的最高版本是3.3，支 数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。 图论学习整理 图论程序整理出来 程序中图可以用邻接矩阵 Dijkstra算法 Floyd算法 Kruskal算法 Prim算法 算法类型：最短路，网络流，二分图算法。 解释： 最短路问题：（Dijkstra，Floyd算法） 最小生成树问题：连接多个节点费用最低（Prim，Kruskal算法）图的匹配问题：（匈牙利算法） 遍历性问题 最大流问题 运输问题：完成运输问题，并寻求运输费用最小方案 Matlab程序： n=8;A=[0 2 8 1 Inf Inf Inf Inf 2 0 6 Inf 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞ D=A; %赋初值 for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值 for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j) if(pd)break;end %存在一条负回路, 终止程序 end %程序结束 求最小费用最大流matlab代码 n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1) for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量 if(dvt>dvtt)dvt=dvtt;end if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量 t=s(t);end %继续调整前一段弧上的流f pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值 t=n;while(1) %调整过程 if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整 elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整 if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用 一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。 目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出 一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个圈或者一条链），如果路径闭合（一个圈），则称为欧拉回路[1]。 一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。 [编辑] 一笔画定理 对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。 [编辑] 定理一 有限图G 是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图G 是圈当且仅当它没有奇顶点[2]。 证明[2][3]： 必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。 充分性： 如果图中没有奇顶点，那么随便选一个点出发，连一个圈C1。如果这个圈就是原图，那么 习题十 1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。 证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数。■ 2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) 数理与信息工程学院 课程论文 课程名称图论及其应用 题目图论中邻接矩阵的应用 姓名沈海华朱国淼 学号06200123 06200129 专业信息与计算科学06（1）指导老师卜月华 浅谈图论中邻接矩阵的应用 [摘 要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。 [关键字] 邻接矩阵、算法、连通性、最小生成树 1、引言 首先介绍图论中邻接矩阵的一个重要定理: G 是一个图,V (G)为 G 的顶点集, E(G)为 G 的边集。设G 中有 n 个顶点，v 1,v 2,…,v n ;A=(a ij )n ×n 为 G 的邻接距阵, 其中 n j i G E v v G E v v a j i j i ij ,...,2,1,) (0)(1=??????∈= 定理 1:设 A (G)为图 G 的邻接距阵,则 G 中从顶点 vi 到顶点 vj,长度为 k 的道路的A k 条数为中的 i 行 j 列元素。 证:对 k 用数学归纳法 k =1时,显然结论成立;假设 k 时,定理A l .A= A l+1 成立,考虑 k +1的情形。 记 A l 的 i 行 j 列元素为l ≥2,因为所以 nj l in j l i j l i l ij a a a a a a a +++=+...2211) 1( (1) 而从v i ,v j 到长 k +1的道路无非是从v i 经 k 步到某顶点v l (1≤l ≤n),再从v l 走一步到v j ; 由归纳假设从v l 到v j 长为 k 的道路共计 而从v l 到v j 长为 1的道路为a ij 条,所以长为k+1的v l 经过k 部到v i 再一步到v j 的道路共有 ∑-+= n l lj k il l ij a a a 1 )()1(条故从v i 经 k +1步到v j 的路径共有 1、 邻接矩阵现实问题中的运用 锁具装箱问题 某厂生产一种弹子锁具,每个锁具的钥匙有 5个槽,每个槽的高度从 {1, 2, 3, 4, 5, 6}6个数 (单位略 )中任取一数由于工艺及其他原因,制造锁具时对 5个槽的高度还有两个限制:至少有 3个不同的数,相邻两槽的高度之差不能为 5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每 60个装一箱出售。问每一批具有多少个,装多少箱。 分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有 5个槽,每个槽有 6个高度,至少有三个不同高度的槽。且相邻槽高差不为 。我们先求出无相邻高5差为 5的锁具数量,再减去仅有一个、两个槽高的锁具数目。 先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。为此,构造一个 6 二、应用题 题0：（1996年全国数学联赛） 有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。 注：[n /2]表示不超过n /2的最大整数。 证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有 （1）对每个顶点x ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , 离散数学图论部分综合练习 1 ．设图G ＝ 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f 浅谈图论中邻接矩阵的应用 [摘要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想,对于更好地理解问题,思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的,它是数学的重要分支,使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题,是源于生活,高于生活。图论作为组合数学的一分支,与其他数学分支,如矩阵论,概率论,拓扑学数值分析都有着重要的联系。 [关键字] 邻接矩阵、算法、连通性、最小生成树 1、引言 首先介绍图论中邻接矩阵的一个重要定理: G是一个图,V (G)为G的顶点集, E(G)为G的边集。设G中有n个顶 点,v1,v2,…,vn;A=(aij)n ×n为G的邻接距阵, 其中 定理1:设A (G)为图G的邻接距阵,则G中从顶点vi 到顶点vj,长度为k的道路的Ak条数为中的i行j列元素。 证:对k用数学归纳法 k =1时,显然结论成立;假设k时,定理Al.A= Al+1成立,考虑k +1的情形。 记Al的i行j列元素为l≥2,因为所以 (1) 而从vi,vj到长k +1的道路无非是从vi 经k步到某顶点vl(1≤l≤n),再从vl走一步到vj; 由归纳假设从vl到vj长为k的道路共计而从vl到vj 长为1的道路为aij条,所以长为k+1的vl经过k部到vi再一步到vj的道路共有条故从 vi经k +1步到vj的路径共有 1、邻接矩阵现实问题中的运用 锁具装箱问题 某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1, 2, 3, 4, 5, 6}6个数(单位略)中任取一数由于工艺及其他原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数,相邻两槽的高度之差不能为5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每60个装一箱出售。问每一批具有多少个,装多少箱。 分析:锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有5个槽,每个槽有6个高度,至少有三个不同高度的槽。且相邻槽高差不为。我们先求出无相邻高5差为5的锁具数量,再减去仅有一个、两个槽高的锁具数目。 先计算由1, 2, 3, 4, 5, 6构成无1, 6相邻的情况的数目。为此,构造一个6节点的图:将1, 2, 3, 4, 5, 6这6个数作为6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具各槽之间的关系示意图(见图1)。 由图我们可以试着画出这个图的邻接矩阵来: 邻接矩阵A的所有元素之和表示两个槽高无1, 6相邻的锁具的个数,每个无1, 6相邻的5位数与图1中长度为4的一条链1 - 1对应,如12345, 11111, 22335等。A的k次方中各元素之和就是长度为k的链的个数。事实上,从这2个具体问题可以看出, A 中第i行第j列 的元素指从i开始经过两条边到达j的链数,即从i开始经过一条边到k,再 从k经过一条边达到j, i和j就决定了中间顶点k的数目。于是,利用Matlab就很容易得到。 离散数学（图论部分）1-4章习题课 1. 证明：在10个人中，或有3人互相认识，或有4人互不认识。 证：设x为10人中之任意某人，则在余下9人中：(1) x至少认识其中4人，或(2) x至多认识其中3人（即至少不认识其中6人），两者必居其一。 (1) 若此x认识的4人互不相识，命题得证；否则，互相认识的2人加上x 构成互相认识的3人，命题得证。 (2) 若此x不认识的6人中有3人互相认识，命题得证；否则，由 Ramsey(3,3)=6知，此6人中至少有3人互不认识，此3人加上x为互 不认识的4人，命题得证。 2. 设(a) V={a,b,c,d}，A={ 【图论基础】求连通子图的个数 Time Limit:10000MS Memory Limit:65536K Total Submit:42 Accepted:30 Description 求一个无向图中连通子图的个数。 Input 第一行一个数n，表示无向图的顶点的数量（n<=5000），接下来从第2行到第n+1行，每行有n个数（1表示相应点有直接通路，0表示无直接通路），形成一个n*n的矩阵，用以表示这个无向图。示例： Output 输出一个数，表示这个图含有连通子图的个数。 Sample Input 5 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 Sample Output 自己算吧！ Source ?var ? i,j,n,ans,x:longint; ? a:array[1..5000,0..5000] of longint; ? b:array[1..5000] of boolean; ?procedure dfs(x:longint); ?var i:longint; ?begin ? b[x]:=false; ? for i:=1 to a[x,0] do if b[a[x,i]] then ? dfs(a[x,i]); ?end; ? ?begin ? readln(n); ? for i:=1 to n do ? for j:=1 to n do begin ? read(x); ? if x=1 then begin ? inc(a[i,0]); a[i,a[i,0]]:=j; ? end; ? end; ? fillchar(b,sizeof(b),true); ? for i:=1 to n do if b[i] then begin ? inc(ans); ? dfs(i); ? end; ? writeln(ans); ?end.图论基础
图论法用于供水管网水力计算的研究
图论算法及其MATLAB程序代码
离散数学测验题--图论部分(优选.)
离散数学图论与系中有图题目
介绍几个图论和复杂网络的程序库
数学建模中的图论方法
图论学习的整理笔记
一笔画问题是图论中一个著名的问题
习题参考解答图论部分
图论学生论文
图论习题参考答案
离散数学图论部分综合练习
离散数学图论部分经典试题及答案
浅谈图论中邻接矩阵的应用
离散数学(图论部分)1-4章习题课
1040 【图论基础】求连通子图的个数 1041 【图论基础】求最小生成树(prim)