图和网络模型_图论_数学建模.ppt

图与网络模型 瑞士数学家欧拉在1736年发表了一篇题 为“依据几何位置的解决方法”的论文，有 效地解决了哥尼哥尼斯堡“七桥问题”，这 是有史以来的第一篇图论论文，欧拉被公 认为图论的创始人。18世纪的哥尼斯堡城中流过一条河。河上游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且 仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。 1857年，英国数学家哈密顿发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个定点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次切仅一次再回到原出发点的路，这就是“环球旅行”问题。如图5-3所示。 他与七桥问题不同，前者要在图中找一条经过每边且仅一次的路统称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。哈密顿根据这个问题的特点，给出了一种解法如图5-4所示。 在这一时间，还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。 运筹学中的“中国邮路问题”：一个邮递员从邮局出发要走遍他所负责的每一条街道去送信，蚊蝇如何选怎适当的路线可是所走的总路程最短。这个问题就与欧拉回路有密切的关系。而著名的“货郎担问题”则是一个带权的哈密尔顿回路。而著名的“货郎担问题”则是一个带权的哈密尔顿回路问题。 图论的第一本专著是匈牙利数学家O Koing 写的“有限图与无限图的理论”，发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经历了200年之久，总的来讲这一时期图论的发展是缓慢的。直到20世纪中期，电子计算机的发展以及离散数学问题具有越来越重要的地位，使得作为提供离散数学模型的图论得以迅速发展，成为运筹学中十分活跃的重要分支。目前图论被广泛地应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物、心理学等各个领域，并取得了丰硕的成果。 第一节 图与网络的基本知识 一、图与网络的基本概念 1. 图及其分类 自然界和人类社会中，大量的实物以及事物之间的关系，常可以用图形来描述。例如，为了反映5个队参加的球类比赛请况，可以用点表示球队，用点间连线表示两个队已经比赛过，如图5-5所示。又例如工作分配问题，我们可以用点表示工人与需要完成的工作，点间连线表示每个人可以胜任那些工作，如图5-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属于E，如果他们有一个公共端点u，则称ei, ej相邻。边ei, ej 成为点u的关连边。 用m（G）=|E|表示图G中的边数，用年（G）=|V|表示图G的定点个数。在不引起混淆情况下简记为m,n。 对于任一条边（vi, vj）属于E，如果边（vi, vj）端点无序，则他是无向边，此时图G成为无向图。图5-7时无向图。如果边（vi, vj）的端点有序，即他表示以vi为