第七章第六节图论

发布时间:2016-11-28 10:24:10 流览量:377 发布者:admin

  图论是数学的一个分支,它以因为研究对象.图论中的图是若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物问具有这种关系.因此,在这种图中,点的位置、线的长短曲直是无关紧要的.

    图论起源于著名的柯尼斯堡七桥问题.在柯尼斯堡(前苏联加里宁格勒)的普莱格尔河上有七座桥,将河中的两个岛和河岸连接(图4).   

    要寻找一条路线,经过所有的桥而每座桥只经过一次,最后返回到出发点.当然,这个问题无法找到答案.1736年,L.欧拉用点表示陆地,用连接两个点的线来表示桥,以图5代替图4,提出了第一个图论问题:对给定的图,是否存在一条路线,使得通过每条线正好一次而能回到起点.他证明了:当且仅当,图是连通的并且每个点都与偶数条线相关联时,才存在上述路线(这路线称作欧拉圈).图5虽然是连通的,但是每个点都与奇数条线相关联,所以并不存在欧拉圈.

    1847年,G.R.基尔霍夫在建立电网络理论时,以图G(图6)代替电网络N(图7),提出了"连通图"、"树"、"支撑树"等基本概念.

    1857年,A.凯莱在研究饱和碳氢化合物(CnH2n+2)同分异构体的数目时,独立地提出了"树"的概念.他把这一类化合物的计数问题抽象为计算某类树的个数问题.这一问题是图的计数理论的起源.

    1859年,W.R.哈密顿提出了一种叫做"旅行世界"的游戏.把一个正十二面体的20个顶点看作20个城市(图8).要寻找一条沿着多面体的边走的旅行路线,经过每个顶点正好一次,最后回到出发点.例如,l→2→3→……  

→20→1就是一种走法.将这个问题推广到一般图上,即:对给定的图是否存在一条路线,使得通过每个点正好一次,最后回到起点(即哈密顿圈),这就是哈密顿问题.哈密顿问题在许多学科(如运筹学、计算机科学以及编码理论)中都有着广泛的应用.

    1936年,D.柯尼希写出了第一本图论的书.经过几十年的广泛应用,促进了图论自身的发展.例如,W.T.塔特等发展了由H.惠特尼首先提出的拟阵理论,C.伯奇等发展了超图理论,P.爱尔特希发展了极图理论.另外,代数图论,拓扑图论等方面也有了很大的进展.