树与平面图

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

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

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

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

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

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

8.4.3.png


图3 平面图