平面嵌入

《平面嵌入》由会员分享，可在线阅读，更多相关《平面嵌入（31页珍藏版）》请在金锄头文库上搜索。

1、平面嵌入平面嵌入 应用应用算法在实际中的算法在实际中的重要重要应用是电路板设计应用是电路板设计. .平面嵌入的目的不过是让所有的边都不相交平面嵌入的目的不过是让所有的边都不相交! !目的目的3相关定义相关定义: :n n平面嵌入平面嵌入: : 在平面内将一张图转化为所有边都不相在平面内将一张图转化为所有边都不相 交交( (除开段点处相交除开段点处相交) )的图的过程的图的过程. .n n平面图平面图: : 能够进行平面嵌入的图能够进行平面嵌入的图. .对于一张对于一张n n个节点的图算法的目的：个节点的图算法的目的：n n算法可以用算法可以用O(n)O(n)的时间判断一张图是不是平面图并的时间

2、判断一张图是不是平面图并 且实现平面嵌入且实现平面嵌入, ,但由于时间的关系但由于时间的关系, ,我这里只介绍我这里只介绍 O(nO(n2 2) )的算法的算法. .定义定义深度优先遍历深度优先遍历首先对图进行一次深度优先遍历首先对图进行一次深度优先遍历. . 然后每个点将拥有属然后每个点将拥有属 于它的边于它的边. .将这些边做这样的定义将这些边做这样的定义: :n n树边树边: :在深度优先搜索树中在深度优先搜索树中, ,节点与它儿子相连的节点与它儿子相连的 边边. .n n回落边回落边: :节点与它非儿子后裔相连的边节点与它非儿子后裔相连的边. .平面图的边不会超过平面图的边不会超过3n

3、-53n-5条条. . 定理定理 简略流程简略流程建立一张空图建立一张空图GP,GP,然后进行深度优先遍历然后进行深度优先遍历, ,完成后按照逆完成后按照逆 向深度优先搜索序处理所有节点向深度优先搜索序处理所有节点: :n n把节点的树边加入图把节点的树边加入图GPGP中中. .n n向下遍历向下遍历, , 同时将节点的回落边加入到图同时将节点的回落边加入到图GPGP 中中 walkdown.walkdown.v2加入树边加入树边当处理节点当处理节点v v的时候的时候, ,会首先加入节点会首先加入节点v v的树边的树边, ,不过不过 在加入树边的时候在加入树边的时候得做一个分离操作得做一个分离

4、操作: :v1c1c2vn n将将v1v1和和v2v2称做它们所在的连通分量的根称做它们所在的连通分量的根. .n n将将v1v1和和v2v2所在的分量称作所在的分量称作v v的子块的子块. .Walkdown Walkdown 向下遍历向下遍历(1)(1)向下遍历向下遍历 回落边的加入过程回落边的加入过程在处理节点在处理节点v v的时候的时候, ,会进入它的每个子块进行顺会进入它的每个子块进行顺 时针和逆时针两次遍历时针和逆时针两次遍历, ,当回到连通分量的根节点当回到连通分量的根节点 或者遭遇终止节点时就会停止遍历或者遭遇终止节点时就会停止遍历. .n n终止节点终止节点: :是外部活跃节

5、点但不是相关节点的节是外部活跃节点但不是相关节点的节 点点. .外部活跃与相关外部活跃与相关设当前处理节点为设当前处理节点为v, v, 对于原有节点对于原有节点, ,定义如下定义如下: :n n外部活跃节点外部活跃节点: :l l与与v v的祖先有连接的节点的祖先有连接的节点l l子块中有外部活跃节点的节点子块中有外部活跃节点的节点n n相关节点相关节点: :l l与与v v有连接的节点有连接的节点l l子块中有相关节点的节点子块中有相关节点的节点外部活跃与相关外部活跃与相关uvvsw swke在这张图中在这张图中, ,当前处理节点为当前处理节点为v,k,sv,k,s为外部活跃节点为外部活跃节

6、点, , e,we,w为相关节点为相关节点. .Walkdown Walkdown 向下遍历向下遍历(2)(2)由于终止节点的存在由于终止节点的存在, ,随机的遍历会很快遭遇终止节点随机的遍历会很快遭遇终止节点 而终止遍历而终止遍历, ,这将导致需要加入的边没有加入到图这将导致需要加入的边没有加入到图GPGP 中中. .所以在遍历的时候有一个原则所以在遍历的时候有一个原则. .n n尽量晚的终止遍历尽量晚的终止遍历. .有两个法则来约束遍历有两个法则来约束遍历, ,从而维护这个原则从而维护这个原则. .Walkdown Walkdown 向下遍历向下遍历(2)(2)法则法则1:1:n n当节点

7、有多个子块需要遍历的时候当节点有多个子块需要遍历的时候, ,总是先进入没总是先进入没 有外部活跃节点的子块进行遍历有外部活跃节点的子块进行遍历. .法则法则2:2:n n每次进入子块进行遍历都优先选择是走向只具有每次进入子块进行遍历都优先选择是走向只具有 相关性节点方向相关性节点方向, ,否则选择走向具有相关性的节点否则选择走向具有相关性的节点 的方向的方向. .Walkdown Walkdown 向下遍历向下遍历(2)(2)n n节点是相关节点节点是相关节点, ,那么加入回落边那么加入回落边. .在满足两个法则的情况下在满足两个法则的情况下, ,向下遍历时向下遍历时, ,会依次处理下面几会依

8、次处理下面几 种情况种情况: :n n遇到终止节点或者块的根时遇到终止节点或者块的根时, ,终止遍历终止遍历. .n n节点有包含相关节点的子块节点有包含相关节点的子块, ,到它子块中继到它子块中继 续遍历续遍历. .n n节点不是外部活跃节点节点不是外部活跃节点, ,走向下一节点走向下一节点. .当加入回落边的以后当加入回落边的以后, ,会将该边所连接的两个块和它们之会将该边所连接的两个块和它们之 间的块全部合并间的块全部合并. .它和分离是对应的它和分离是对应的. .节点所在块与子块节点所在块与子块 合并后也不再拥有该子块合并后也不再拥有该子块. .n n分离是在加入树边的时候分离是在加入

9、树边的时候. .Walkdown Walkdown 向下遍历向下遍历(2)(2)n n合并是在加入回落边以后合并是在加入回落边以后. .翻转操作翻转操作为了将所有的回落边都顺利的加入图为了将所有的回落边都顺利的加入图GP GP 中中, ,图图GP GP 必须始必须始 终满足一个性质终满足一个性质. . 这个性质就是这个性质就是: :n n外部活跃节点都必须留在外部面上外部活跃节点都必须留在外部面上. .翻转操作翻转操作我们把接触最外层空间的面我们把接触最外层空间的面, ,叫做外部面叫做外部面.(.(图中黄线标出图中黄线标出 的面的面) )翻转操作翻转操作为了将所有的回落边都顺利的加入图为了将所

10、有的回落边都顺利的加入图GP GP 中中, ,图图GP GP 必须始必须始 终满足一个性质终满足一个性质. . 这个性质就是这个性质就是: :n n外部活跃节点都必须留在外部面上外部活跃节点都必须留在外部面上. .加入回落边的时候会覆盖向下遍历时经过的面加入回落边的时候会覆盖向下遍历时经过的面, ,这可能这可能 导致外部活跃节点被覆盖导致外部活跃节点被覆盖, ,为了保证图为了保证图GPGP的性质的性质. .定义定义 一个翻转操作一个翻转操作. .翻转操作翻转操作uvwevwewewewewewewewewewewewewewewewewewewewewewewewewewewes1Walkdo

11、wn Walkdown 向下遍历向下遍历(3)(3)uvwkvwks2ees信息取得信息取得算法需要有快速取得外部活跃信息和相关信息的方法算法需要有快速取得外部活跃信息和相关信息的方法. .n n对于外部活跃信息可以通过预处理和以后的维护来对于外部活跃信息可以通过预处理和以后的维护来 快速取得快速取得. .n n对于相关节点对于相关节点, ,可以在向下遍历时查找取得可以在向下遍历时查找取得.O(n).O(n)的的 算法有另一种取得方式算法有另一种取得方式( (请参考论文请参考论文).).接下来我们具体介绍外部活跃信息的取得接下来我们具体介绍外部活跃信息的取得. .外部活跃信息的取得外部活跃信息

12、的取得快速的取得外部活跃信息外部活跃信息快速的取得外部活跃信息外部活跃信息. .n n给每个节点配备一个给每个节点配备一个lowpoint,lowpoint,表示它能直接或者间接表示它能直接或者间接 到达的最早祖先到达的最早祖先, ,间接是指通过它的子孙到达间接是指通过它的子孙到达. .n n可以通过开始的深度优先搜索取得所有节点的可以通过开始的深度优先搜索取得所有节点的 lowpoint.lowpoint.外部活跃信息的取得外部活跃信息的取得给每个节点配备一个给每个节点配备一个SDlist,SDlist,其中记录它的所有儿子其中记录它的所有儿子, , 并且是按照他们的并且是按照他们的lowp

13、ointlowpoint从小到大排序的从小到大排序的. .维护维护SDlist:SDlist:n n在节点所在块与其子块合并后在节点所在块与其子块合并后, ,将该儿子在该节点将该儿子在该节点 的的SDlistSDlist中的值删除中的值删除. .外部活跃信息的取得外部活跃信息的取得快速的得到外部活跃信息快速的得到外部活跃信息: :n n节点连接的最早祖先或者节点连接的最早祖先或者SDlistSDlist中的第一个值小中的第一个值小 于于v,v,该节点就是外部活跃节点该节点就是外部活跃节点. .虚边虚边在上面的图中在上面的图中,s,s到到w w部分以后都是不会用到的部分以后都是不会用到的. .加

14、入边加入边 (v,w)(v,w)覆盖它覆盖它. .vsw总览总览总体流程总体流程: :n n取得相关信息取得相关信息. .按照反向深度优先搜索序依次处理每个节按照反向深度优先搜索序依次处理每个节 点点. . n n将节点所有的树边加入图将节点所有的树边加入图GPGP中中. .n n进入进入v v的每个子块向下遍历的每个子块向下遍历. .l l分离操作分离操作l l合并操作合并操作l l翻转操作翻转操作总结总结复杂的问题总是能够简化的复杂的问题总是能够简化的. .只要我们不畏困难只要我们不畏困难, ,勇敢勇敢 攀登攀登, ,它们一定都能解决它们一定都能解决. .我们也不可能学完所有的算法我们也不

15、可能学完所有的算法, ,但是只有不断的汲取但是只有不断的汲取, ,才才 能提高和完善自己能提高和完善自己. .谢谢谢谢! !快速翻转快速翻转当进入子块进行遍历会从新选择方向当进入子块进行遍历会从新选择方向, ,当选择方向与原当选择方向与原 有方向不同时有方向不同时, ,就需要进行翻转操作就需要进行翻转操作. .对外部面对外部面O(1)O(1)的翻转的翻转: :n n只需要交换块根节点的两个方向的指示只需要交换块根节点的两个方向的指示. .在以后的遍历中在以后的遍历中, ,只需要知道由哪一个节点到达只需要知道由哪一个节点到达, ,并并 且走向下一节点且走向下一节点. .快速翻转快速翻转对邻接表的

16、翻转对邻接表的翻转: :n n对于节点的子块对于节点的子块, ,如果翻转如果翻转, ,将该节点与子块中将该节点与子块中 唯一的儿子相连的树边标记为唯一的儿子相连的树边标记为-1.-1.最后对图只经过树边进行一次深搜最后对图只经过树边进行一次深搜, ,当到达节点经过当到达节点经过 了奇数个了奇数个-1,-1,就将节点的邻接表前后颠倒就将节点的邻接表前后颠倒. .相关信息的取得相关信息的取得walkup walkup 向上遍历向上遍历: :存在回落边存在回落边(v,w),(v,w),从从w w开始沿着外部面向上遍历到开始沿着外部面向上遍历到 v.v.并且给每个节点配备一个并且给每个节点配备一个proots,proots,表示它有哪些表示它有哪些 块包含相关节点块包含相关节点. .n n从外部面的两个方向同时遍历从外部面的两个方向同时遍历. .n n遇到遍历过的点就停止遍历遇到遍历过的点就停止遍历. .n n在从节点的子块上升到该节点时在从节点的子块上升到该节点时, ,将该子块