图与网络模型 图论 数学建模.ppt

《图与网络模型 图论 数学建模.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络模型瑞士数学家欧拉在1736年发表了一篇题为“依据几何位置的解决方法”的论文，有效地解决了哥尼哥尼斯堡“七桥问题”，这是有史以来的第一篇图论论文，欧拉被公认为图论的创始人。18世纪的哥尼斯堡城中流过一条河。河上游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点

2、出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。1857年，英国数学家哈密顿发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个定点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次切仅一次再回到原出发点的路，这就是“环球旅行”问题。如图5-3所示。他与七桥问题不同，前者要在图中找一条经过每边且仅一次的路统称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。哈密顿根据这个问题的特点，给出了一种解法如图5-4所示。在这一时间，还

3、有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。运筹学中的“中国邮路问题”：一个邮递员从邮局出发要走遍他所负责的每一条街道去送信，蚊蝇如何选怎适当的路线可是所走的总路程最短。这个问题就与欧拉回路有密切的关系。而著名的“货郎担问题”则是一个带权的哈密尔顿回路。而著名的“货郎担问题”则是一个带权的哈密尔顿回路问题。图论的第一本专著是匈牙利数学家OKoing写的“有限图与无限图的理论”，发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经

4、历了200年之久，总的来讲这一时期图论的发展是缓慢的。直到20世纪中期，电子计算机的发展以及离散数学问题具有越来越重要的地位，使得作为提供离散数学模型的图论得以迅速发展，成为运筹学中十分活跃的重要分支。目前图论被广泛地应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物、心理学等各个领域，并取得了丰硕的成果。第一节图与网络的基本知识一、图与网络的基本概念1.图及其分类自然界和人类社会中，大量的实物以及事物之间的关系，常可以用图形来描述。例如，为了反映5个队参加的球类比赛请况，可以用点表示球队，用点间连线表示两个队已经比赛过，如图5-5所示。

5、又例如工作分配问题，我们可以用点表示工人与需要完成的工作，点间连线表示每个人可以胜任那些工作，如图5-6所示。这样的例子很多，物质结构、电路网络、城市规划、交通运输、物资调配等也都可以用点和线连接起来的图进行模拟。由上面的例子可以看出，这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间又无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。总之，这里所讲的图是反映对象之间关系的一种工具。图的理论和方法，就是从形形色色的具体的图以及与他们相关的实际问题中，抽象出共同性的东西，找出其归律、性质、方法，在应用到

6、解决实际问题中去定义1.一个图是由点集V={}和V中元素的无序对的一个集合E={}所构成的二元组，记为G=(V,E),V中元素叫做顶点，E中的元素叫做边。当V,E为有限集合时，G成为有限图，否则，成为无限图。本章只讨论有限图。例5.1在图5-7中：V={v1，v2，v3，v4，v5}E={e1，e2，e3，e4,e5}.其中：e1=（v1，v2）e2=（v1，v2）e3=（v1,v3）e4=（v2，v3）e5=（v2，v3）e6=（v3,v4）两个点u，v属于V，如果边（u，v）属于E，则称u，v两点相邻。u，v成为边（u，v）的端点。两边ei,ej

7、属于E，如果他们有一个公共端点u，则称ei,ej相邻。边ei,ej成为点u的关连边。用m（G）=

8、E

9、表示图G中的边数，用年（G）=

10、V

11、表示图G的定点个数。在不引起混淆情况下简记为m,n。对于任一条边（vi,vj）属于E，如果边（vi,vj）端点无序，则他是无向边，此时图G成为无向图。图5-7时无向图。如果边（vi,vj）的端点有序，即他表示以vi为试点，vj为终点的有向边（或称弧），这时图G称为有向图。一条边的两个端点如果相同，称此边为环。如图5-7中的e1。两个点之间多余一条边的，称为多重边。如图5-7中的e4，e5。定义2不含环和多重边的图称

12、为简单图，含有多重边的图成为多重图。以后我们讨论的图，如不加特别说明，都是简单图。有向图中两点之间有不同方向