关于极大平面图自同构群的几个定理和生成算法

Some Theorems and a Algorithm on Automorphism Group of a Maximal Planar Graph

本文对极大平面图及其若干四着色通过其二色子图间的同构定义了四着色的同构 (定义6、7), 并给出相关定理. 定理A: 若G有同构四着色C1、C2, 置换σ是相应同构置换, 则σ是G的自同构. 定理B: G和其四着色C, 置换σ是其各二色子图共同的自同构, 则σ也是G的自同构.据此, 给出了求解G的自同构群的算法. 一个四连通或五连通的G, 其自同构问题被转化为三对子图的同构、自同构问题.这些子图的连通度通常为2. 点数仍为p, 边数仅为G的三分之一. 对相当广泛的图类,子图可为树或路,使问题的难度大为简化.文中给出两个具体图例. 说明了对数十个点的G, 在普通微机上(如133主频, 16M 内存)

In this paper, some definitions, theorems, and an algorithm about automorphism group of a maximal planar graph are given. Definition 6: Direct Isomorphism 4-coloring. For given maximal planar graph G with p vertices and its two 4-colorings C 1,C 2 ;G′ ij ,G″ ij is bichromatic subgraph of C 1,C 2 respectively. If G′ ij G″ ij ,1≤ i<j≤4, and σ is their common isomorphism replacement, then C 1 is direct isomorphism 4-coloring of C 2, σ is their isomorphism replacement. Definition 7: Isomorphism 4-coloring, For G and C 1,C 2,C 2=｛V″ 1,V″ 2,V″ 3,V″ 4｝, if σ: i→σ(i), ι=1,2,3,4, cause C 1C 2 σ, where C 2 σ=｛V″ σ(1) ,V″ σ(2) ,V″ σ(3) ,V″ σ(4) ｝, then C 1C 2, namely, C 1 is a isomorphism of C 2. Theorem A: For a given G and its two 4-colorings C 1,C 2, if C 1C 2 and σ is their common isomorphism replacement, then σ is an automorphism of the G. Theorem B: For given G and its a 4-coloring C, if σ is a common automorphism of G ij ,1≤i<j≤4, then σ is an automorphism of G. In section 4, we present our algorithm of generating automorphism group. The definitions in section 2 and the theorems in section 3 are the basis of our algorithm. The problem to find the automorphism of G is converted to one to find automorphism of G ij or isomorphism between G′ ij and G″ ij . In ref.[9] we have proved: ｜V 12 ∪V 34 ｜=｜V 1 ∪V 2∪V 3∪V 4｜=｜V｜= p ｜E 12 ∪E 34 ｜=p-2=｜E｜/3 Therefore the complexity of problem is reduced notably.