图论建模.ppt
《图论建模.ppt》由会员分享,可在线阅读,更多相关《图论建模.ppt(184页珍藏版)》请在三一文库上搜索。
1、数学建模中的图论模型,Seven Bridges of Knigsberg Problem,Knigsberg (now Kaliningrad) , Germany seven bridges over the Pregel river,18th century The residents of Knigsberg wondered if it was possible to take a walking tour of the town that crossed each of the seven bridges over the Pregel river exactly once.,Le
2、onhard Euler,Leonhard Euler solved this Seven Bridges of Knigsberg and published his research in 1736. This paper is regarded as the first paper in the history of graph theory as a subject.,Eulers Answer: There is no tour that uses each edge exactly once. (Even if we allow the walk to start and fini
3、sh in different places.) Can you see why?,Leonhard Euler (1707-1783),Born April 15, 1707 in Basel, Switzerland His father Paul Euler was a Protestant minister University of Basel in 1720 at age 14 1723 completed Masters degree in Philosophy 1726 completed Masters degree in Mathematics,father of grap
4、h theory,Todays Bridges of Knigsberg,A map of Knigsberg (Kaliningrad, as it is now called) after its rebuilding after its destruction in World War II,Todays Bridges of Knigsberg,Bridge 1,Todays Bridges of Knigsberg,Bridge 2,Todays Bridges of Knigsberg,Bridge 3,Todays Bridges of Knigsberg,Bridge 4,To
5、days Bridges of Knigsberg,Bridge 5,Todays Bridges of Knigsberg,Bridge 6,Birth of Graph theory,The term of graph has been introduced by Sylvester in a paper published in 1878 in Nature. First theoretic book Hnig,D. Theorie der Endliche und Unendliche Graphen, Leipzig, Akademishe Verlagsgesellshaft, 1
6、936 What is graph theory? “Graph theory is the study of mathematical objects (graphs) that are made of dots that may or may not be connected by lines.”,History & application,More than one century after Eulers paper on the bridges of Knigsberg and while Listing introduced topology, Cayley were led by
7、 the study of particular analytical forms arising from differential calculus to study a particular class of graphs, the trees. This study had many implications in theoretical chemistry. The involved techniques mainly concerned the enumeration of graphs having particular properties. Enumerative graph
8、 theory then rose from the results of Cayley and the fundamental results published by Plya between 1935 and 1937 and the generalization of these by De Bruijn in 1959. Cayley linked his results on trees with the contemporary studies of chemical composition. The fusion of the ideas coming from mathema
9、tics with those coming from chemistry is at the origin of a part of the standard terminology of graph theory.,History & application,One of the most famous and productive problem of graph theory is the four color problem: “Is it true than any map drawn in the plane may habe its regions colored with f
10、our colors, in such a way that two regions having a common border get different color?“. This problem remained unsolved for more than one century and the proof given by Kenneth Appel and Wolfgang Haken in 1976 (determination of 1936 types of configurations which study is sufficient and checking of t
11、he properties of these configurations by computer) did not convince all the community. A simpler proof considering far less configurations has been given twenty years later by Robertson, Seymour, Sanders and Thomas. The study and the generalization of this problem by Tait, Heawood, Ramsey and Hadwig
12、er has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. Taits reformulation generated a new class of problems, the factorization problems, particularly studied by Petersen and Knig. The works of Ramsey on colorations and more specially the resu
13、lts otained by Turn in 1941 is at the origin of another branch of graph theory, the extremal graph theory.,Developments in Graph theory,The introduction of probabilistic methods in graph theory, specially in the study of Paul Erds and Alfred Rnyi of the asymptotic probability of graph connectivity i
14、s at the origin of yet another branch, known as random graph theory (1960).,Paul Erds (1913-1996) Oliver Sacks: “A mathematical genius of the first order, Paul Erds was totally obsessed with his subject - he thought and wrote mathematics for nineteen hours a day until the day he died. He traveled co
15、nstantly, living out of a plastic bag, and had no interest in food, sex, companionship, art - all that is usually indispensable to a human life.“ - The Man Who Loved Only Numbers (Paul Hoffman, 1998),Erds Number,Erds Number Erds published 1,600 papers with 500 coauthors in his life time Published 2
16、papers per month from 20 to 83 years old Main contributions in modern mathematics: Ramsey theory, graph theory, Diophantine analysis, additive number theory and prime number theory, ,Erds had a (scale-free) small-world network of mathematical research collaboration Science collaboration network Auth
17、or - node Paper coauthored - link,图论应用前景,We need this theory for our research on communication and networking and A network is a set of nodes interconnected via links Examples: Internet: Nodes routers Links optical fibers WWW: Nodes document files Links hyperlinks Scientific Citation Network: Nodes
18、papers Links citation Social Networks: Nodes individuals Links relations Nodes and Links can be anything depending on the context,Internet: ip-level,www,(K. C. Claffy),Telecomm Networks,(Stephen G. Eick),VLSI Circuits,1. 问题引入与分析,98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的: 今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救,
19、县领导决定,带领有关部门负责人到 全县各乡(镇)、村巡视. 巡视路线指从县政府 所在地出发,走遍各乡(镇)、村,又回到县政 府所在地的路线.,1)若分三组(路)巡视,试设计总路程最,短且各组尽可能均衡的巡视路线.,2)假定巡视人员在各乡(镇)停留时间T=2,小时,在各村停留时间t=1小时,汽车行驶速度V,=35公里/小时. 要在24小时内完成巡视,至少应分,几组;给出这种分组下最佳的巡视路线.,公路边的数字为该路段的公里数.,2) 问题分析:,本题给出了某县的公路网络图,要求的是在不,同的条件下,灾情巡视的最佳分组方案和路线.,将每个乡(镇)或村看作一个图的顶点,各乡,镇、村之间的公路看作此图
20、对应顶点间的边,各条,再回到点O,使得总权(路程或时间)最小.,公路的长度(或行驶时间)看作对应边上的权,所,给公路网就转化为加权网络图,问题就转化图论中,一类称之为旅行售货员问题,即在给定的加权网络,图中寻找从给定点O出发,行遍所有顶点至少一次,如第一问是三个旅行售货员问题,第二问是四,本题是旅行售货员问题的延伸,多旅行售货员问题.,本题所求的分组巡视的最佳路线,也就是m条,众所周知,旅行售货员问题属于NP完全问题,,显然本问题更应属于NP完全问题. 有鉴于此,,经过同一点并覆盖所有其他顶点又使边权之和达到,最小的闭链(闭迹).,个旅行售货员问题.,即求解没有多项式时间算法.,一定要针对问题
21、的实际特点寻找简便方法,想找到,解决此类问题的一般方法是不现实的,对于规模较大,的问题可使用近似算法来求得近似最优解.,问题2(哈密顿环球旅行问题): 十二面体的20个顶点代表世界上20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?,问题3(四色问题): 对任何一张地图进行着色,两个共同边界的国家染不同的颜色,则只需要四种颜色就够了. 问题4(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这
22、些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个?,2.图论的基本概念,1) 图的概念,2) 赋权图与子图,3) 图的矩阵表示,4) 图的顶点度,5) 路和连通,1) 图的概念,定义 一个图G是指一个二元组(V(G),E(G),其中:,其中元素称为图G的顶点.,组成的集合,即称为边集,其中元素称为边.,定义 图G的阶是指图的顶点数|V(G)|, 用,来表示;,2) E(G)是顶点集V(G)中的无序或有序的元素偶对,定义 若一个图的顶点集和边集都是有限集,则称,其为有限图. 只有一个顶
23、点的图称为平凡图,其他的,所有图都称为非平凡图.,定义若图G中的边均为有序偶对,称G为有向,边 为无向边,称e连接 和 ,顶点 和 称,连接,,称 为e的尾,称 为e的头.,若图G中的边均为无序偶对 ,称G为无向图.称,为e的端点.,既有无向边又有有向边的图称为混合图.,常用术语,1) 边和它的两端点称为互相关联.,2)与同一条边关联的两个端点称,为相邻的顶点,与同一个顶点,点关联的两条边称为相邻的边.,3) 端点重合为一点的边称为环,,端点不相同的边称为连杆.,4) 若一对顶点之间有两条以上的边联结,则这些边,称为重边,5) 既没有环也没有重边的图,称为简单图,常用术语,6) 任意两顶点都相
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 建模
链接地址:https://www.31doc.com/p-3290015.html