算法合集之《平面嵌入》

《算法合集之《平面嵌入》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、142007年冬令营信息学讲座平面嵌入四川古楠平面嵌入四川绵阳南山中学古楠[引子]什么是平面嵌入呢？大家还记得冬令营2005的蜂窝玉米吗？它涉及到了图的一个性质，那就是所有的边都不能相交。图这个性质叫做图的平面性。当我们需要知道一个图是否具有平面性和这张图实现平面性后的结构时，平面嵌入算法就是一个好的工具。[摘要]本文主要由两大部分构成。第一部分主要介绍了平面嵌入的算法，其中包括了具体的操作，复杂度的分析，正确性的证明和一些相关题目。第二部分主要是附录，包含参考文献和伪码。[关键字]平面，嵌入，内部活跃，相关，外部活跃，块，根边，回落边[目

2、录]一．算法--------------------------------------------------11．平面嵌入的相关定义----------------------------------12．算法的目的------------------------------------------23．一些相关的知识--------------------------------------24．算法总揽--------------------------------------------25．边的嵌入---------------

3、-----------------------------36．外部活跃，相关与内部活跃----------------------------37．反转操作--------------------------------------------58．一个全面的分析--------------------------------------68.1walkup函数-------------------------------------78.2walkdown函数-----------------------------------89．复

4、杂度的分析----------------------------------------910．正确性的证明---------------------------------------1011．相关题目-------------------------------------------1212．总结-----------------------------------------------12二．附录--------------------------------------------------121．MergeBiconnec

5、tedComponent伪码----------------------132．walkup伪码------------------------------------------133．walkdown伪码----------------------------------------14[算法]1.平面嵌入的相关定义如果对平面嵌入还有些陌生，希望下面的定义对你有所帮助。（1）平面作图：一张图能够转化会为一张所有边都不相交的图（在节点上相交不算），转化过程就叫做平面作图。（原来相连的节点在转化后依然相连，图1展示了平面作图）（2）平面图：

6、一张图能够进行平面作图它就是平面图，否则为非平面图。14142007年冬令营信息学讲座平面嵌入四川古楠（3）平面嵌入：和平面作图是等价的，不过在储存方式上是这样的，对于每个节点都顺时针储存和它连接节点。我们将记录用的表叫邻接表。注意：本篇论文所有的平面都是指这里的相关定义，和几何平面是不同的。图12．算法的目的在明白了平面嵌入的一些基本定义以后。对于给定的图G，它有n个节点，m条边。（以后我们将始终用n表示图G的节点个数，m表示图G的节点边数）算法的目的就是用O(n)的时间判断一个图是否为平面图，如果是的话要用O(n)的时间实现平面嵌入。3

7、．一些相关的知识为了实现我们的目的，我们必须先知道一些必要的知识。这些知识将包含深度优先搜索，双连通分量，关节点，计数排序（一个复杂度和关键码范围有关的算法）。还要知道一些必要的定理，如一个平面图的边将不能超过3n-5条边，否则它将是一个非平面图。Kuratowiski曾经证明了两个图将阻碍平面嵌入的进行，那就是图2所描述的图，我们称作k5图和k33图。一张图中如果包含了k5图和k33图的同胚图（如果一个图可以通过延展，弯曲，合并连接节点的方式转化为另一张图，这两张图就是同胚的），那么这张图一定是非平面图，反之也成立。我们的算法有一个基本操

8、作，就是加边操作。我们创建一个图GP，我们要将原图中的边按照一定的顺序加入图GP中。我们把这个操作称作边的嵌入。为了叙述的通顺性，有关复杂度的分析和正确性的证明我都会放到论文的末