《国家集训队2007论文集2.古楠《平面嵌入》》由会员分享，可在线阅读，更多相关《国家集训队2007论文集2.古楠《平面嵌入》（16页珍藏版）》请在金锄头文库上搜索。
1、平面嵌入四川绵阳南山中学古楠引子 什么是平面嵌入呢？大家还记得冬令营2005 的蜂窝玉米吗？它涉及到了图的一个性质，那就是所有的边都不能相交。图这个性质叫做图的平面性。当我们需要知道一个图是否具有平面性和这张图实现平面性后的结构时，平面嵌入算法就是一个好的工具。摘要 本文主要由两大部分构成。第一部分主要介绍了平面嵌入的算法，其中包括了具体的操作，复杂度的分析，正确性的证明和一些相关题目。第二部分主要是附录，包含参考文献和伪码。关键字 平面，嵌入，内部活跃，相关，外部活跃，块，根边，回落边目录 一算法 -11平面嵌入的相关定义 -12算法的目的 -23一些相关的知识 -24算法总揽 -25边的嵌
2、入 -36外部活跃，相关与内部活跃 -37反转操作 -58一个全面的分析 -68.1 walkup函数 -78.2 walkdown函数 -89复杂度的分析-910正确性的证明 -1011相关题目 -1212总结 -12二附录 -121 MergeBiconnectedComponent 伪码 -132 walkup 伪码 -133 walkdown伪码 -14算法 1.平面嵌入的相关定义如果对平面嵌入还有些陌生，希望下面的定义对你有所帮助。（ 1）平面作图：一张图能够转化会为一张所有边都不相交的图（在节点上相交不算），转化过程就叫做平面作图。 （原来相连的节点在转化后依然相连，图 1 展示了
3、平面作图）（ 2）平面图：一张图能够进行平面作图它就是平面图，否则为非平面图。（ 3）平面嵌入：和平面作图是等价的，不过在储存方式上是这样的，对于每个节点都顺时针储存和它连接节点。我们将记录用的表叫邻接表。注意：本篇论文所有的平面都是指这里的相关定义，和几何平面是不同的。图 12算法的目的在明白了平面嵌入的一些基本定义以后。对于给定的图G，它有 n 个节点， m 条边。（以后我们将始终用n 表示图 G 的节点个数， m 表示图 G 的节点边数）算法的目的就是用O(n)的时间判断一个图是否为平面图，如果是的话要用O(n) 的时间实现平面嵌入。3一些相关的知识为了实现我们的目的，我们必须先知道一些
4、必要的知识。这些知识将包含深度优先搜索，双连通分量，关节点，计数排序（一个复杂度和关键码范围有关的算法）。还要知道一些必要的定理， 如一个平面图的边将不能超过3n-5 条边，否则它将是一个非平面图。Kuratowiski曾经证明了两个图将阻碍平面嵌入的进行，那就是图2 所描述的图，我们称作k5 图和 k33图。一张图中如果包含了k5 图和 k33 图的同胚图（如果一个图可以通过延展，弯曲，合并连接节点的方式转化为另一张图，这两张图就是同胚的），那么这张图一定是非平面图，反之也成立。我们的算法有一个基本操作，就是加边操作。 我们创建一个图GP，我们要将原图中的边按照一定的顺序加入图GP 中。我们
5、把这个操作称作边的嵌入。为了叙述的通顺性，有关复杂度的分析和正确性的证明我都会放到论文的末尾。图 24算法总览为了后面的叙述更加清晰，这里将叙述算法的总体过程。我们只讨论对双连通分量图的平面嵌入，对于有关节点的图，我们可以将图从关节点处断开分别进行平面嵌入后再合并。首先对图进行一次深度优先遍历，得到一棵深度优先搜索树和图的逆向深度优先搜索序（由于深度优先搜索序简称DFI 序，所以后面写作逆向DFI 序）。我们将每个节点和它儿子相连的边叫做树边，将和它后裔相连的边叫做回落边（注意： 我们指的后裔是不包括儿子的）。然后我们按照逆向的DFI 序依次处理每个节点。所谓处理节点就是：首先将它的树边嵌入图
6、 GP 中，然后将它的的回落边都嵌入到图GP 中，我们并不处理它和它祖先相连的边（祖先是包括父亲的） 。如果嵌入过程失败，那么可以得到图G 是非平面图的结论，否则就完成构造。5边的嵌入我们算法最重要和操作就是对边的嵌入，我将针对图3 进行详细的说明，在图3(a)中，我们要嵌入边 (v,w)。在开始的时候该连通分量包含了一个关节点r，我们将r 去掉后该连通分量就变成了两个部分，就象图3(b)。然后分别给两个分量配上一个r, 这样 r 就被分成了两个，象图 3(c)。然后将边（ v,w）嵌入，然后将两个连通分量合并在一起，这时候，r 已经不再是关节点了，象图3(d)。这样我们就完成了一个最基本的嵌
7、入操作。为什么要这么麻烦呢？大家注意到图3(d)了吗？它的下半部分左右颠倒了，这也是嵌入时候的一个操作，叫做反转操作，这个操作是为了保证图GP 的一个重要性质，这些都将在下文中提到。图 3在我们的嵌入过程中，只要图 GP 中含有关节点， 我们都将从这个关节点把它所在的连通分量断为两个部分。在嵌入回落边的时候又会将他们组合在一起。这样，图 GP 就是由很多的双连通分量组成的， 请大家注意， 在代码的实现中我们必须实际的这样处理， 并不是为了理解。6.外部活跃，相关与内部活跃反转操作所要保护的性质就是：在嵌入边的过程中所有的外部活跃节点都必须留在外部面上。 什么是外部面呢？外部面的名称很形象，也就
8、是图中接触到最外层空间的点和边构成的面， 并且外部面都会是完整的环， 如果一个双连通分量只有一条边， 那么我们就要进行相应的转化，像图 4 这样。图 4外部活跃节点的定义就要复杂些，为了清楚的叙述，我们要加入些新的定义。我们将双连通分量中DFI 序最小的节点称作该双连通分量的根节点。由于我们在只有嵌入树边的时候才会产生分离操作，所以我们会发现当一个关节点被分离成多个后，和儿子分到一个分量中的节点一定会成为该分量的根节点。我们把这些节点称作复制点，把唯一的不是根的点称作原节点。 假设 r是一个双连通分量 B的根节点， 那么 r 在该双连通分量中一定只有一个儿子，若 r有两个儿子 c1,c2，由于
9、是深度优先遍历，在访问到 c1后，继续访问的过程中将通过双连通分量 B的某一条路径不经过 r 到达 c2,那么 c2将不会成为 r 的儿子，也就与假设矛盾。我们设定 r 的这个唯一儿子为 c，那么我们将 r 到c 的边称做根边（由于我们只有在加入树边的时候才会导致双连通分量的拆分，所以根边一定是树边），将该根节点称作节点（儿子还没有确定的我们写作r），将该双连通分量称做块。这样就可以和原r 节点区分开并且双连通分量也可以明确表示（后来的叙述都将遵从这里的设定）。子块的定义在这里就产生了，我们将块称做原节点 r 的子块。知道了这些后，只要满足下面两个条件的任何一个，它就是外部活跃节点：(1) 当
10、我们在处理节点v 的时候，该节点处理过，并且有直接连接v 的祖先的边。(2) 当我们在处理节点 v 的时候，该节点处理过，并且该节点的子块中存在外部活跃节点。就象图 5 中，方形的点都是外部活跃节点。那么我们怎么得到外部活跃节点的信息呢？我们把每个节点本身能够直接到达的最早祖先的深度记做该节点的ecpoint ，把能够直接或者间接到达的最早祖先的深度叫做该接点的lowpoint( 所 谓 间 接 就 是 通 过 它 的 子 孙 到 达 ) 。 同 时 ， 我 们 给 每 个 节 点 配 备 一 个图 5图 5：z 有直接连接 v 的祖先 u 的边所以， v 是外部活跃节点 ,，z 在 d 的子
11、块中，所以 d 也是外部活跃节点， d 在 x 的子块中，所以 x 也是外部活跃节点。SDlist ，它是一个双向链表， 其中记录了它的每个儿子的lowpoint 。并且，SDlist 中的 lowpoint值是按照从小到大排序的，为了满足这个条件，我们需要一次排序。因为我们的lowpoint值和深度有关，所以深度大小不会超过n。在求出所有节点的lowpoint 后，就可以用计数排序将它们按照从小到大排序，再依次加入它们父亲的 SDlist 中。那么如何快速的得到lowpoint呢？在深度优先搜索的时候，可以顺便得到它的 ecpoint ，在深搜返回的时候再将它的ecpoint和它的儿子中最小的lowpoint 值做比较中，返回较小的
