图论方法

引言图论(GraphTheory)是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。BACD哥尼斯堡七桥问题(KönigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理.很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联ABCD例6.1：哥尼斯堡七桥问题1图与网络的基本概念一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图C1C2C3C4根叶2最小支撑树(生成树)一树的定义及其性质无圈连通图称为树(tree)，记为T树的性质：任何树必存在次数为1的点具有n个节点的树T的边恰好为n1条，反之，任何有n个节点，n1条边的连通图必是一棵树ACDBACDBACDBADCB图的生成树:若图G的一个支撑图T是一棵树,则称T是G的一棵生成树(spanningtree).在赋权图G中，一棵生成树所有边上权的和，称为生成树的权。具有最小权的生成树，称为最小树（或最优树）,求最小树有破圈法和避圈法.定理图G有生成树的充分必要条件为图是连通图。定义（最优树）在赋权图G中，一棵生成树所有树柱上权的和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。求最小树的方法有破圈法和避圈法。3最小枝杈树问题v1v7v4v3v2v5v620159162532817412336例10-7破圈法v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v693174123总造价=1+4+9+3+17+23=57v1v7v4v3v2v5v620159162532817412336避圈法v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336总造价=1+4+9+3+17+23=574：最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设为连通图，图中各边有权(表示，之间没有边）,为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。即：),(EVG),(jivvijlijliv,svjvtvsvtv),()(jivvijlL最小。最短路算法中1959年由（狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为算法。下面通过例子来说明此法的基本思想。DijkstraDijkstra条件：所有的权数0ijl思路：逐步探寻。1v2v3v5v7v8v6v4v46761519554471v2v3v5v7v8v6v4v4676151955447下求到的最短路：1v8v1）从出发，向走。首先，从到的距离为0，给标号（0）。画第一个弧。（表明已标号，或已走出）1v8v1v1v1v1v1v)0(从出发，只有两条路可走，其距离为1v),,(21vv),(31vv2）,412l.613l①1v2v3v5v7v8v6v4v4676151955447)0(可能最短路为4}6,4min{},min{},min{13121312llkk),(21vv2v)4(①给划成粗线。③划第二个弧。②给标号（4）。①②1v2v3v5v7v8v6v4v4676151955447)0()4(表明走出后走向的最短路目前看是，最优距离是4。1v8v),(21vv现已考察完毕第二个圈内的路，或者说，已完成的标号。,1v2v①②1v2v3v5v7v8v6v4v4676151955447)0()4(3）接着往下考察，有三条路可走：),,(42vv),,(31vv).,(52vv可选择的最短路为6}44,54,6min{},,min{},,min{2512241213252413dldllkkk),(31vv3v)6(①给划成粗线。③划第3个弧。②给标号（6）。③①②1v2v3v5v7v8v6v4676151955447)0()4()6(4）接着往下考察，有四条路可走：),,(42vv).,(52vv可选择的最短路为8}13,10,8,9min{},,,min{35342524kkkk5v4v),,(43vv).,(53vv),(52vv)8(①给划成粗线。③划第4个弧。②给标号（8）。①②③④1v2v3v5v7v8v6v4676151955447)0()4()6(5）接着往下考察，有四条路可走：),,(42vv可选择的最短路为9}14,13,10,9min{},,,min{57563424kkkk4v),,(43vv),,(65vv),(42vv)8().,(75vv4v)9(①给划成粗线。③划第5个弧。②给标号（9）。①②③④⑤1v2v3v5v7v8v6v4676151955447)0()4()6(6）接着往下考察，有四条路可走：),,(64vv可选择的最短路为13}14,13,16,18min{},,,min{57564746kkkk6v),,(74vv),,(65vv),(65vv)8().,(75vv4v)9()13(①给划成粗线。③划第6个弧。②给标号（13）。①②③④⑤⑥1v2v3v5v7v8v6v4676151955447)0()4()6(7）接着往下考察，有四条路可走：可选择的最短路为14}14,18,14,16min{},,,min{68675747kkkk8v),,(76vv),,(75vv)8(),,(75vv4v)9()13().,(86vv)14(),,(74vv),(86vv,7v)14(①同时给划成粗线。②分别给标号（14）。最后，从逆寻粗线到，得最短路：1v2v3v5v7v8v6v4676151955447)0()4()6()8(4v)9()13()14()14(8v1v86521vvvvv长度为15。例5-3用狄克斯拉算法求解图5-1所示最短路问题。4v1v2v3v4v6v5v722561413412图5-1例5-3网络图解：先将图5-1的网络用矩阵形式表示出来:02142013104641401431025642025207654321VVVVVVVD1v2v3v4v5v6v7v步骤考察点T标号点集标号（表P标号）1v1{v2，…，v7}v1v2v3v4v5v6v70------0+20+525----23456v2v3v4v5v6{v3，…，v7}{v4，…，v7}{v5，v6，v7}{v5，v7}2+22+42+6468--4+14+3587-5+45+15+48696+288{v7}8+18反向追踪，得到最优路线：v1v2v3v4v6v7v5讨论：若先把v7的标号改为永久性标号，该怎麽继续作下去？56v6v7{v5，v7}{v5}v1v2v3v4v5v6v76+2888+18869反向追踪，得到相同的最优路线。在得到从起点到终点的最短路长的同时，还能得到什麽附加信息？（5）D氏标号法（Dijkstra）的特点（获得的附加信息）：1v能得到从（起点）到各点的最短路线和最短路长。第二讲：最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实际应用的例子。例设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表8-21v2v3v4v5v6v131219284059151520294122213014解：把这个问题化为最短路问题。用点表示第i年初购进一台新设备，虚设一个点，表示第5年底。6viv边表示第i年购进的设备一直使用到第j年初（即第j-1年底）。),(jivv1v2v3v4v5v6v131219284059151520294122213014边上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。),(jivv1v2v3v4v5v6v131219284059151520294122213014这样设备更新问题就变为：求从到的最短路问题.1v6v)12(2v3v4v5v6v131219284059151520294122213014⑴1v)0(①⑵12}59,40,28,19,,12min{},,,,min{1615141312kkkkk1v)0(),(21vv给划成彩线。②19}4112,2912,2012,1312,59,40,28,19min{},,,,,,,min{2625242316151413kkkkkkkk⑶)12(2v)19(3v)28(4v5v6v131219284059151520294122213014①1v)0(②),(31vv给划成彩线。28}49,40,33,53,41,32,59,40,28min{},,,,,,,,min{363534262524161514kkkkkkkkk⑷③),(41vv给划成彩线。④40}50,43,49,35,43,41,59,40min{},,,,,,,min{4645363526251615kkkkkkkk⑸)12(2v)19(3v)28(4v)40(5v6v131219284059151520294122213014①1v)0(②③④),(51vv给划成彩线。⑤)12(2v)19(3v)28(4v)40(5v6v131219284059151520294122213014①1v)0(②③④⑤49}55,50,49,53,59min{},,,,min{5646362616kkkkk⑹),(63vv给划成彩线。计算结果：最短路631vvv)12(2v)19(3v)28(4v)40(5v6v1319284059