图论的发展及其在现实生活中几个应用

图论的1736年是图论的历史元年．这一年，欧拉（L•Euler）（Königsberg）七桥问题，了关于图论的首篇文章．欧拉也因此被称为图论之父．哥尼斯堡城濒临蓝色的的海，城中有一条普莱格尔（Pregel）河，河的两条谁能够从A，B，C，D四个陆地中的任一个地方出发一次走遍所有的7座桥，F(面数)＋V(顶点数)E(棱数)这个证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十面体五种．这个定理成为拓扑学的第一个定理，这个被认为开启了数学史上新11)．191936弈问题、棋盘上马的行走路线问题等，[2]随着对这些问题的深入研究，图论又产生了新是图论研究的基本问题之一，路、中国邮路问题、哈密顿问题、树与图的支撑树、匹配问题都是连通性的典型问题地图问题即是对无论多么复杂的地图只需用四了问题即给定一个图如果要求把所有顶点涂上颜色使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色?这个问题叫做图的点问题．如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色?这个问题叫做边的问题边的问题可以转化为点问题由这些问题人们逐渐丰富并发展了图1847克希霍夫将树的概念和理论应用于工程技术的电网路方程组的研究．1936年匈牙利的定义 V

VEDE为边集，它是笛卡尔积VV例[4]（渡河问题）一个摆渡人要把一只狼，一只羊和一捆菜运过河去，由于船很解F表示摆渡人，WSCFWSC16FWSC166WSC、FW、FC、WS、SCFFC表示人和菜在原岸而狼和羊在对岸，这当然是不允许的．因此，10102.1：

S

FWSC到⑴FWSCWCFWCCFSCSFS⑵FWSCWCFWCWFWSSFS旅行问销员从他所在的城市出发途经其余n1定义 给定图G

V,

（G为无向图或有向图，设WER（R集G中任意的边evivj

G为有向图时，e

vi,v

wije上的权，并将wijeG为带权图，此时常将带权图G记作VE,W．设GG最邻近法

We为G的权，记作WG，即WG

WeB7AC86例[8]某流动售票员居住在A城，为推销货物他要B、C、D城后返回A城B7AC86D 步骤如下图①—A①A②A③A④最短距离为定义 设G

V,

，G

为两个图（同为无向图或同为有向图若VVEEG是G的子图，G为GGGVVEE则称G为G的真子图，若VV，则称G为G定义 定义2.3.3[11] 如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵2.3.4[12]设无向连通带权图G

V,

，T是G的一棵生成树，T之和称为TG的所有生成树中，权最小的生成树称为G⑴破圈法在G如此继续下去，最后得到的连通图的无圈的生成子图就是G的一棵生成树．旅游线路中的最短问题对于旅客来说，要求在最短的时间内用最少的钱来旅游例[16]公园的路径系统图如图2.3，其中S为，T为出口，A，B，C，D，为五个景点，现求如何能使观光旅游车从S到出口T所经过的距离最短DA7 7 7 用破圈法求带权的最小生成树的方法求解，求解步骤如下图①—DA7 7 7 ①DA7 7 7 ②DA 7 7 ③DA 7 ④DA5 1 7 ⑤ADAD225SB113 ⑥S到出口TSABED最短距离为“格里斯．而据他后来撰文披露，该问题的真正发现者实际是他是的哥哥 定义 设G为无向标定图，G中的顶点与边的交替序列v

ve i1ejvi称为vi到vi的通路，其中vivi为ejr=1,2,l，vi，vi分别称为l r- i的始点与终点，中边的条数称为它的长度，若i0

v，则称通路为回路．若ili边各异，则称为简单通路，又若vivi，则称为简单回路．若的所有顶点（除 与vi可能相同外）各异，所有边也各异，则称为初级通路或路径，此时又若vivi 则称定义2.4.2[19] 对无环图G的每个顶点涂上一种颜色使相邻的顶点涂不同的颜色，称为对图G的一种．若能用k种颜色给G的顶点，就称对G进行了k，也称G是k—可 的．若G是k—可 的，但不是k1—可 的，就称G是k色图，并称这样的k为G的色数，记作Gk． 定义 在n1（n4）边形 所有顶点均相邻，所得n阶简单图称为n阶轮图．n为奇数的轮图称为奇阶轮图，n为偶定理2.4.1（四色定理 定理 例1[22] ⑴8:00——⑵10:15——⑶12:30——⑷2:45——⑸5:00——⑹7:15—— Brian：AC，G，Carla：G，LP， ：GT，LP，Edward：DE，GT， ：DE，GT，Grance：DE，S， Henry：AC，DE，解2.4.1，8色．DEG≥4；又由定理1G≤4，GACACS2DEG8时间段1：统计学、几何学、图论 时间段3：微分方程、近世代数 时间段4：线性规划故可在安排时间段(1)8:00— (2)10:15—(3)12:30— (4)2:45—例 有8种化学药品需要空运飞越整个国家.运费根据运送的容器数量来确定运送一个容器需要125元.某些药品之间可以发生化学反应,所以把它们放在同一个容器中是很的.这些化学药品被标记成A,B,C,D,E,F,G,H.下面列出的是A:B,E, B:A,C,E,C:B,D, D:C,F,G,E:A,B,F,G, F:A,D,E,G:B,C,D,E, H:D,E,F,解2.4.2,8EH≥4；1H≤4，H＝4．HGFDHGF故将这8种化学药品放置在四个容器内,安排方法为：第一个容器:D, 第二个容器:C,第三个容器:A, 第四个容器:B,定义 非空图G的一个边染色是指给G的边分配颜色，每条边分配一颜色，使得邻接的边分配不同的颜色．对G的边染色所需的最少颜色数称为是边色数，1G．应用k种颜色的边染色称为是k边染色．定义 设G

V,

vV，称vv的度数，简记为度，记作dGv，在不发 时，简记为dv定理 对于任意非空图G1G＝G1G1G定理 设G是一个阶为n，边数为m的图．m(n21G1G1[23]AlvinA3BobB)CarrieCHansonDavidDEdithEIrwinFrankF)和GenaG)的每一位都要与其配偶之外的每位客人比赛．另外,AlvinDavidEdith,Frank,Gena进行一场比赛．若没有人在同一天进行两场比赛,则要在最少天数完成解首先构造图2.5.1,其顶点为住在Alvin的避暑别墅的人,因此VHAB,CDEF,G,H中的两个顶点是邻接的,如果这两个顶点(人)需要进行H的边色数．2G2G 532E4135D41C6F62A

H5

1H51H6Hn7,边数为m16m1615(71)5(n1)H 2．5．2,1H6HH6第一天:Bob第二天:Alvin第三天:Alvin第四天:Alvin第五天:David第六天:Alvin例 来自亚特兰大、波士顿、芝加哥、丹佛、路易维尔、迈阿密以及纳什维亚特兰大（A：波士顿，芝加哥，迈阿密，纳什维尔波士顿（BD)：芝加哥，路易维尔，迈阿密，纳什维尔E)：芝加哥，丹佛，迈阿密F解2.5.2,7VGAB,CDEF,G,G中确定G的边色数．33

G4

1G41G5．此外,Hn7,边数为m13m1312(71)4(n 第一天 亚特兰大－波士 －迈阿 芝加哥第二天：波士顿－亚特兰大－芝加 丹佛第三天：亚特兰大－迈阿 芝加哥－波士 丹佛－第四天：芝加哥－丹佛 亚特兰大－第五天：丹佛－迈阿密路程最短,这个问题学者管梅谷1962定义2.6.1[26] 在图上,从某个顶点出发,对各条边只通过一次,这样的迹称为定义2.6.2[27] 将边e的两个端点再用一条权同样为we的新边连接，即得重复定理2.6.1 若G是Euler图，则G中任意用Fleury算法做出的迹都是G上 定理 设赋权图G经添加重复边集E后得到赋权图G 权值总和wEPweP最小的充要条件是：每条边最多重复一次，并且GE个圈C，其所含重复边的权值之和都不大于所在圈CFleury算法[27]任意选取一个顶点v0,置W0v0ei1ei1和vi除非没有别的边可选择，否则ei1不是GiGe1e2,...,ei2）不能再执行时，算法停止，得到G中一条迹．Euler图求最优环游的算法步骤[27]：Euler图；则转（3；（2． BC8D6E BC8D6EAF dA1，dF1故此图为 图．添加重复边使其变 图，如下 2．6．2，BC D6E6FFleury算法可得到一条最优环游,这条最优环游是:ABCEFECBDEBA李冰．图论的和发展[J]．大众文艺，2010（9：34．耿素云、屈婉玲．离散数学[M]．2版．：高等教育，2009，39（24耿素云、屈婉玲．离散数学[M]．2版．：高等教育乔维声、汤惟．离散数学[M]．西安：西安电子科技大学乔维声、汤惟．离散数学[M]．西安：西安电子科技大 耿素云、屈婉玲．离散数学[M]．2版．：高等教育瑞．图论[M]．3版．：理工大学瑞．图论[M]．3版．：理工大学耿素云、屈婉玲．离散数学[M]．2版．：高等教育瑞．图论[M]．3版．：理工大学瑞．图论[M]．3版．：理工大学2009,30（5：583．刘海英．最短路径问题在管理中的应用[J]．福建广播电视大学学报（29：87．程钊．图论中若干著名问题的历史标记[J]．数学的实践与认识（24：78．耿素云、屈婉玲．离散数学[M]．2版．：高等教育，2004:276．[19]耿素云、屈婉玲．离散数学[M]．2版．：高等教育，2004:333．[20耿素云、屈婉玲．离散数学[M]．2版．：高等教育，2004:332．GaryChartrand、Zhang．图论导引[M]．范益政等，译．：人民邮电出GaryChartrand、Zhang．图论导引[M]．范益政，朱明，龚世才等译．北京：人民邮电，2007：246－247．GaryChartrand、Zhang．图论导引[M]．范益政，朱明，龚世才等译．北京：人民邮电，2007：248—250．耿素云、屈婉玲．离散数学[M]．2版．：高等教育、．GaryChartran