应用数学妙用

《应用数学妙用》由会员分享，可在线阅读，更多相关《应用数学妙用（57页珍藏版）》请在装配图网上搜索。

1、图论模型图论模型1、循环比赛的名次循环比赛的名次2、社会经济系统的冲量过程社会经济系统的冲量过程3、效益的合理分配效益的合理分配4 4、最短路、最短路及应用及应用5、最小部分树及应用最小部分树及应用6、案例分析、案例分析数学建模暑期培训班数学建模暑期培训班一、循环比赛的名次一、循环比赛的名次 n支球队循环赛，每场比赛支球队循环赛，每场比赛只计胜负，没有平局。只计胜负，没有平局。根据比赛结果排出各队名次根据比赛结果排出各队名次方法方法1：寻找按箭头方向通寻找按箭头方向通过全部顶点的路径。过全部顶点的路径。123456312456146325方法方法2：计算得分：计算得分：1队胜队胜4场，场，2,

2、3队各胜队各胜3场，场，4,5队各胜队各胜2场，场，6队胜队胜1场。场。无法排名无法排名2,3队，队，4,5队无法排名队无法排名6支球队比赛结果支球队比赛结果32，4 5排名排名 132456 合理吗合理吗123(1)123(2)1234(1)1234(2)1234(3)1234(4)循环比赛的结果循环比赛的结果竞赛图竞赛图：每对顶点间都有边相连的有向图每对顶点间都有边相连的有向图3个顶点个顶点的竞赛图的竞赛图名次名次1，2，3(1,2,3)并列并列1,2,3,42,(1,3,4)(1,3,4),24个顶点个顶点的竞赛图的竞赛图名次名次(1,2),(3,4)1,2,3,4?1234123412

3、34(1)(2)(3)1234(4)竞赛图的竞赛图的3种形式种形式 具有唯一的完全路径，如具有唯一的完全路径，如(1)；双向连通图双向连通图任一对顶点存在两条有任一对顶点存在两条有向路径相互连通，如向路径相互连通，如(4)；其他，如其他，如(2)，(3)。竞赛图竞赛图的性质的性质 必存在完全路径；必存在完全路径；若存在唯一的完全路径，则由它确定的顶若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如点顺序与按得分排列的顺序一致，如(1)。TeAes)1,1,1(,级得分向量1)1,1,2,2()1(TAes级得分向量2)2,1,2,3()1()2(TAss00011000110

4、00110AEvvEvvajijiij,0,11234(4)双向连通竞赛图双向连通竞赛图G=(V,E)的名次排序的名次排序邻接矩阵邻接矩阵Tnssss),(21得分向量得分向量TTss)3,3,5,5(,)3,2,3,3()4()3(eAAsskkk)1()(?,)(kskTTss)8,5,8,9(,)5,3,6,8()6()5(TTss)13,9,17,21(,)9,8,13,13()8()7(.ii其中:s 表示顶点的得分双向连通竞赛图的名次排序双向连通竞赛图的名次排序 对于对于n(3)个顶点的双向连通竞赛图，存在个顶点的双向连通竞赛图，存在正整数正整数r，使邻接矩阵，使邻接矩阵A 满足满

5、足Ar 0，A称称素阵素阵seAkkklim 素阵素阵A的最大特征根为正单的最大特征根为正单根根，对应正特征向量，对应正特征向量s，且，且eAAsskkk)1()(0001100011000110A排名为排名为1，2，4，3sskk)(,)(归一化后Ts)230.0,167.0,280.0,323.0(,4.1用用s排名排名1234(4)1,2,3,4?000100100100110000001010111000111010ATTTTssss)16,25,21,32,28,38(,)9,12,7,16,10,15()3,4,3,9,5,8(,)1,2,2,3,3,4()4()3()2()1(1

6、234566支球队比赛结果支球队比赛结果Ts)104.0,150.0,113.0,231.0,164.0,238.0(,232.2排名次序为排名次序为1，3，2，5，4，6v1能源利用量；能源利用量；v2能源价格；能源价格；v3能源生产率；能源生产率；v4环境质量；环境质量；v5工业产值；工业产值；v6就业机会；就业机会；v7人口总数。人口总数。二、社会经济系统的冲量过程二、社会经济系统的冲量过程系统的元素系统的元素图的顶点图的顶点元素间的影响元素间的影响带方向的弧带方向的弧影响的正反面影响的正反面弧旁的弧旁的+、号号带符号的有向图带符号的有向图影响影响直接影响直接影响符号符号客观规律；方针政

7、策客观规律；方针政策例例 能源利用系统的预测能源利用系统的预测+-+-+-+v2v1v3v4v6v7v5Evvvvvvajijijiij若，为若为若，0,110000001100000001000011000000001001000000010001110A带符号有向图带符号有向图G1=(V,E)的邻接矩阵的邻接矩阵AV顶点集顶点集 E弧集弧集定性模型定性模型-vivj+某时段某时段vi 增加导致增加导致下时段下时段vj 增加增加减少减少带符号的有向图带符号的有向图G1+-+-+-+v2v1v3v4v6v7v50000005.1100000005.100002.13.0000000001002

8、00000007.00002.18.05.00W加权有向图加权有向图G2及其邻接矩阵及其邻接矩阵W定量模型定量模型某时段某时段vi 增加增加1单位导致单位导致下时段下时段vj 增加增加wij单位单位jwivvij的特例视为 WAv70.311.511.51.20.8-2-2-0.7-0.5v1v2v3v4v5v6加权有向图加权有向图G2,2,1,0,2,1),1()()1(tnitptvtviiininiiijjiijjtpatptpwtp11)()1(),()1(或)1()()1(tptvtv冲量过程冲量过程（Pulse Process)研究由某元素研究由某元素vi变化引起的系统的演变过程变

9、化引起的系统的演变过程 vi(t)vi在时段在时段t 的的值值；pi(t)vi在时段在时段t 的的改变量改变量(冲量冲量)(,),(),()(),(,),(),()(2121tptptptptvtvtvtvnnjwivvij冲量过程模型冲量过程模型Wtptp)()1(Atptp)()1(或或231-10010-12-21-110-11-11-10103-32-211-1能源利用系统的预测能源利用系统的预测简单冲量过程简单冲量过程初始冲量初始冲量p(0)中中某个分量为某个分量为1，其余为，其余为0的冲量过程的冲量过程若开始时能源利用量有突然增加，预测系统的演变若开始时能源利用量有突然增加，预测系

10、统的演变)0()0(pv)1()()1(tptvtvAtptp)()1(设设能源利用系统的能源利用系统的 p(t)和和v(t)-110-11-100011-10000t4p3p5p6p7p2p4v3v2v1v5v6v7v01000000100000001p简单冲量过程简单冲量过程S的稳定性的稳定性 任意时段任意时段S的各元素的值和冲量是否为有限的各元素的值和冲量是否为有限(稳定稳定)S不稳定时如何改变可以控制的关系使之变为稳定不稳定时如何改变可以控制的关系使之变为稳定 S冲量稳定冲量稳定对任意对任意 i,t,|pi(t)|有界有界 S值稳定值稳定对任意对任意 i,t,|vi(t)|有界有界值稳

11、定值稳定冲量稳定冲量稳定)1()()1(tptvtvWtptp)()1(tWptp)0()(S的稳定性取决于的稳定性取决于W的特征根的特征根记记W的非零特征根为的非零特征根为 S冲量稳定冲量稳定|1 S冲量稳定冲量稳定|1且均为单根且均为单根 S值稳定值稳定 S冲量稳定冲量稳定且且 不等于不等于10000001100000001000011000000001001000000010001110A对于能源利用系统的邻接矩阵对于能源利用系统的邻接矩阵A)1()(2352f特征多项式特征多项式76)2(,2)1(ff)2,1(能源利用系统存在能源利用系统存在冲量冲量不稳定不稳定的简单冲量过程的简单冲

12、量过程简单冲量过程简单冲量过程S的稳定性的稳定性 简单冲量过程的稳定性简单冲量过程的稳定性 改进的玫瑰形图改进的玫瑰形图S*带符号的带符号的有向图双向连通，且存在一个有向图双向连通，且存在一个位于所有回路上的中心顶点。位于所有回路上的中心顶点。回路长度回路长度 构成回路的边数构成回路的边数回路符号回路符号 构成回路的各有向边符号构成回路的各有向边符号+1或或-1之乘积之乘积ak长度为长度为k的回路符号和的回路符号和r使使ak不等于不等于0的最大整数的最大整数 S*冲量稳定冲量稳定 )1,2,1(rkaaar-krk,1ra 若若S*冲量稳定，则冲量稳定，则S*值稳定值稳定 1r1kka+-+-

13、+-+v2v1v3v4v6v7v5简单冲量过程简单冲量过程S*的稳定性的稳定性 a1=0,a2=(-1)v1v2 (-1)v2v1=1a3=(+1)v1v3v5v1+(-1)v1v4v7v1+(+1)v1v3v2v1=1,a4=0,a5=1,r=5 S*冲量稳定冲量稳定 )1,2,1(rkaaar-krk,1ra352aaa(-1)v1v2(+1)v1v2(由鼓励利用变为限制利用由鼓励利用变为限制利用)a2=-1+S*冲量不稳定冲量不稳定)1()(2352fA的的特征多项式特征多项式且为单根12/)31(,1,0,0iiS*冲量稳定冲量稳定 S*冲量稳定冲量稳定|1且均为单根且均为单根v1利用

14、量利用量,v2价格价格v7+-+-+-+v2v1v3v4v6v5 若S*冲量稳定，则冲量稳定，则S*值稳定值稳定 1r1kka1,0,1,1,0,54321aaaaa S*冲量稳定冲量稳定 )1,2,1(rkaaar-krk,1rav3能源生产率能源生产率 v5工业产值工业产值1,1,5353aaaa(-1)v3v5 违反客观规律违反客观规律S*值不稳定值不稳定S*值值稳定稳定(+1)v3v5(-1)v3v5能源利用系统的值不应稳定？能源利用系统的值不应稳定？-+-+-+v2v1v3v4v6v7v5+三、三、效益的合理分配效益的合理分配11321xxx457323121xxxxxx例例甲乙丙三

15、人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元，三人合作获利三人合作获利11元。又知每人单干获利元。又知每人单干获利1元。元。问三人合作时如何分配获利？问三人合作时如何分配获利？记甲乙丙三人分配为记甲乙丙三人分配为),(321xxxx 解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)1,321xxx)(1Ivxniiniivxi,2,1),(212121),()()(0)(sssvsvssvv,2,1nI集合(1)Shapley合作对策合作对策满足实函数，子集)(svIs I,v n人合作对策，

16、人合作对策，v特征函数特征函数),(21nxxxxn人从人从v(I)得到的分配，满足得到的分配，满足v(s)子集子集s的获利的获利!)!1()!()(nssnswniisvsvswxiSsi,2,1),()()(公理化方法公理化方法 s 子集子集 s中的元素数目，中的元素数目，Si 包含包含i的所有子集的所有子集)(sw由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值)()(isvsv i 对合作对合作s 的的“贡献贡献”)(siShapley合作对策合作对策三人三人(I=1,2,3)经商中甲的分配经商中甲的分配x1的计算的计算 1/3 1/6 1/6 1/3)1()()(s

17、vsvsw)(sws)1()(svsv)1(sv)(sv1S1 1 2 1 3 I1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x1=13/3类似可得类似可得 x2=23/6,x3=17/6)1()()(11svsvswxSs1 2 2 3若甲乙合作获利若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，元，乙丙合作获利乙丙合作获利4元，元，三人合作获利三人合作获利11元。元。每人单干获利每人单干获利1元。元。合作对策的应用合作对策的应用:例例1 污水处理费用的合理分担污水处理费用的合理分担20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123

18、污水处理，排入河流污水处理，排入河流三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水由上游城镇送往下游城镇由上游城镇送往下游城镇)Q1=5Q3=5Q2=3Q污水量，污水量，L管道长度管道长度建厂费用建厂费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L230)3(,160)2(,230573)1(712.0CCC35020566.0)35(73)2,1(51.0712.0C36538366.0)53(73)3,2(51.0712.0C46358566.0)55(73)3,1(51.0712.0C460)3()1(CC污水处理的污水处理

19、的5 种方案种方案1）单独建厂）单独建厂620)3()2()1(1CCCD总投资总投资2）1,2合作合作3）2,3合作合作4）1,3合作合作580)3()2,1(2CCD总总投资投资595)3,2()1(3CCD总投资总投资合作不会实现合作不会实现55638)35(66.020566.0)535(73)3,2,1(51.051.0712.05CD5）三城合）三城合作总投资作总投资D5最小最小,应联合建厂应联合建厂 建厂费：建厂费：d1=73(5+3+5)0.712=453 12管道费：管道费：d2=0.66 50.51 20=30 23管道费：管道费：d3=0.66 (5+3)0.51 38=

20、73D5城城3建议：建议：d1 按按 5:3:5分担分担,d2,d3由城由城1,2担负担负城城2建议：建议：d3由城由城1,2按按 5:3分担分担,d2由城由城1担负担负城城1计算：计算：城城3分担分担d1 5/13=174C(3),城城2分担分担d1 3/13+d3 3/8=132C(1)不不同同意意D5如何分担？如何分担？230)3(160)2(230)1(CCC0)3()2()1(,0)(vvvv3,2,1I集合特征函数特征函数v(s)联合联合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资),(321xxxx 三城从三城从节约投资节约投资v(I)中得到的分配中得到的分配403

21、50160230)2,1()2()1()21(CCCv 64556230160230)3,2,1()3()2()1()(0)31(25365230160)3,2()3()2()32(CCCCIvvCCCv Shapley合作对策合作对策计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x1)1()()(svsvsw)(sws)1()(svsv)1(sv)(svs1 1 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1=19.7,城城1 C(1)-x1=210.4,城城2 C(2)-x2=127

22、.8,城城3 C(3)-x3=217.8三城在总投资三城在总投资556中的分担中的分担x2=32.1,x3=12.2x2最大，如何解释？最大，如何解释？230)3(160)2(230)1(CCC)1()()(11svsvswxSs合作对策的应用合作对策的应用 例例2 派别在团体中的权重派别在团体中的权重 90人的团体由人的团体由3个派别组成，人数分别为个派别组成，人数分别为40,30,20人。人。团体表决时需过半数的赞成票方可通过。团体表决时需过半数的赞成票方可通过。1)()32()31()21(,0)3()2()1(,0)(Ivvvvvvvv虽然虽然3派人数相差很大派人数相差很大若每个派别的

23、成员同时投赞成票或反对票，用若每个派别的成员同时投赞成票或反对票，用Shapley合作对策合作对策计算计算各派别在团体中的权重。各派别在团体中的权重。3/1321xxx权重团体团体 I=1,2,3，依次代表，依次代表3个派别个派别否则否则，的成员超过的成员超过定义定义特征函数特征函数045,1)(ssv优点：优点：公正、合理，有公理化基础。公正、合理，有公理化基础。如如n个单位治理污染个单位治理污染,通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共方共同治理的投资同治理的投资Y,及第及第i方不参加时其余方不参加时其余n-1方的投资方的投资zi(i=1,2,n).确定共同治

24、理时各方分担的费用。确定共同治理时各方分担的费用。iijjzyiIv)(其它其它v(s)均不知道均不知道,无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有,)(),2,1(0)(1YyIvniivnii缺点：缺点：需要知道所有合作的获利，即要定义需要知道所有合作的获利，即要定义I=1,2,n的所有的所有子集子集(共共2n-1个个)的特征函数，实际上常做不到。的特征函数，实际上常做不到。),(1nbbb记设只知道设只知道)(iIvbi无无 i 参加时参加时n-1方合作的

25、获利方合作的获利)(IvB及全体合作的获利全体合作的获利0),(21inxxxxxB的分配求各方对获利),(),7,5,4(11321xxxxbB求，即已知求解合作对策的其他方法求解合作对策的其他方法例例.甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元。问三人合作时如何分配获利？元。问三人合作时如何分配获利？（2）协商解）协商解00,AbAxTT11nniiibxxbxxBx11将剩余获利将剩余获利 平均分配平均分配 ixBnBbbnxBnxxiiiii1)(111

26、),7,5,4(.Bb例模模型型以以n-1方合作的获利为下限方合作的获利为下限TTbxA求解求解iiibbnx11 xi 的下限的下限,3),1,3,4(ixBx)2,4,5()1,1,1(xx（3）Nash解解 ),(1nddd记为现状点（谈判时的威慑点）为现状点（谈判时的威慑点）iiiiiidxBxtsdxxma.)(iixd 在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B模模型型0id)(1iiidBndx平均分配获利平均分配获利B3）Nash解解 2）协商解）协商解（4）最小距离解）最小距离解的上限为记xxxxn),(1iiiiiixxBxtsxxnmi.)

27、(2模模型型 第第i 方的边际效益方的边际效益iibBx若令若令nBbbnxiii111),7,5,4(.Bb例)(1Bxnxxiii4）最小距离解）最小距离解 2）协商解）协商解,6),4,6,7(Bxxi)2,4,5()2,2,2(xx（5）满意解）满意解iiiiidedxu满意度Bxtsunmixmaiii.)(di现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模模型型iiiixexd,5）基于满意度的解）基于满意度的解 2）协商解）协商解iiixed,0)(iiiiiiiiideudxdedBu的比例分配中在按iiiiixxBxxx（6）Raiffi 解解jjxbBnjj

28、获利为方合作时的原来无参与当,1)(jininxxxxxjiijj,1,)1(2,2:)1的分配基础上进行方合作获利的分配（在Bnx方再等分方平分，和先由11nnjxj得到再平均取,2,1njijjiiixnxnxnnx)1(21211)4,6,7(),1,3,4(xx与协商解与协商解x=(5,4,2)比较比较11),7,5,4(.Bb例)1252,12113,324（x求解合作对策的求解合作对策的6种方法（可分为三类）种方法（可分为三类）Shapley合作对策合作对策A类类B类类!)!1()!()(nssnswniisvsvswxiSsi,2,1),()()()(),(IvBiIvbi只需I

29、ssv),(需要所有协商解协商解)(1iiixBnxx下限ixNash解解 )(1iiidBndx现状id最小距离解最小距离解)(1Bxnxxiii上限ix满意解满意解)(iiiiiiiiideudxdedBudi现状现状,ei理想理想iiiixexd,iibBx,1bAxB类类4种方法相同种方法相同例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙),仅当资方与至少仅当资方与至少一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？Raiffi解解C类类)(),(IvBiIvbi只需方再等分方平分，和先由上限对每个11,nnjxjj10)(),10,1

30、0,0(),(.IvBbiIvbBi)67.1,67.1,67.6().(xShapleyA)0,0,10(,xbBxii)0,0,10(1TTbAx)83.0,83.0,34.8(xijjiiixnxnxnnxRaiffiC)1(21211).()0,0,10(xB类：计算简单，便于理解，可用于各方实类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者。力相差不大的情况；一般来说它偏袒强者。C类：类：考虑了分配的上下限，又吸取了考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者。的思想，在一定程度上保护弱者。A类：公正合理；需要信息多，计算复杂。类：公

31、正合理；需要信息多，计算复杂。求解合作对策的三类方法小结求解合作对策的三类方法小结四、最短路径问题及其应用四、最短路径问题及其应用定义：定义：(1)设设 是赋权图是赋权图G中从中从u到到v的路径，则称的路径，则称 为路径为路径P的的权权;(2)在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最的具有最 小权的路小权的路 ，称为，称为u到到v的的最短路最短路。(,)p u v()()()e E Pw Pw e*(,)P u v 最短路问题就是从给定的网络图中找出任意两点最短路问题就是从给定的网络图中找出任意两点间距离最短的一条路，其中距离只是权数的代称（在间距离最短的一条路，其中距离

32、只是权数的代称（在实际网络中，权数可指时间、费用等）。如选址、管实际网络中，权数可指时间、费用等）。如选址、管道铺设时的选线、设备更新、投资等都可以归给为求道铺设时的选线、设备更新、投资等都可以归给为求最短路的问题。最短路问题有一个重要而明显的性质最短路的问题。最短路问题有一个重要而明显的性质（算法思想）：最短路是一条路径，且最短路的任一（算法思想）：最短路是一条路径，且最短路的任一段也是最短路。段也是最短路。求最短路的方法求最短路的方法：1)求从一点到其余各点间的求从一点到其余各点间的Dijkstra算法算法;2)求任意两点间最短距离的求任意两点间最短距离的矩阵算法矩阵算法(Floyd算法算

33、法)。Dijkstra(标号法）的算法：标号法）的算法：设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非负。不妨边上的权均非负。不妨用用 表示图中两相邻点表示图中两相邻点i和和j的距离；若点的距离；若点I和和j不相邻，不相邻，则可令则可令 ，显然，显然 ；用；用 表示从点表示从点s到到i点的点的最短距离。现要求从点到某一点最短距离。现要求从点到某一点t的最短路。的最短路。ijdijd 0iid siL)重复第三步，一直到t点得到标号为止。1)s0,ssL 从点 出发,因将此值标在s点旁,表示此点已标号;3)min;,spssspsrrpLLdLdp从已标号的点出发,找出与这些点

34、相邻的的所有未 标号点p.若有 则对 点 标号;Dijkstra算法步骤如下：2)ssrsssrLLd从点 出发,找出与s点相邻的点中距离最小的一个,设为r,将的值标在r点旁,表示此点已标号;矩阵算法步骤（略）例：求下图中顶点v0与v5的最短路径.算法示例解:可以将计算过程用一张表表示出来(见下页表)：由上表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这样从v5往前追踪,得v0到v5的最短路径为：=v0v1v2v4v3v5.W()=9.Dijkstra算法的标号法举例21073645210736452210736452107364510 2 95225

35、599990000最短路径问题实例：医院选址问题1.问题重述：新建居民小区的医院，对该区每一户居民都很重要。如下图是一个新建居民区的示意图，医院建在哪里为好呢？V2V1V3V5V10V7V6V4V9V893218279564813165 在上图中，v1，v，v10表示各居民点，边表示两居民点之间的道路，边上的数值表示两居民点之间的距离（也就是该边的权）.现在需要我们考虑的问题是在这10个居民点中，何处作为新建医院的理想地址，以使所建医院到最远的居民点距离尽可能近（即最远点的病人到医院看病时走的路尽可能短）。V2V1V3V5V10V7V6V4V9V893218279564813165 求出上图中

36、各点间的距离，如下表所示，这样就可以把每个顶点vi对应的最大服务距离L(vi)求出来.2.问题求解：显然可以看出，上图是一个连通无向图，记为，.任取vi V(i=1,2,10)，考察vi与中其他顶点间的最短路（也称为距离）：（vi，v1），（vi，v2），（vi，v），把这10个距离中最大的数称为顶点 vi的最大服务距离，记为L(vi).最短路径问题实例：医院选址问题1 2 3 4 5 6 7 8 9 1010 5 3 6 5 10 10 9 12 1325 0 2 3 4 9 6 8 8 933 2 0 3 2 7 7 6 9 1046 3 3 0 5 7 5 6 7 855 4 2 5 0

37、 5 5 4 7 8610 9 7 7 5 0 2 1 4 5710 6 7 5 5 2 0 1 2 389 8 6 6 4 1 1 0 3 4912 8 9 7 7 4 2 3 0 51013 9 10 8 8 5 3 4 5 0 由于，所以把医院建在v4或v5为较好的选择，进一步调查，如果居民点v的居民比v5多，那么把医院建在v最好.注：注：上表中的，上表中的，1分别代表：分别代表：v1，v，v，v，v，v，v，v，v，v110min()8iiL v v1到各顶点的距离就是上表中的第一行各数，它们中最大的是13，所以L(v1)=13，其它各点的最大服务最大服务距离距离分别为:L(v2)=9

38、，L(v3)=10，L(v4)=8，L(v5)=8，L(v6)=10，L(v7)=10，L(v8)=9，L(v9)=12，L(v10)=13。1.问题重述:1 2 3 4 5 6 1 0 13 51 77 68 502 13 0 60 70 67 593 51 60 0 57 3 624 77 70 57 0 20 555 68 67 36 20 0 346 50 59 2 55 34 0最小生成树实例:有线电视网最优布线问题 卫星加密电视的开播,受到大家的欢迎,要想收看加密电视必须建立一套有线电视网我们考虑这样一个具体问题：设某市六个个区之间的相互距离如下表所示，试确定该表数据形成的网络中，

39、如何布线才能使布线最省？单位：100米五、最小生成树的应用.问题求解:V1V6V3V5V4V260702013675977575568512343650最优布线问题，就是要求任何两地都有链相连，而使总线路最短，这个问题在图论中也称为最小树问题作下图，其中顶点v1，v，v，v，v，v 分别表示两区之间的距离 对于上图，我们要找使布线最省的网络模型。图论中的破圈法可以解决这个问题，具体过程如下：在圈v1vvv1中，去掉最长边vv60，同样去掉圈v1vvv1，vvvv，vvvv，v3 v5vv3，v4v5 v6 v4，v1v3v4v1，v1v6v2v1，v2v5v6v2中最长的边v1v51，v2v4

40、70，v3v457，v3v536,v4v655，v1v477，v1v568，v2v659，v2v567，最后构成的图（如下）就是最省的布线图132503420v2v3v1v6v4v6六、图论模型实例分析 实例一实例一 握手的次数握手的次数 史密斯先生和他太太邀请四对夫妻参加晚会每个人史密斯先生和他太太邀请四对夫妻参加晚会每个人到的时候，房间里的一些人都要与别的一些人握手。到的时候，房间里的一些人都要与别的一些人握手。当当然，每个人都不会与自己的配偶握手，也不会跟同一然，每个人都不会与自己的配偶握手，也不会跟同一个个人握手两次。之后，史密斯先生问每个人和别人握了人握手两次。之后，史密斯先生问每个

41、人和别人握了几几次手，他们的答案都不一样。那么，史密斯太太和别次手，他们的答案都不一样。那么，史密斯太太和别人人握了几次手呢握了几次手呢?这个问题具有挑战性的原因是因为它没有一个明这个问题具有挑战性的原因是因为它没有一个明显的起始点，但如果对此建立一个图模型，问题就变显的起始点，但如果对此建立一个图模型，问题就变得很简单了。得很简单了。分析：从题目我们得到了哪些信息分析：从题目我们得到了哪些信息?史密斯和太太邀请四对夫妻参加晚会房间里共有10 人;每个人都不会与自己的配偶握手握手的两个人不是配偶;每个人都不会跟同一个人握手两次两个人间的握手最多是一次;史密斯先生问每个人和别人握了几次手，他们的

42、答案都不一样除史密斯先生外，每个人和别人握手的次数都不一样;除史密斯先生外，每个人握手的次数最多是8次，最少为0次;房间里除了史密斯先生外的9个人，他们与别人握手的次数分别为0，1，2，3，4，5，6，7，8次。要知道史密斯太太和别人握手的次数，只需确定除史密斯先生外的9人中哪一个是史密斯太太即可。根据以上信息，建立图模型：由图可知：8 8号的配偶是号的配偶是0 0号；号；7 7号的配偶是号的配偶是1 1号；号；6 6号的配偶是号的配偶是2 2号；号；5 5号的配偶是号的配偶是3 3号；号；史密斯太太是史密斯太太是4 4号，所以史密斯太太和别号，所以史密斯太太和别 人握了人握了4 4次次 其余例子详见word格式：