图与网络.ppt

图与网络引言图论是专门研究图的理论的一门数学分支,属于离散数学范畴,与运筹学有交叉,它有200多年历史,大体可划分为三个阶段:第一阶段是从十八世纪中叶到十九世纪中叶,处于萌芽阶段,多数问题因游戏而产生,最有代表性的工作是所谓的Euler七桥问题,即一笔画问题。第二阶段是从十九世纪中叶到二十世纪中叶,这时,图论问题大量出现,如Hamilton问题,地图染色的四色问题以及可平面性问题等,这时,也出现用图解决实际问题,如把树应用于化学领域,,由生产管理、军事、交通、运输、计算机网络等方面提出实际问题,以及大型计算机使大规模问题的求解成为可能,特别是以Ford等人建立的网络流理论,与线性规划、动态规划等优化理论和方法相互渗透,促进了图论对实际问题的应用。例1:哥尼斯堡七桥问题哥尼斯堡(现名加里宁格勒)是欧洲一个城市,一条河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题:有没有办法从某处(如A)出发,经过各桥一次且仅一次最后回到原地呢?ABCD数学家Euler在1736年巧妙地给出了这个问题的答案,并因此奠定了图论的基础,Euler把A、B、C、D四块陆地分别收缩成四个顶点,把桥表示成连接对应顶点之间的边,问题转化为从任意一点出发,能不能经过各边一次且仅一次,最后返回该点。这就是著名的Euler问题。ACBD例2:有7个人围桌而坐,如果要求每次相邻的人都与以前完全不同,试问不同的就座方案共有多少种?用顶点表示人,用边表示两者相邻,因为最初任何两个人都允许相邻,所以任何两点都可以有边相连。1237645