算法合集之平面嵌入第1页，共31页，星期日，2025年，2月5日应用算法在实际中的重要应用是电路板设计.第2页，共31页，星期日，2025年，2月5日２４５３１平面嵌入的目的不过是让所有的边都不相交!目的２3４５１第3页，共31页，星期日，2025年，2月5日相关定义:平面嵌入:在平面内将一张图转化为所有边都不相交(除开段点处相交)的图的过程.平面图:能够进行平面嵌入的图.对于一张n个节点的图算法的目的：算法可以用O(n)的时间判断一张图是不是平面图并且实现平面嵌入,但由于时间的关系,我这里只介绍O(n2)的算法.定义第4页，共31页，星期日，2025年，2月5日深度优先遍历首先对图进行一次深度优先遍历.然后每个点将拥有属于它的边.将这些边做这样的定义:树边:在深度优先搜索树中,节点与它儿子相连的边.回落边:节点与它非儿子后裔相连的边.平面图的边不会超过3n-5条.[定理]第5页，共31页，星期日，2025年，2月5日简略流程建立一张空图GP,然后进行深度优先遍历,完成后按照逆向深度优先搜索序处理所有节点:把节点的树边加入图GP中.向下遍历,同时将节点的回落边加入到图GP中—walkdown.第6页，共31页，星期日，2025年，2月5日v2加入树边当处理节点v的时候,会首先加入节点v的树边,不过在加入树边的时候得做一个分离操作:v1c1c2v将v1和v2称做它们所在的连通分量的根.将v1和v2所在的分量称作v的子块.第7页，共31页，星期日，2025年，2月5日Walkdown—向下遍历(1)向下遍历—回落边的加入过程在处理节点v的时候,会进入它的每个子块进行顺时针和逆时针两次遍历,当回到连通分量的根节点或者遭遇终止节点时就会停止遍历.终止节点:是外部活跃节点但不是相关节点的节点.第8页，共31页，星期日，2025年，2月5日外部活跃与相关设当前处理节点为v,对于原有节点,定义如下:外部活跃节点:与v的祖先有连接的节点子块中有外部活跃节点的节点相关节点:与v有连接的节点子块中有相关节点的节点第9页，共31页，星期日，2025年，2月5日外部活跃与相关uvv’sws’w’ke在这张图中,当前处理节点为v,k,s为外部活跃节点,e,w为相关节点.第10页，共31页，星期日，2025年，2月5日Walkdown—向下遍历(2)由于终止节点的存在,随机的遍历会很快遭遇终止节点而终止遍历,这将导致需要加入的边没有加入到图GP中.所以在遍历的时候有一个原则.尽量晚的终止遍历.有两个法则来约束遍历,从而维护这个原则.第11页，共31页，星期日，2025年，2月5日Walkdown—向下遍历(2)法则1:当节点有多个子块需要遍历的时候,总是先进入没有外部活跃节点的子块进行遍历.法则2:每次进入子块进行遍历都优先选择是走向只具有相关性节点方向,否则选择走向具有相关性的节点的方向.第12页，共31页，星期日，2025年，2月5日Walkdown—向下遍历(2)节点是相关节点,那么加入回落边.在满足两个法则的情况下,向下遍历时,会依次处理下面几种情况:遇到终止节点或者块的根时,终止遍历.节点有包含相关节点的子块,到它子块中继续遍历.节点不是外部活跃节点,走向下一节点.第13页，共31页，星期日，2025年，2月5日当加入回落边的以后,会将该边所连接的两个块和它们之间的块全部合并.它和分离是对应的.节点所在块与子块合并后也不再拥有该子块.分离是在加入树边的时候.Walkdown—向下遍历(2)合并是在加入回落边以后.第14页，共31页，星期日，2025年，2月5日翻转操作为了将所有的回落边都顺利的加入图GP中,图GP必须始终满足一个性质.这个性质就是:外部活跃节点都必须留在外部面上.第15页，共31页，星期日，2025年，2月5日翻转操作我们把接触最外层空间的面,叫做外部面.(图中黄线标出的面)第16页，共31页，星期日，2025年，2月5日翻转操作为了将所有的回落边都顺利的加入图GP中,图GP必须始终满足一个性质.这个性质就是:外部活跃节点都必须留在外部面上.加入回落边的时候会覆盖向下遍历时经过的面,这可能导致外部活跃节点被覆盖,为了保证图GP的性质.定义一个翻转操作.第17页，共31页，星期日，2025年，2月5日翻转操作uvwev’wewewewewewewewewew