极大平面图

maximal planar graph 极大平面图的局部结构及其着色特性 G是极大平面图的充要条件是 “G是平面图 且 |E(G)| = 3*|V(G)|-6”。 如果只知道“G是简单图”和“m=3n-6”的话，是推不出“G是极大平面图”的。 王的书中多半是“若G是平面图，则G是极大平面图的充要条件是m=3n-6”。 只是平面图是不行的,应该是 “若G是简单平面图,则G是极大平面图的充要条件是m=3n-6” 构造极大平面图的加点法 设G是一个平面图，v为G的一个顶点，现将G画在平面上，求证：必存在一种画法使v在G边界上。 证明： 如果v不在G的边界上，则任选以v为一顶点的闭面D，将图在D外的部分全部反射到D内，则v就出现在了边界上。 例如： 下图ABCDEF，取闭面ABC，将外面的点EDF反射到ABC内(E'D'F')，则ABCD'E'F'与ABCDEF相同但B已调到了边界上。 极大平面图：n个顶点边数最多的简单平面图称为极大平面图。  割边：设e是G的一条边，若G中删去e连通分支数增加，就称e为G的一条割边。 定理：n顶点的极大平面图G中e=3n-6,d=2n-4。 其中e为边数,d为面数(包括最外面那个开面) 证： 易知： (1)，极大平面图G中每条边邻两个面。 (2)，极大平面图中每个面都是三角面。 由(1)(2)得e/d=3/2,代入欧拉公式d+n=e+2解得： e=3n-6 d=2n-4。 我们知道当图的顶点数n≥12时不存在正则极大平面图．相关文献提出了（k，l）-正则极大平面图的概念，并讨论了（5，6）-正则极大平面图的存在性．在相关文献中，作者分别讨论了阶n〉12的（k，l）-正则极大平面图的存在条件及构造方法．本文讨论了阶n（≤12）的（k，l）-正则极大平面图的存在性，除两种情况外，本文给出了阶n（≤12）的（k，l）-正则极大平面图的存在条件及其一种构造的例子． (共7页 1.引言 本文讨论的极大平面图仍记为G=（V，E），令其点数为p，边数为e。所讨论的层圈结构是相对于某点v∈V，且v不在无限面边界。还假定无限面边界有点w，记d(v, w) = r。仍记 Di即Di（v）= {u| u∈V，并且d(u, v)= i } 众所周知， 极大平面图中的分离3圈和分离4圈都是可约构形（reducible configuration）[2]。可约构形不可完备集概念在K. Apple 和W. Haken的四色定理证明中有核心地位。K. Apple等正是声称用计算机找到一个1936个元素的可约构形不可免完备集才宣布完成了四色定理的证明[3—5]。求证四色猜想的另一种努力是仅对排除某些已知可约构形的图G求证。K. Apple的证明极长，并且是花费了1200个机时用计算机辅助作出的，其细节的获得及论证的检验都甚困难。对K. Apple的证明持怀疑的人可能一直多有人在。这可从K. Apple答复责难的文章[6]中看出。这篇文章是面对认为证明有误的传言写的。文章除承认有相当广泛的持久的传言外，还披露一则要事：V. Schmidt 于1981年在其学位论文中检验K. Apple等人的证明时，发现了15个差错。K. Apple在这篇答辩文章中说，其中14个本质上都是“bookkeeping errors”。 K. Apple允诺将发表其原证明校订的完整新文本。由于几方面的原因，人们对四色定理简短证明的追求并没有中断。另外，图的一般K着色算法是NP问题[7、8]。对某些图类有效着色算法的研讨也与图的结构密切相关。本文的目的在于继续研讨极大平面图的结构特点及着色性质。我们假设G不包括分离3圈和4圈，即G是五连通的。这个假定自然推出G不含3次点和4次点，即对任意v，点的次（度）d(v) ≥5。 为了论述方便，用到以下图例。图1.a是五连通极大平面图中的最小图，它只有12个5次点，记为512，称之为点次序列。其Di中的点数序列称层序列，为1、5、5、1。图1。b和c 的两种序列数意义相同。 2.1 轮图 v和D1导出的图构成轮图，其样式如图2.a。这个图中，D1中每个点只有圈C1上左右两点相邻，不可能产生图2.b情况，图2.b中vab组成分离3圈，与G为五连通矛盾。 2.2 弦弧图 图1.b中D3导出圈C3。该C3外部不再有G的任何点。D3导出的该图可重新嵌入平面，得到如图3.a的同构形式。它只有圈和其内的弦组成。圈上边可称为弧。因其只含弦边和弧边而称为弦弧图。 一般来说，弦弧图有如下特征：所有点构成一个大圈，除圈上的边（弧）外，其它边都可画在圈内部（或圈外部），这圈内（外）的边称为弦。我们还假定这些弦把圈内（或外）都划分为三角形区域。如果还保存有大于3边的区域，则特称“非完满弦弧图”。弦弧图有以下性质。实际上这里的完满弦弧图既极大外平面图，弦弧图既一般的外平面图。 性质1： 含n几个点的弦弧图（n＞3）,有n条弧，n-3条弦，把整个平面划分为一个n边形和n-2个3角形。该性质可用欧拉公式推出，此从略。 性别2：一个n个点的弦弧图（n＞3），内次（指由弦边产生的次）为零的点至少有两个，最多有[n/2]个。（参见图3.b、3.c）。 性质3：弦弧图是唯一3色图。 2.3 圈树图 圈树图是Dr不生成圈时，Dr-1与Dr导出的一种图。或Dr-1生成圈C，Dr生成树To 在v不在无限面边界时树在圈外部。经过新的平面嵌入，可得同构形式，使树位于圈内，如图4.a样式。 性质1：连接图和树的边的数目ect=2p+pc-2 性质2：五连通极大平面图中圈树图中必有pc≥pt+4 性质3：圈树图可4色 2.4 平行圈——层间结构的简单情况 性质2 对于5的连通极大平面图，关于点v的层圈结构中，必定有D2≥D1，否则，C2上有间次大于2的点y，C1上有间次为1的点u。u的邻圈是分离4圈，与图G的五连通性矛盾。 性质3 平行圈可3色或4色。一种简单论证方法可仿照弦弧图方法，逐个用三色着色圈间三角形。一种简单论证方法可仿照最初着色三角相遇时，可能用到第4色调整。这种论证仅对图6.a情况可行。对图6.b和c情况，其复杂程度可能和完整四色定理同样难。 .5 悬结构——层间结构的一种复杂情况 2.6 囊结构——层间结构的又一种复杂情况 3.极大平面图的某种二元分解 （1）把整个G表示为两个弦弧图的某种组合。如果G有哈米尔顿性，即其全部点生成一个大圈。这个大圈和其内部弦组成一个弦弧图，这同一个大圈和其外部的弦组成另一个弦弧图。整个G就是两个弦弧图大圈重合得到的。图10就是图1.a的哈尔顿表示。 （2）图11是图1.a的另一种同构表示，图11中圈C1和其内部弦构成一个弦弧图，图C2及其外部弦构成一个弦弧图。两个弦弧图的圈C1和C2为平行圈。这里G表为两个唯一三色弦弧图的平行联接。 猜想A 五连通极大平面图G，都可以表为两个弦弧图的平行联接。 （3）可以证明，G能做如下的分解。G中全部点组成两个圈C1、C2。C1和其内部弦，C2和其外部弦，都构成两个弦弧图（见图12）。C1上外侧若干弦及C1的部分边组成圈C’1。C’1内部包括全部圈C1内部，且其内一切区域都是三角形。类似地，C2内部若干弦和C2的若干边组成圈C’2。圈C’2和C’1是平形圈。但这里，除去C’1、C’2之间边后两个连通支都已不再是3色图，而是4色图了。 （4）图13是图1.a的又一种同构表示。其中包括一个圈C，和一个树T。Vc和Vi包括全部点V， C及其外部边构成弦弧图，C及其内部元素组成圈树图。这是圈树图和弦弧图大圈重合构成的，或者看成是一个3色弦弧图与一个树（二色树）的平行联接。 猜想B 五连通极大平面图，可以表示为弦弧图及圈树图的组合（或弦弧图与树的平行联接），但这里的圈树图可能出现比2.3中复杂的情况，即圈内可能有悬结构。 该系列文章将经常用到以下几个基本概念，故首先介绍如下（均根据我自己的理解，力求用比较通俗的语言写出，如有不妥，请指正）：     极大平面图：若G是节点数大于等于3的平面图，在其任意两节点之间增加一条边，将不再是平面图，则称G是极大平面图。（极大不是节点或边最多的意思，而仅仅是在一定的节点数的前提下，边不可再增加扩大。我以前用“饱和”来表示这种状况。）     路：路是一个由节点和边组成的交错序列（其中各节点各不相同）：         v0e1v1e2v2……envn     圈：首尾相连的路称为圈（简单圈）。         v0e1v1e2v2……env0     树：一个图如果它的任意两个点之间都有路相联结，但其中不包含圈，称之为树。简而言之，树是不包含圈的路。  由于在平面图中，两相邻节点之间的边是唯一的，因此在文章中路和圈分别用以下方式描述：         v0-v1-v2……vn         v0-v1-v2……vn-v0   连通：两节点之间有路联结，则说这两个节点是连通的。     子图：设有两个图G=（Vg，Eg），H=（Vh，Eh），VhEh分别是VgEg的子集合，周围称图H是图G的子图；有如果图 G中那些两个端点都在Vh中的边，也都是Eh的元素，则称图H是图G的由节点集合Vh导出的子图。    已着四色的极大平面图的二色子图：我们考虑一个极大平面图G=（V，E）的一个四着色C=[V1，V2，V3，E4]。其中两种颜色导出的子图Gij，其节点节点集合就是ViVj  的和，其边集合就是全部联结Vi和Vj的边，Gij共有6个：G12，G34，G13，G24，G14，G23。它们可以自然地分为三组：G12和G34，G13和G24，G14和G23 。     为了统一，在一个对偶二色子图上，我分别用青色、羊红色画两个二色子图上的边，在我的文章中称之为有色边；同时为了显示各节点之间的全部联系，我将对偶二色子图的补图的边用灰色画出，称之为灰色边。 定义17.3 设G为简单平面图，若在G的任意不相邻的顶点u，v之间加边(u，v)，所得图为非平面图，则称G为极大平面图。 　　 从定义不难看出，K1，K2，K3，K4，,K5-e(K5删除任意一条边)都是极大平面图。还可以容易地证明下面两个定理。 　定理17.5 极大平面图是连通的。 　定理17.6 设G是n(n≥3)阶极大平面图，则G中不可能存在割点和桥。 　　极大平面图的最大特点由下面定理给出。 　定理17.7 设G为n(n≥3)阶简单连通的平面图，G为极大平面图当且仅当G的每个面的次数均为3. 　　证 本定理的充分性留在第二节的最后证明，下面只证必要性。 图17.3 　　因为G为简单平面图，所以G中无环和平行边。由定理17.5和17.6可知，G中无割点和桥。于是G中各面的次数大于或等于3，下面只需证明G各面的次数不可能大于3.假设面Ri的次数deg(Ri)=s≥4,见图17.3所示。 　　在G中，若v1与v3不相邻，在Ri内加边(v1，v3)不破坏平面性，这与G是极大平面图矛盾，因而v1与v3必相邻，由于Ri的存在，边(v1，v3)必在Ri外。类似地，v2与v4也必相邻，且边(v2，v4)也必在Ri外部，于是必产生(v1，v3)与(v2，v4)相交于Ri的外部，这又矛盾于G是平面图，所以必有s＝3，即G中不存在次数大于或等于4的面，所以G的每个面为3条边所围，也就是各面次数均为3. 　　在图17.4所示的各平面图中，只有(3)是极大平面图。 设G为n(n≥4)阶极大平面图，证明G的对偶图G*是2边-连通的3-正则图。 分析与解：          根据定义，3-边连通的图自然也是2-边连通的和1-边连通的（注意，证明2-边连通就是证明删除1条边后还连通就可以了，并不要求证明“边连通度为2”）。         3-正则图不一定是就是3-边连通的，反例如下：   *  ──  *  / \    / \   *   *  *   *  \ /    \ /   *  ──  *          课本定义理解要透,k-边连通是指最小边连通度>=k ,即可 ,3-正则图最少删除2条边后连同分支才可>=2,故为2-边连通          边连通度>=K就说图是K连通的,并不是你想的边连通度=2,比如说该题连通度=5.图是1边连通的也是2边连通的也是3边连通的...要证明它是2边连通的只要证明删除任一条边还是连通的即可      (1)由对偶图的性质可知，G*连通。又因为极大平面图均为简单图，所以G中无环， 故G*中无桥，于是G*2边—连通。      (2)由于G的阶数n≥4，由定理17.7可知G的每个面的次数均为3，因而G*为简单平面 图，且每个顶点的度数均为3，故G*为3—正则图。 另附：设n阶m条边的平面图是自对偶图，证明m=2n-2 设G*为G的对偶图，因为G为自对偶图，所以 　　　　G*G(同构) 　　由于对偶图都是连通的平面图，因而G连通，所以满足欧拉公式，即 　　　　n-m+r=2 其中r为G的面数。并且n*=n，由定理17.17可知，r=n*=n，代入欧拉公式，得         n-m+n=2 于是，解得         m=2n-2 设G是面数r<12的简单平面图，G中每个顶点的度数至少为3。 (1) 证明G中存在至多由4条边围成的面； (2) 给出一个例子说明，若G中的面数为12，且每个顶点的度至少为3，则(1)的结论不成立。 证明： (1)不妨设G是连通的，否则可以对它的每个连通分支进行讨论。因而由欧拉公式有:                        n-m+r=2                        （1） 又由已知条件知道 r<12 且 n≤2m/3                                   （2） 将式（2）的结果代入式（1）得 2<2m/3–m+12 得m<30      　              （3） 若所有的面均至少由5条边围成，则 5r≤2m 得 r≤2m/5                                 （4） 将式（2），（4）的结果代入式（1） 2≤2m/3-m+2m/5 得 m≥30                   （5） 式（3）与式（5）矛盾，因而必存在至多由4条边围成的面。 (2)十二面体图有12个面，每个顶点均为3度，每个面由5条边围成， 并没有4条边围成的面。 命题： 任意阶数大于等于3的极大可平面图一定是Hamilton图, 显然总存在N阶（N>3）具有Hamilton性的极大可平面图。 但是是否每一N阶（N>3）的极大可平面图总是Hamilton图，我不知道。 我没构造出反例，亦没有证明猜想。我认为你的猜想是对的,并且,我还认为,任意n>3的极大平面图不仅是hamiltom图,而且它的每一条边都存在于一个H圈中. 我们从任一面出发,逐渐扩圈,就能得到这个结果,不过是否对所有极大平面图都成立,我还未能证明,我想,这也是你正在思考的吧,我下次再把具体的方法给出来,大家共同讨论. 设G为N阶极大可平面图， 首先，可以证明当N>3时，对于任意v属于G，v的邻点的集合N(v)在G中的导出子图Q含有Hamiltion圈。v可能在这个Hamiltion圈里面，也可能在这个Hamiltion圈外。 由图的拓扑等价性，我们可以认为v被Q中的圈包围了。 当然，我们可以去掉Q中的某些边，使v不被Q中的圈包围，即将v从包围圈中解放出来。 其次，任一N阶极大可平面图都可以通过减去N-3条边的方式，将每个顶点v从其邻集在G中的导出子图Q的圈中解放出来，同时使剩下的边和点组成一个N阶的极大外部可平面图。这个不难证明，也不难给出算法。 再次，我们知道任一N阶极大外部可平面图都是Hamiltion图（其外部面的边界即是其Hamiltion圈）。这个结论见 张先迪，李正良的《图论及其应用》（高等教育出版社）第130页。 注：另外我发现设G为N阶极大外部可平面图对于任意v属于G，v的邻点的集合N(v)在G中的导出子图Q为一条路。（呵呵）反例: 设G为5阶极大平面图,则G有6个面.在G的每个面(面的边界为一个三角形)中取一个顶点,将该顶点与它所处的三角形的三个顶点相连,设此时形成的极大平面图为H,则H-G的连通分支数为6-----大于|G|,则H不满足Hamilton图的必要条件.