平面性辅助图

编辑:正要网互动百科 时间:2020-06-05 10:49:24
编辑 锁定
本词条缺少信息栏名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
平面性辅助图(planarity auxiliary graph)一类特殊的图,它是由判定一个图的平面性而引出的另一个图。
根据这个图是否有某种性质的圈来判定原来的图是否是可平面的.首先,用确向术(深探、左探或右探)求图G上的一个支撑树T,并给出G的一个对于T的树浸人.将T的边依端点出现的次序给以定向,以每一个节点(除树梢外)处的这样的边对作为新节点,在边对中必有一边为树边且方向为离开这个节点而另一边不为那条指向这个节点的树边.对于任何一对不相邻的上树边,若它们的基本圈至少有一个公共节点,则必有两个相应新节点的边对,其中两边分别落在两个基本圈上.从而,可以引进一条新边连此两新节点.并且,在新边上可以赋以一个权,即,当此新边相应的边对在这个树嵌人中相交奇数个点时为1;否则,为0.这样的一个由新节点和新边所得带权的新图,就称为平面性辅助图,记为Aux <G).它是刘彦佩于1978年首先引进的.由Aux <G)是否有奇权的圈就可以判定G是否为可平面的.一般而言,Aux(G)的阶和度均不超过原图阶的一个二次函数.以后又引进了第一类和第二类的平面性辅助图以得到线性时间的算法,Aux(G)也称为第。类辅助图.在第一类平面性辅助图中节点只是第。类节点集的一个子集,它相应于那些含有一条树边和一条上树边的边对.这就保证了它的阶不超过原图阶的一个线性函数.然而边的集合则必须要重新构造.而第二类平面性辅助图的节点集与第一类的相同,但边的集合是第一类的一个子集,并且使得它的度也不超过原图阶的一个线性函数.这就从理论上导致判定图的平面性与求平面嵌人都可以用线性时间算法实现.平面性辅助图不仅在判定图的平面性以及进行平面嵌人时有用,而且,在确定图的不可分离连通块以及3连通块、列出所有不等价的平面嵌人、图的平面分解以及判定平面图的同构、图的曲面嵌人等方面均有应用.
词条标签:
文化术语 文化