资源描述：
《数学建模---5图论.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学建模---图论前言图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。传统的物理、化学、生命科学也都越来越广泛地使用了图论模型方法。从七桥问题说起---关于图模型在哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块:A、C两个小岛和B、D两块陆地（如图）。问题的提出哥尼斯堡七桥问题七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真
2、实故事。ABCD为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现。ABCD1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决了问题。问题分析与模型假设：2.四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的本质无关，因而可视四块陆地为四个点A、B、C、D。1.问题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大小、形
3、状、长短、曲直等均无关，而只要桥存在，因此不妨将其视为一条弧线ABCDABDC对四个陆地A、B、C、D，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点，代表桥的弧线为边。这样一来，能否从一地出发走遍七座桥一次且仅一次再回到出发点就变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。这就是众所周知的这个图能否“一笔画出”的问题。ABCDABDC能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。7“一笔画出”能否从这个图上任一顶点出发，经过每个顶点一次且仅一次而回到出发顶点。旅行商问题能否
4、从这个图选择尽量少的点，使得所有的其余点都和该点集有路径连接。覆盖问题-系统监控模型能否将图中点集分类，使得每一类点集都没有路径连接，最少需要分几类。支配集--仓库分区将该图中所有顶点用不同颜色表示，最少需要几种颜色。8“点着色将该图中所有边用不同颜色表示，最少需要几种颜色。边着色关键路径最大流、最小流问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）问题3(四色问题):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题4(关键路径问
5、题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？一图的基本概念二三最短路问题及其算法四最小生成树问题图的矩阵表示数学建模-图论132021年9月14日一、图的基本概念数学建模-图论142021年9月14日一、图的基本概念图1图2数学建模-图论152021年9月14日一、图的基
6、本概念一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.数学建模-图论162021年9月14日一、图的基本概念数学建模-图论172021年9月14日一、图的基本概念次数为奇数顶点称为奇点，否则称为偶点。数学建模-图论182021年9月14日一、图的基本概念常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d+(v)，与顶点v入关联的边的数目称为入度，记作d-(v)。用N(v)表示图G中所有与顶点v
7、相邻的顶点的集合.任意两顶点都相邻的简单图称为完全图.有n个顶点的完全图记为Kn。数学建模-图论192021年9月14日一、图的基本概念几个基本定理：若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F).设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…vk是G的一条通路.如果通路中没有相同的顶点,则称此通路为路径,简称路.始点和终点相同的路称为圈或回路.一、图的
