图论

来自计算思维百科
跳转至: 导航搜索

图论(Graph Theory)是研究边和点的连接结构的数学理论。

图的基本概念

一个图G是一个三元组<V,E,ψ>,其中V是一个非空有限集,称为G的顶点集合,E是有限集,称为G的边集合,ψ是从边集E到顶点偶对集合的函数。图G的顶点数目称为它的阶。

发展与应用

图论起源于1736年瑞士数学家欧拉(L.Euler,1707-1783)发表的解决“哥尼斯堡七桥问题”的第一篇图论论文。经过许多研究人员的努力,图论学科才逐步发展起来。特别是1852年格斯里(Gathrie)提出“四色问题”和1859年哈密顿(Hamilton)提出的“哈密顿回路问题”,它们不仅成为图论中最重要的两个问题,而且导致了许多新成果的诞生。

1874年,德国物理学家基尔霍夫(G.R.Kirchhoff,1824~1887)第一次把图论用于电路网络的拓扑分析,开创了图论面向实际应用的成功先例。1936年,科尼格(Konig)出版了第一本“图论”书籍。目前图论已成为解决许多实际问题的基本工具之一,受到工程界和数学界的重视。

图论是一门应用性很强的学科,应用图论可以解决运筹学、物理学、化学、生物学、网络理论、信息论、控制论、博弈论和计算机科学等问题。图论在计算机科学的许多领域,如开关理论与逻辑设计、数据结构、形式语言、操作系统以及计算机网络等都起着重要的作用。

典型问题

树与平面图

树(Tree)是图论的一个重要概念,是结构最简单、用途最广泛的数学模型。特别是二叉树,它在计算机科学中用得最多。因此,要很好地掌握诸如树的充要条件、生成树、最优生成树、根树、树的各种算法及二叉树的访问次序等内容。

平面图(Planar Graph)是一类有实际应用背景的数学模型。比如,有3家工厂和3座矿山,要从每家工厂到每座矿山修一条专用铁路,问能否在同一平面上修建这些铁路,并使这些铁路互不交叉。这个问题在图论中的反映就是在一个平面内,一个图具备什么条件,它的边才能互不相交。

图论中的这个问题是很多实际问题的模型。比如,在集成电路的布线设计中就遇到了这个问题。这类问题在图论中就归结为平面图的研究,那么,什么是平面图呢?

设G=(V,E)是无向图,如果能把G画在一个平面内,使得图的各边除在端点外彼此都不相交,则称G为平面图。

一个图看上去有相交的边,但我们并不能马上说它就不是平面图,可以适当地改画这个图的边,使它们彼此不相交,如图3(a)可以画成(b),因此,图3(a)是平面图。但是,有些图无论怎样改画都有相交的边,这类图才是真正的非平面图。

8.4.3.png


图3 平面图