《论文_算法合集之《平面嵌入》研究(定稿)》

《《论文_算法合集之《平面嵌入》研究(定稿)》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、关定义12.算法的目的23.一些相关的知识24・算法总揽25.边的嵌入36.外部活跃，相关与内部活跃37.反转操作58.一个全面的分析68.1walkup函数78.2walkdown函数89.复杂度的分析911・相关题目-101210・正确性的证明12•总结二附录121.MergeBiconnectedComponent伪码132.walkup伪码133.walkdown伪码141・平面嵌入的相关定义如果对平面嵌入还有些陌生，希望下血的定义对你有所帮助。（1）平血作图：一张图能够转化会为一张所有边都不相交的图（在节点上相交不算）

3、,转化过程就叫做平面作图。（原来相连的节点在转化后依然相连，图1展示了平血作图）（2）平面图：一张图能够进行平面作图它就是平面图，否则为非平面图。（3）平而嵌入：和平而作图是等价的，不过在储存方式上是这样的，对于每个节点都顺时针储存和它连接节点。我们将记录川的表叫邻接表。注意:本篇论文所有的平面都是指这里的相关定义，和几何平面是不同的。以:n)3・一些相关的知识为了实现我们的目的，我们必须先知道一些必要的知识。这些知识将包含深度优先搜索,双连通分量，关节点，计数排序（一个复朵度和关键码范围有关的算法）。还要知道一些必要的定理，如

4、一个平血图的边将不能超过3n-5条边，否则它将是一个非平血图。Kuratowiski曾经证明了两个图将阻碍平而嵌入的进行，那就是图2所描述的图，我们称作k5图和k33图。一张图中如果包含了k5图和k33图的同胚图（如果一个图可以通过延展，弯曲，合并连接节点的方式转化为另一张图，这两张图就是同胚的），那么这张图-•定是非平而图，反之也成立。我们的算法有一个基本操作，就是加边操作。我们创建一个图GP,我们要将原图中的边按照一定的顺序加入图GP中。我们把这个操作称作边的嵌入。为了叙述的通顺性，有关复杂度的分析和止确性的证明我都会放到论

5、文的末尾。4.算法总览为了后血K5图K33图:图从关节点我们只讨处断开分别进TIWIIX八丿口円•百力-。首先对图进行一次深度优先遍历，得到一棵深度优先捜索树和图的逆向深度优先搜索序(由于深度优先搜索序简称DFI序，所以后面写作逆向DFI序)。我们将每个节点和它儿子相连的边叫做树边，将和它后裔相连的边叫做回落边(注意:我们指的后裔是不包括儿子的。然后我们按照逆向的DF1序依次处理每个节点。所谓处理节点就是：首先将它的树边嵌入图GP屮，然后将它的的回落边都恢入到图GP中，我们并不处理它和它祖先相连的边(祖先是包括父亲的)。如果倏入

6、过程失败，那么可以得到图G是非平面图的结论，否则就完成构造。5.边的嵌入我们算法最重要和操作就是对边的嵌入，我将针对图3进行详细的说明，在图3(a)中，我们要嵌入边(v,w)o在开始的时候该连通分屋包含了一个关节点「我们将I•去掉后该连通分量就变成了两个部分，就象图3(b)。然后分别给两个分量配上一个r,这样I•就被分成了两个,象图3(c)。然后将边(v,w)嵌入，然后将两个连通分量合并在一起，这时候，I■己经不再是关节点了，彖图3(d)o这样我们就完成了一个最基本的像入操作。为什么要这么麻烦呢？大家注意到图3(d)了吗？它的下

7、半部分左右颠倒了，这也是恢入吋候的一个操作，叫做反转操作，这个操作是为了保证图GP的一个重要性质，这些都将在下文中提到。VVVV在我们的恢入过程中，只要图Gpq-含有关节点，我们都将从这个关节点把它所在的连通分量断为两个部分。在嵌入回落边的时候又会将他们组合在一起。这样，图GP就是由很多的双连通分量组成的，请大家注意，在代码的实现中我们必须实际的这样处理，并不是为了理解。6•外部活跃，相关与内部活跃反转操作所要保护的性质就是：在嵌入边的过程屮所有的外部活跃节点都必须留在外部面上。什么是外部血呢?外部面的名称很形彖，也就是图中接触

8、到最外层空间的点和边构成的血，并且外部血都会是完整的坏，如果一个双连通分量只有一条边，那么我们就要进行相应的转化，像图4这样。外部活跃3我们将双卫茨入树边的时候才会产牛分离操作，所以我们会发现当一个关节点被分离成多个后，和儿子分到一个分量中的节点一定会成为该分量