数学建模-图论

数学建模图论方法专题图论概述图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。图论应用十分广泛，如，物理学、化学、控制论、信息论、管理科学、通信系统、交通运输系统计算机科学、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。图论概述

图论最早处理的问题是哥尼斯堡城的七桥问题：18世纪在哥尼斯堡城（今俄罗斯加里宁格勒）有一条名叫普莱格尔（Pregel）的河流横经其中，河上有7座桥，将河中的两个岛和河岸连结。后来有人请教当时的大数学家欧拉,欧拉用图论的方法证明这个问题无解,同时他提出并解决了更为一般的问题,从而奠定了图论的基础,欧拉也被誉为“图论之父”.

ABCD图论起源城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点?哥尼斯堡七桥问题从某点出发通过每座桥且每桥只通过一次回到起点DABCABCD建模：点——陆地岛屿边——桥

后来,英国数学家哈密尔顿在1856年提出“周游世界”的问题：一个正十二面体,20个顶点分别表示世界上20个大城市,要求从某个城市出发,经过所有城市一次而不重复,最后回到出发地.这也是图论中一个著名的问题.

“四色问题”也是图论中的著名问题：地图着色时,国境线相邻的国家需要着上不同的颜色,最少需要几种颜色？1976年,美国人阿佩尔和哈肯用计算机运行1200个小时,证明4种颜色就够了.但至今尚有争议.在生产和日常生活中，经常碰到各种各样的图。如公路或铁路交通图、管网图、通讯联络图等。对所要研究的问题确定具体对象及这些对象间的性质关系，并用图的形式表示出来，这就是对所研究原问题建立的模型。例如，为了反映5家企业的业务往来关系，可以用点表示企业，用点间连线表示两家企业有业务联系，如图所示。又例如工作分配问题，我们可以用点表示工人与需要完成的工作，点间连线表示每个人可以胜任哪些工作，如图所示。戊甲乙丙丁戊甲乙丙丁工人工作DCBA这样的例子很多，物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等也都可以用点和线连接起来的图进行模拟。这里所研究的图与平面几何中的图不同。这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。这里所讲的图是反映对象之间关系的一种工具。图的理论和方法，就是从形形色色的具体的图以及与它们相关的实际问题中，抽象出共同性的东西，找出其规律、性质、方法，再应用到解决实际问题中去。图论的基本概念

所谓的图，直观的讲就是在平面上n个点，把其中的一些点对用线连接起来，不考虑点的位置与曲线的曲直长短，这样形成的一个关系结构就是一个图。一个图(Graph)定义为三元有序组G=(V(G),E(G),

G)，V(G)={v1,v2,…,vn}是图的顶点集合，E(G)={e1,e2,…,em}是图的边集合，它联结V

中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.

G称为顶点与边之间的关联函数。V(G)中的元素vi称为顶点,E(G)中的元素ek

称为边.一个图习惯记作

G=(V,E).一、基本概念１.图G的几何实现其中：例1:设G是一个图，图的分类如果E的每一条边都是无向边,则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.如果图的每一条边都对应一个实数w(e)，称w(e)为边e的权，称该图为赋权图。图1图2若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.端点重合为一点的边称为环。连接同一对顶点的多条边称为重边。一个图称为简单图，如果它既没有环也没有重边。含有重边的图称为多重图.我们只讨论有限图.图的术语1、相邻和关联设图G=(V(G),E(G))，若e

连接u和v，称u和v是e的端点.称端点u，v与边e是关联的，称两个顶点u，v是邻接（相邻）的.两条边e,e1有公共端点v，则称e,e1相邻.若图G是有向图，称点u

,v分别为边uv的始点和终点若t∈V，t不与其他顶点相邻，称t为孤立顶点。uvewe1图的术语2、顶点的度无向图中与结点v相关联的边数称为v的度数，记作deg(v)

或d(v)，有向图中以v为起点的边数称为v的出度，记作deg+(v)或d+(v)

，以v为终点的边数称为v的入度，记作deg-(v)或d-(v)

,此时d(v)

=d+(v)

+d-(v)

。称度为奇数的顶点为奇点；称度为偶数的顶点为偶点.（1）无向图中所有结点的度数之和等于边数的两倍;（2）有向图中所有结点的出度(入度)之和等于边数。握手定理:推论：任何图的奇结点必为偶数个。d(v1)=d(v3)=d(v4)=4,d(v2)=2.(环e6在计算d(v4)时算作两次)图的术语3、完全图任意两顶点都相邻的简单图（既没有环也没有重边）,称为完全图.n个定点的完全图记为Kn.K4K3K5图的术语4、二分图（二部图）（X,Y;E）二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y;(X,Y)也称为图的二分划。完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,n戊甲乙丙丁工人工作DCBA图的术语5、子图有两个图G和H，如果称图H是图G的子图，记为若且称H是G的真子图。称H是G的生成子图.如果，e1e3e2Gv3v4v5v2v1H1:真子图v3v5v2v1H2:生成子图e1e3e2v3v4v5v2v16、顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为G[W]。导出子图G[V-W]记为G-W，即它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。e1e3e2Gv3v4v5v2v1e3e2v3v4v2G[v2,v3,v4]G-{v1,v5}e1e3e2v3v4v5v2v16、边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为G[F]。记G-F表示以E(G)\F为边集的G的生成子图，它是从G中删除F中的边所得到的子图。e1e3e2Gv3v4v5v2v1G[e1,e2,e3]G-

e1e1e3e2v3v4v5v2v1e1e3e2v3v4v2v1说明：一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下面举几个实际生活中的例子：例2铁路交通图北京天津济南青岛连云港上海南京徐州郑州武汉用点表示城市用点与点之间的连线表示两城市间的铁路线诸如此类的还有电话线分布图、煤气管道图、航空线路等等例3球队比赛的情况v5v4v3v1v2用点v1v2v3v4v5代表五个球队某两个队比赛过，就在这两个队所对应的点之间连一条线，从上面的例子可知，可以用由点及点与点之间的连线所构成的图，去反映实际生活中，某些对象之间的某个特定的关系。一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系并不重要。所以，图论中的图与几何图、工程图等是不同的。例3也可以用下图表示(1)对象之间的“关系”具有“对称性”:象上面的两个例子

(2)对象之间的“关系”是“非对称的” 例如人们之间的认识关系，甲认识乙并不意味着乙也认识甲；比赛中的胜负关系，甲胜乙和乙胜甲不同。反映这种非对称的关系，只用一条连线就不行了。

为了反映这种关系，我们用一条带箭头的连线表示。v1v2v3v4v5如例2中球队胜了，可从v1引一条带箭头的连线到v2，每场比赛的胜负都用带箭头的连线标出，即可反映五个球队比赛的胜负情况。如下图v5v4v3v1v2由图可知，v1三胜一负，v4打了三场球，全负等等类似胜负这种非对称性的关系，在生产和生活中也是常见的，如交通运输中的“单行线”，部门之间的领导和被领导关系，一项工程中各工序之间的先后关系等等。为适合使用计算机对图进行存储和处理，需要用矩阵表示图。常用的有：邻接矩阵、关联矩阵等。

图的矩阵表示（1）邻接矩阵(点点)无向图G有向图G赋权图G的权矩阵A=(aij

)

n×n

,例4：写出右图的邻接矩阵：v1v2v3v4解：例5：写出右图的邻接矩阵：图的矩阵表示（2）关联矩阵(点边)无向图G有向图G解：例6：写出右图的关联矩阵：图的连通性1、通路与路径在图G中，顶点与边相互交错的有限非空序列称为一条从v0到vk的通路，记为;边不重复但顶点可重复的通路称为道路，记为;边与顶点均不重复的通路称为路径，记为.通路道路路径通路：wcxdyhwbvgy路径：xcwhyeuavabdefghcuvyxw设G＝(V，E)，(V0，V1，…，Vk)是G中的一条道路，则称V0到Vk连通或可达。说明：对无向图而言，若V0到Vk可达，则Vk到V0也可达。对有向图而言则未必。定义２：（１）任意两点均有路径的图称为连通图．（２）起点与终点重合的路径称为圈．（３）连通而无圈的图称为树．圈：uavbwhyeuabdefghcuvyxw无向图的连通性：若Ｇ＝(Ｖ，Ｅ)中任两个不同顶点都连通，则称此无向图是连通的。定理：任意一个连通无向图的任两个不同顶点都存在一条简单道路。连通分图：图Ｇ可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为Ｇ的连通分图。有向图的连通性：

(1)弱连通：若Ｇ＝(Ｖ，Ｅ)对应的无向图是连通图，则称Ｇ为弱连通。(2)强连通：若Ｇ＝(Ｖ，Ｅ)中任两点间都有路，即对ａ与ｂ，ａ到ｂ可达，ｂ到ａ可达，称Ｇ为强连通。用邻接矩阵讨论图G的连通性质：

在邻接矩阵中，若aij＝１，表明vi到vj有一条边，即vi到vj可达；若aij

＝０不说明vi到vj没有道路，若通过其他点中转，也有可能连通。作邻接矩阵的普通矩阵乘法：

bij的值表示vi到vj路长为２的道路条数，一般地，就有：定理:Am的元素mij表示vi到vj长度为m的道路条数。定义3：设P(u,v)是赋权图G中u到v的路径，则：（1）为路径P的权；（2）从u到v的具有最小权的路P*(u,v)，称为u到v的最短路。76528936uvyxw如果图G中具有一条经过所有边一次且仅一次的回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边一次且仅一次的路径,称欧拉路。

欧拉（Euler）图Euler路：ydxcwhyeuavfygvbwabdefghcuvyxw定理:(1)连通无向图G是欧拉图的充要条件是G的每个结点均为偶结点;(2)连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉路必始于一个奇结点而终止于另一个奇结点.

abcdef在下左图中,所有结点均为偶结点,故为欧拉图.一条欧拉回路为：abcdefcebfa.abcde在下右图中有一条欧拉路bcdeabe.

例6：如下图是某街道图形.洒水车从A点出发执行洒水任务.试问是否存在一条洒水路线,使洒水车通过所有街道且不重复而最后回到车库B？

ABCDFEG解此问题即为求证图中是否存在A到B的欧拉路.由于图中只有A,B为奇结点,因此这样的洒水线路是存在的,例如,ACDEFBGCFGAB或AGFEDCFBGCAB,等等.

例7：下左图是一幢房子的平面图,前门进入一个客厅b,由客厅通向四个房间.如果要求每扇门只能通过一次,现在由前门进入,能否通过所有的门走遍所有的房间(包括客厅),然后从后门走出？

dacebfbfadec解将四个房间和一个客厅及室外作为结点,门作为边画出上右图.由于b和e是仅有的两个奇结点,故从前门进、后门出的欧拉路是不存在的,即本题无解.

如果把“前门进、后门出”这一条件去掉,则存在“每扇门通过一次且仅一次”的走法.请同学找出具体的走法.

有向图的欧拉定理：

不含出/入度为０的孤立顶点的有向图具有欧拉路的充要条件是：除了可能有２个顶点，一个入度比出度大１，一个出度比入度大１，其余顶点出度等于入度。推论：不含出/入度为０的孤立顶点的有向图具有欧拉回路的充要条件是：所有顶点出度等于入度。如果图G中具有一条经过所有结点一次且仅一次的回路(称哈密尔顿回路)简称Ｈ回路，则称之为哈密尔顿图。如果图G中具有一条经过所有结点一次且仅一次的路，称为哈密尔顿路，简称Ｈ路哈密尔顿（Hamilton）图

所谓哈密尔顿回路,起源于一个名叫“周游世界”的游戏,它是由英国数学家哈密尔顿(Hamilton)于1859年提出的.他用一个正十二面体的20个顶点代表20个大城市(见下左图),这个正十二面体同构于一个平面图(见下右图).要求沿着正十二面体的棱,从一个城市出发,经过每个城市恰好一次,然后回到出发点.这个游戏曾风靡一时,它有若干个解.定理：设Ｇ＝(Ｖ，Ｅ)是ｎ个顶点的简单图，如果任何一对顶点的度之和≥ｎ－１，则Ｇ中一定有Ｈ道路(n>=2)。注意:

此定理条件显然不是必要条件，如ｎ≥６的ｎ边形，二个顶点度之和＝４，４＜ｎ－１，而ｎ边形显然有Ｈ道路。推论：

Ｇ＝(Ｖ，Ｅ)是ｎ≥３的简单图，若任何一对顶点的度之和≥ｎ，则Ｇ必有哈密顿回路。

要判别一个图不存在Ｈ道路，Ｈ回路，也不是很容易的，只能对无向图给出一些必要条件：（1）Ｈ道路存在的必要条件：１）连通２）至多只能有二个顶点的度＜２，其余顶点的度≥２。bcda（2）Ｈ回路存在必要条件：对Ｖ的任一非空真子集Ｓ，Ｇ－Ｓ的连通分图个数≤|Ｓ|。解：取Ｓ＝｛A1，A2

｝G－Ｓ存在3个分图

根据H道路存在的必要条件之二，可知：H道路不存在。用图论思想求解以下各题例8、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，构成一个图,根据此图便可找到渡河方法.问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。

将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.

从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.例9:证明：在任意6人的集会上，总有3人互相认识，或总有3人互相不认识。解：以顶点表示人，以边表示认识，得6个顶点的简单图G。问题：3人互相认识即G包含K3为子图，3人互相不认识即G包含（3,0）图为子图。某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从{1，2，3，4，5，6)中任取一数．由于工艺及其它原因，制造锁具时对5个槽的高度有两个限制：(1)至少有3个不同的数；(2)相邻两槽的高度之差不能为5．满足以上条件制造出来的所有互不相同的锁具称为一批．我们的问题是如何确定每一批锁具的个数?例10：1994年全国大学生数学建模竞赛B题(锁具装箱)中关于锁具总数的问题可叙述如下：解：该问题用图论中的邻接矩阵解决较为简单。设：x表示一批锁具的个数

，

t表示相邻两槽高度之差不为5的锁具数，即：满足限制条件(2)的锁具数，s表示相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数，即：满足限制条件(2)但不满足限制条件(1)的锁具数．则x=t-s我们用图论方法计算t和s.

构造无向图

在G中每一条长度为4的道路对应于一个相邻两槽高度之差不超过5的锁具，即满足限制条件（2）的锁具，反之亦然，于是可以通过G的邻接矩阵A来计算t的值因此，

数学建模-图论又令

其中yi表示满足限制条件(2)但不满足限制条件(1)且首位为i的锁具数,（i=1,2,3,4,5,6),显然y1=y6,y2=y4=y3=y5,于是我们只需要计算y1和y2.计算y1可分别考虑槽高只有1，（1、2），（1、3），（1、4），（1、5）的情形．若只有1，这样的锁具效只有1个，若只有1和i(i=2,3,4,5)，这样的锁具数同理，计算y2时应考虑槽高只有2,21,23,24,25,26时的情形，类似计算可得

y2=(24-1)×5+1=76．于是，s=61×2+76×4=426，x=6306-426=5880.该算法既易理解又易操作并且又可扩展．公交线路选择问题：在给定某城市公交线路的公交网信息后，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。

12345图中由两条公交线路组成，实线表示第一条线路，依次经过站点1,3,4,5，虚线表示第二条线路，依次经过站点2,3,5。首先考虑换乘次数最少的线路选择模型，首先建立直达矩阵如下：12345计算A2得到：由于A2为非零矩阵，所以任意两站点经过换乘一次都可到达，由于问题较简单，结果显然正确。一般地，比较A=(aij),A2=(a(2)ij),…,Ak=(a(k)ij)中的(i,j)元够成的向量中第一个非零向量的上标即为出行换乘的最少次数。12345接下来考虑出行时间最短的模型，建立直达距离矩阵：下面利用Floyd矩阵算法可计算出出行时间最短的路线。定义T*T=(t(2)ij),t(2)ij=min{min1<=k<=5{tik+tkj},tij},t(2)ij表示从站点i到站点j的至多换乘一次的最短时间。

41235利用matlab编写程序如下：T=[0inf123;inf01inf2;11011;2inf101;32110];n=length(T);T2=zeros(n);fori=1:nforj=1:nT2(i,j)=min(min(T(i,:)+T(:,j)'),T(i,j));endendT2计算结果为：T2=

0212220122110112210122110

12345类似可计算出T3，T4，实际上T2的值已为出行路线的最短时间，例如T2（2,5）=2，说明站点2到站点5的最短时间为2站路时间。思考：最