资源描述：
《国家集训队2007论文集2.古楠《平面嵌入》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、平面嵌入四川省绵阳南山中学古楠应用算法在实际中的重要应用是电路板设计.２４５３１平面嵌入的目的不过是让所有的边都不相交!目的２3４５１相关定义:平面嵌入:在平面内将一张图转化为所有边都不相交(除开段点处相交)的图的过程.平面图:能够进行平面嵌入的图.对于一张n个节点的图算法的目的：算法可以用O(n)的时间判断一张图是不是平面图并且实现平面嵌入,但由于时间的关系,我这里只介绍O(n2)的算法.定义深度优先遍历首先对图进行一次深度优先遍历.然后每个点将拥有属于它的边.将这些边做这样的定义:树边:在深度优先搜索树中,节点与它儿子相连的边.回
2、落边:节点与它非儿子后裔相连的边.平面图的边不会超过3n-5条.[定理]简略流程建立一张空图GP,然后进行深度优先遍历,完成后按照逆向深度优先搜索序处理所有节点:把节点的树边加入图GP中.向下遍历,同时将节点的回落边加入到图GP中—walkdown.v2加入树边当处理节点v的时候,会首先加入节点v的树边,不过在加入树边的时候得做一个分离操作:v1c1c2v将v1和v2称做它们所在的连通分量的根.将v1和v2所在的分量称作v的子块.Walkdown—向下遍历(1)向下遍历—回落边的加入过程在处理节点v的时候,会进入它的每个子块进行顺时针
3、和逆时针两次遍历,当回到连通分量的根节点或者遭遇终止节点时就会停止遍历.终止节点:是外部活跃节点但不是相关节点的节点.外部活跃与相关设当前处理节点为v,对于原有节点,定义如下:外部活跃节点:与v的祖先有连接的节点子块中有外部活跃节点的节点相关节点:与v有连接的节点子块中有相关节点的节点外部活跃与相关uvv’sws’w’ke在这张图中,当前处理节点为v,k,s为外部活跃节点,e,w为相关节点.Walkdown—向下遍历(2)由于终止节点的存在,随机的遍历会很快遭遇终止节点而终止遍历,这将导致需要加入的边没有加入到图GP中.所以在遍历的时
4、候有一个原则.尽量晚的终止遍历.有两个法则来约束遍历,从而维护这个原则.Walkdown—向下遍历(2)法则1:当节点有多个子块需要遍历的时候,总是先进入没有外部活跃节点的子块进行遍历.法则2:每次进入子块进行遍历都优先选择是走向只具有相关性节点方向,否则选择走向具有相关性的节点的方向.Walkdown—向下遍历(2)节点是相关节点,那么加入回落边.在满足两个法则的情况下,向下遍历时,会依次处理下面几种情况:遇到终止节点或者块的根时,终止遍历.节点有包含相关节点的子块,到它子块中继续遍历.节点不是外部活跃节点,走向下一节点.当加入回落
5、边的以后,会将该边所连接的两个块和它们之间的块全部合并.它和分离是对应的.节点所在块与子块合并后也不再拥有该子块.分离是在加入树边的时候.Walkdown—向下遍历(2)合并是在加入回落边以后.翻转操作为了将所有的回落边都顺利的加入图GP中,图GP必须始终满足一个性质.这个性质就是:外部活跃节点都必须留在外部面上.翻转操作我们把接触最外层空间的面,叫做外部面.(图中黄线标出的面)翻转操作为了将所有的回落边都顺利的加入图GP中,图GP必须始终满足一个性质.这个性质就是:外部活跃节点都必须留在外部面上.加入回落边的时候会覆盖向下遍历时经过
6、的面,这可能导致外部活跃节点被覆盖,为了保证图GP的性质.定义一个翻转操作.翻转操作uvwev’wewewewewewewewewewewewewewewewewewewewewewewewewewewes1Walkdown—向下遍历(3)uvwkv’wks2ees信息取得算法需要有快速取得外部活跃信息和相关信息的方法.对于外部活跃信息可以通过预处理和以后的维护来快速取得.对于相关节点,可以在向下遍历时查找取得.O(n)的算法有另一种取得方式(请参考论文).接下来我们具体介绍外部活跃信息的取得.外部活跃信息的取得快速的取得外部活跃信息
7、外部活跃信息.给每个节点配备一个lowpoint,表示它能直接或者间接到达的最早祖先,间接是指通过它的子孙到达.可以通过开始的深度优先搜索取得所有节点的lowpoint.外部活跃信息的取得给每个节点配备一个SDlist,其中记录它的所有儿子,并且是按照他们的lowpoint从小到大排序的.维护SDlist:在节点所在块与其子块合并后,将该儿子在该节点的SDlist中的值删除.外部活跃信息的取得快速的得到外部活跃信息:节点连接的最早祖先或者SDlist中的第一个值小于v,该节点就是外部活跃节点.虚边在上面的图中,s到w部分以后都是不会用
8、到的.加入边(v’,w)覆盖它.v’sw总览总体流程:取得相关信息.按照反向深度优先搜索序依次处理每个节点.将节点所有的树边加入图GP中.进入v的每个子块向下遍历.分离操作合并操作翻转操作总结复杂的问题总是能够简化的.只
