《图与网络分析》ppt课件

《《图与网络分析》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章图与网络分析Graphtheoryandnetworkanalysis第十一章图与网络分析11.1引言引言图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段。引言第一阶段从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题由游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。引言第二阶段从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际

2、问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.引言第三阶段二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。ABCD哥尼斯堡七桥问题哥尼斯堡七桥问题最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础Euler把A、B、C、D四块陆地分别收缩成四个顶点，

3、把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。ABCD哥尼斯堡七桥问题哥尼斯堡七桥问题ACBD围坐问题有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。1237645围坐问题假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。围坐问题

4、1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题假定第三次就座方案是（1，4，

5、7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题1237645围坐问题假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方

6、案。围坐问题哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路引言瑞士数学家Euler在1736年发表的一篇题为“依据几何位置的解题方法”的论文，有

7、效的解决了哥尼斯堡七桥问题，是有记载的第一篇图论论文，Euler被认为是图论的创始人。图论的第一本专著是匈牙利的OKonig写的“有限图与无限图的理论”，发表于1936。从1736到1936，前后200年，总的来讲这一时期图论发展缓慢。直到20世纪中叶，电子计算机的发展和零散数学问题具有越来越重要的地位，使得图论得以迅速发展第十一章图与网络分析11.1引言11.2图与网络的基本概念§11.2图与网络的基本概念图论是专门研究图的理论的一门数学分支，主要研究点和线之间的几何关系§11.2图与网络的基本概念定义：图是

8、由点集V=（vi）和V中元素的无序对的一个集合E=（ek）所构成的二元组，记为G=（V，E），其中：V=（v1，v2，…...vm）是m个顶点集合；E=（e1，e2，…...en）是n条边集合。当V，E为有限集合时，G称为有限图，否则称为无限图，本章只讨论有限图。§11.2图与网络的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2§11.2图与网络的基本概念V=（v1，