（运筹学与控制论专业论文）图的运算与最小圈基的结构.pdf

摘要 关于图的最小圈基的研究从产生发展到现在，众多的学者包括数学家，生物学 家，物理学家等等已经提出了许多相关的方法但应该指出的是，到目前为止，这 些算法和结果都往往仅限于针对某种或某些类型的图的最小圈基结构，而从图的运 算的角度考虑最小圈基的结构，这方面的工作确是鲜为人知的，本文正是首先由一 般的情况着手，再扩展到射影平面的相关结论。 首先，我们研究2 连通的简单平面图的运算对最小圈基的影响：设g ，g 2 为2 连 通的简单平面图，置为g l 的最小圈基，岛为g 2 的最小圈基 1 、当图g ln g 2 = j 即g l ，仍相交于一个点时，图g 的最小圈基为g l g 2 的最小 圈基的并集。 2 、当图g in g 2 = x , y 即g l ，g 2 相交于两个点时，由于图的运算使图的圈基维 数增加了l ，图g 的最小圈基为g l ，伤的最小圈基的并集以及一个新圈。 3 、当图g ln g 2 = p 。即g i , g 2 相交于一条过x , y 两点的最短路时，图g 的最小 圈基为图g “g 2 的最小圈基的井集。 4 、当图g tn g z = ，即g l ，g 2 相交于一条过x , y 两点的非最短路，且 图g j , g 2 中所有的二度节点都位于路p 0 上我们分两种不同的情况在定理2 2 ，4 和定 理2 2 5 中做出了详尽论述。其中主要的思想是通过图的运算引进了新的通过点x , y 的 最短路，对原最小圈基做出相应的运算。 在第三章中讨论2 一连通的在射影平面上可大边宽度嵌入图的最小圈基结构， 并且就这样的大边宽度嵌入图有唯一最长丽圈和不唯一最长面圈两种情况在定 理3 1 2 和定理3 1 3 中做了详尽论述。考虑一个图的圈空间f i 圈基的组合结构，证明 了一个图的所有最小圈基具有唯一结构，即任意的两个最小圈笨之问存在1 i 对应， 使得相互对应的圈具有相同长度。由此可知，任两个最小圈基中所含k 圈( k 3 ) 的 数目相同 2 一连通图g 是可大边宽度嵌入射影平面m ，记尹为g 的所有面圈集合，c 一。为 图g 的最长面圈，若对任意非面圈的可收缩圈口，都有任意的卢，州口 e 厂一g 。， 使得倒 i g 。i 。 一个曲面s 的e u l e r 示性数* ( s ) 定义如下： - 2 一妫， s = s h 邢) = 2 一k s = n k e u l e r 公式【2 】设g 是一个2 一胞腔嵌入在曲面s | ：的图，如果g 有n 个顶点，口条边，在 曲面s 上有，个面，则，l q + f = 工( s ) 。 图的圈空间理论最早源于k i r c h h o f f 关于电路理论的研究【8 】。从理论上看，拟阵 理论是其动力之一【3 巧1 。后经众多学者工作，其在结构分析【6 j ，以及生命科学【9 】等 领域均有应用。对最小圈基的研究也引起研究者的极大兴趣，文献【3 】给出了其简短 第一章绪论3 综述。 短圈是区分不同的分子图的一个很重要的特征，尤其是在有机化学和结构生物学 上虽然最小圈基往往不是唯一的，但是最小圈基的结构却引起了生物学家的广泛 关注有机碳水化合物通常表现为多轮的结构( 即大多数由一些短圈构成) ，高分 子聚合物，例如：d n a ，对峨和蛋白质也形成一种我们所熟知的3 维结构，这种3 维 结构对它们的生物特性来说是至关重要的最小圈基的理论将整个圈空间压缩成一 种简洁的形式，这样给我们的计算带来了极大的方便，因而尤其具有实用价值。文 献0 0 在更多的一般图中扩展了前人在计算最小圈基长度方面的工作【ll 】。 同时，氨基酸，包括r n a 和d n a ，通常都呈现一种特殊的“二次连接”结构， 这些结构都是外可平面的或是次立方体的，这意味着点的最大度为3 。这些“二 次连接”结构图的最小圈基是唯一的【1 1 1 近年来，更多的研究表明所谓的“假 性节点”结构发挥越来越重要的作用。由于这些结构违反了外可平面性，并且最 简要的来说，导致了“二次可分”结构。这些圈能嵌入到“书脊”是一条牛成树的 。二页书( 2 - p a g e b o o k ) ”中，它们的最小圈基对大多数图来说往往不是唯一的了。 本文研究简单平面图的运算对图的最小圈基的影响，进而分不同的情况，包括两 个平面相交于一个点，相交于一条边，相交于两个点，相交于一条展短路，相交于 一条非最短路，探讨了平面上两面嵌入图的最小圈基结构。 在讨论图的运算与图的最小圈基结构的关系之前，我们首先介绍有关最小圈基结 构的已有的工作。 1 2 几个引理及证明 以下结果是我们主要结论的基础之一。 引理1 2 1 任意一个2 连通图g 的最小圈基由线性无关的圈组成。 显然。口 第一章馨论 4 引理1 工2 觑g ) = 妒一l ( 其中妒为2 连通平面图g 的面数) ，即一一1 个面圈在圈空间中 线性无关。 证明：依欧拉公式知：“g ) 一d g ) + 庐= 2 一幻，又因为觑g ) = s ( g ) 一l ，( g ) + l ；g = 0 ， 所以有庐= d g ) 一郴) + 2 ( = 觑g ) 4 - 1 ) 设图g 有妒一1 个面圈是线性相关的，记 为斯，p 五，刃o ，存在一组不全为0 的数a i a 2 一。堪- i ，使得 a l o f l o a 2 0 f 2 毋0 4 卜l 刃一l = 0 ( ) 不妨设a l 0 ，则与蛳相邻的所有面圈前面的系数都不为0 。否则，若存在一个面 圈颧与奶相邻，但a i = 0 ，则蛳中与鲋相邻的边在对称差运算后将会保留下来，这 样，( ) 式右边不会等于0 。因为这庐一1 个面圈依次相邻接，从而推知a h a 2 ，4 _ i 都 不为0 ，这样就有： a l o f la 2 0 f 2 毋o 口卜i 刃0 t = o f , 其中口厅是剩下的那个面圈这与( ) 矛盾。所以，g 中任意庐一1 个面圈是线性无 关的。口 引理1 2 32 - 连通平面图g 的庐一1 个面圈构成一组基。 证明：由引理1 2 2 和觑g ) = 驴一1 得到。 口 本节建立一个h a l l 型定理，在证明之前，首先叙述一些定义和事实令 朋= 岱i ，s 2 ，j 。) 是一个集族，朋的一个相异代表系( 简称为s d r ) 是指存在m 个不互不相交的不同元 素，记为a f ( 1 f _ ，1 ) ，使得a f s f ，f 1 ，2 ，m 。h a l l 得到了下面的结论，此结论 刻画了含有s d r 的一组集合： 事实1 ( h a l l 定理f 1 2 】) 令朋= ( s l ，s 2 ，s 。) 是一个集族，则朋有一个s d r 且仅 当对于朋中的任意k 个子集族，它们的并至少含有k 个元素，其中k = l ，2 。研 事实2 令k 是数域尸上的一个n 维线性向量空间，缸l ，i f 2 ，j 和够l 岛。，风 是k 的 第一章绪论 5 两个基则集族朋= 岱l ，s 2 ，s 。) 有一个s d r ，其中s i 是m ，i 2 ，中生成届o = l ，2 ，竹) 的一组向量 证明令s j = i n t ( 1 3 , ) ，i = l ，2 ，n 。如果朋没有s d r ，则由h a l l 定理得：存在一个整 数k 和m 中的k 个子集族s j i ，s b ，s k ，使得这k 个子集族的并至多含有k - 1 个向量， 因此，忆中的k 个线性无关的向量可以由至多k - 1 个向量生成，矛盾，证毕 口 这里使用的记号t n r ( a ) 借用于文献f 2 1 ，表示生成口的一组向量。下面的定理给 出了判定一个基是最小圈基的充分必要条件： 引理1 2 a 1 3 设霉是2 连通图g 的一个圈基，则雩是g 的最小圈基的充要条件是 对g 中任一个e _ 子图c ：任意的口i n t ( c ) 都有l a t l l c l ，其中i n t ( c ) 是当中生成 圈c 的向量全体 证明：( 充分性) 令口是一个最小圈基且h 是图g 的一个e - 子图( 即圈空问中的 一个向量) 若h 不满足上述条件，则i n t ( n ) 中存在一个长度大于h 的向量a t 于 是，b 一口+ h 是一个长度小于b 的长度的基，与b 的选取矛盾。 ( 必要性)另一方面，令b 是满足定理条件的一个基但不是最小圈基，则存在 一个最小圈基，其长度小于b 的长度。令 f = l f f l ，a t 2 。，神 其中觑g ) 是图g 圈空间的秩，则对f 中的每个向量嘶，b 中存在一组向量s f = 知) 生成嘶，因此对任意的a i n t ( c e j ) ，有l a t i i2 蚓。由事实l 和事实2 可知，集 族m = ( s t ，s 2 ，s 咸g ) ) 有一个s d r ，假设这个s d r 是u 。，厶，允。，) ，使得 s u = l ，2 ，觑g ) ) 。结合上述条件可得的长度不小于b 的长度，矛盾，证毕。 口 这个引理表明了2 连通图的最小圈基特征。 第二章2 平面图的最小国基结构 2 1 背景介绍和基本概念 图的圈空间理论最早源于k i r c h h o f f 关于电路理论的研究【8 】从理论上看，拟阵 理论是其动力之一f 3 _ 5 】。后经众多学者工作，其在结构分析【6 1 ，以及生命科学【9 】等 领域均有应用。而最小圈基结构傲为圈空间理论中的性质，也引起研究者的极大兴 趣和关注。 在拓扑图论的嵌入理论中，圈运算有特殊用途。例如z h a 在1 9 9 1 年曾提出这样一 个猜想：面宽度至少为3 的嵌入在一个可定向曲面上的图包含一个非平凡的曲面可 分离圈。我们容易得到：一个面宽度至少3 的嵌入图的一个圈c 是可分离的当且仅 当c 可以由一族面圈生成。通过对一个具有特定性质的短圈的计算，h o r t o n 1 4 首先 得到了一个找到最小圈基的多项式时问算法。之后，t h o m a s s e n 1 5 i 正明了，如果一 组圈中的某些圈满足三路条件( 3 - p a t h c o n d i t i o n ) ，则存在一个多项式时间算法可以 找到这组圈中的一个最短圈，基于此，t h o m a s s e n 证明了下列几类短圈可以在多项式 时间内找到： ( 1 ) 嵌入图的一个最短的不可收缩圈； ( 2 ) 嵌入图的一个最短不可分离圈； ( 3 ) 嵌入图的一个最短的单侧圈。 但是，对于一组不满足三路条件的圈的情形如何呢? m o h a r 和t h o m a s s e n 在他们 的专著( 文献【2 】，p 1 1 2 ) 中提出了以下问题： ( a ) 是否存在多项式时问算法找到个嵌入图的最短的可收缩圈? ( b ) 是否存在多项式时问算法找到一个嵌入图的最短的曲面可分离圈? 6 第二章2 平面图的最小圈基结构7 ( c ) 是否存在多项式时问算法找到一个嵌入图的最短的双侧圈? 关于图的最小圈基的结构，前人已有许多相关的结果和算法，而本文从将图的运 算的角度考虑最小圈基的结构。 定义2 1 1 定叉图的对称差运算g 1 由g 2 ：如果两个图中有相同的边，则通过对称差 运算后。那些相同的边都被消除了，而不相同的边仍然保持 定义2 1 2 用”l i 表示求圈的长度的运算符号例如：旧表示圈c 的长度 定义2 1 3 如果2 连通平面图的所有节点都位于两个面圈上，则称图g 为2 平面图 2 22 平面图的最小圈基结构 在这一节中，我们根据两个2 连通平面图的不同的相交情况( 包括两个图相交于 一个节点，两个节点，一条最短路和一条非最短路) ，分五个定理论述了其最小圈 基结构与图的运算的关系。 当两个2 连通平面图仅相交于一个节点的情况下，我们考察这两个2 连通平面图 的并集的最小圈基的结构。我们发现新生成的图的最小豳基是由两个原罔的最小嘲 基的并集组成的。 定理2 工l 设g l ，g 2 为2 连通的平面图，g 1n g 2 = 工j ，则g = g lo g 2 的最小圈基 为：b = b lu 玩其中岛和岛分别为g i 和g 2 的最小圈基 4 g lg 2 ( 图2 2 1 ) g = g l u g 2 第二章2 - 平面圈的最小圈基结构 证明：g i ，g 2 是2 连通的平面图，g = g iu g 2 ，设妒l ，锄分别为g “g 2 的面圈数， 则g i g 2 的圈基维数：i b l i = 妒l l ，i 晚i ：赴一l 。图g = g i u g 2 的面圈数为：毋= l 1 ) + ( 锄一1 ) + l ，则图g 的圈基维数分别为：嘲= 妒一i = 九+ 也一2 ； ( 庐i 1 ) + ( 九一1 ) = i b l i + i 岛i = i b i u 毋1 图g 中任意的圈c ，则c g i 或ceg 2 ，即c 可由口= b iu b 2 线性表示。对于 图g l 中的圈c ，那么有c = c jo 砰o o q ，c e 岛( f = l ，2 曲，则i q i q i ； 若c g 2 ，同理，lc i i i ，c j 髓u ；l ，2 ，七) ，即对于基b = b ，u 晚对任意 的c f i r a ( c ) e b ，有i c f l i c i ，则口= b iu 岛是g 的最小圈基。定理2 2 1 证毕。 口 当两个2 连通的平面图仅相交于两个节点的情况下，我们考察这两个图的并集的 最小圈基的结构。我们发现新生成的图的最小圈基是由这两个原图的最小圈基和新 图中含有这两个相交节点的最短圈组成的。 定理2 2 2 设g l g 2 为2 连通的平面图，g l n g 2 = k 讨，则g = g iu g 2 的最小圈基 为：b = b i u 岛u 岛其中局和b 2 分j i j 为g i g 2 的最小圈基，圈岛= 砖u 砖， 砘，嘿分别是g l g 2 中连接t y 两点的最短路。 b ：固二圄 g lg 2 ( 图2 2 2 ) g = g 1ug 2 证明：g l ，g 2 是2 一连通的平面图，g i n 6 2 = i x , y ，设驴l ，加分别为g l g 2 的面圈数， 则g 1 ，g 2 的圈基维数分别为：旧l = 机一l ，慨i _ 2 一i 。图g = g lu g 2 的面圈数 为：妒= ( 妒i 1 ) + ( 九一1 ) + 2 = l + 妒2 ，则图g 的圈基维数：例= 妒一1 = 妒i + 也一l = ( 庐l 1 ) 4 - ( 如一1 ) + l = l b l i + i 曰2 l + 1 = l b lu b 2u c 盯i 。 图g 中的圈c ，可以分为以下三种情况： 8 第二章2 平面图的最小圈基结构 9 1 若c e g i ，“= l ，2 ) ，则c 可由b 线性表示； 2 若c = c o ，则c 可口由线性表示i 3 若c n g l o 且c ng 2 o ，且c c 0 那么有：c o c o = c l 毋c z ，其 中圈c 分别是图g 咔- 含有路赡的圈，即比cgeg j ( f ；l ，2 ) t 则c 可以这样对 称差表示：c = c i 毋c 2o c b ，即：c = ( c i 、砖) u ( c 2 砖) ，由于砖是g i 中连 接x , y 两点的最短路，戚为g 2 中连接x , y 两点的最短路那么1 1 c 的长度i c l = l c l 、砖i + i c 2 、p 纠i g 、砖i + l p q = i g i ，又由于对任意的口ei n t ( g ) 毋， 有m i g i 。1 1 1i c l = i g 、砖l + i c 2 砖l i 砖i + i 砖i = i c 一。综上所述，对任意 的口e i n t ( c ) b ，都有s l c i ，则b = b lu b 2 u l c 0 是g 的最小圈基。定理2 2 2 证 毕。 口 当两个2 连通的平面图仅相交于一条最短路时，我们从图的运算的角度来研究这 两个图的并集的最小圈基结构。我们发现新生成的图的最小圈基为这两个原图的最 小圈基的并集 定理2 2 3 设g i , g 2 为2 一连通的平面图，g ln g 2 = ，则g = g lug 2 的最小圈 基为：b = b 1u 晚，其中b l 和现分别为g l 和g 2 的最小圈基，p 聃为g l g 2 中连 接x , y 两点的最短路 ) r g l g 2 ( 图2 2 3 ) g = g 1u g 2 证明：g l g 2 是2 一连通的平面图，g = g l u g 2 ，设l ，也分别为g l ，g 2 的面圈数， 则g 1 ，g 2 的圈基维数分别为：泌l i 妒i l ，i b = i = 也一l 。图g = g lug 2 的面圈 数为：妒= ( 九一1 ) + ( 也一1 ) + l ，则图g 的圈基维数：i b i = 庐一l = 庐l + 锄一2 = 第二章2 - 平面图的最小圃基结构 ( 妒l 1 ) + ( 赴一1 ) = i b l i + i 岛i = i b i u b 2 i 图g 中任意的圈c ，可分为下面两种情况讨论： 1 若圈c g ，( f = 1 。2 ) 则c 可由b 线性表示： 2 如果圈c 不完全属于图g 1 也不完全属于图g 2 ，即c n g l 0 且c n g 2 0 ，则 圈c 可由如下对称差的形式表示：c = c l oc 2 = c l i o 毋c i ，o 审c 2 l o o 白， 其中p fcc ieg l ，p 巧c 2cg 2 ，并且l c l l ，c l ，lcb l c 2 l c 甜c 岛 即圈c 可由最小圈基口中元素线性表示。由于路氏为图g l g 2 中连接x , y 两点的最 短路，因此路c l 、的长度和路c l 、的长度都大于路的长度：i c i 、l i 岛i ，| c 2 、i i 岛i 。因此圈c 的长度：l c | c = i c j $ c 2 1 = l c i 、i + 1 c 2 i l c l i + i 尸一= i c d ；同理，i c - pi g i 。而对于圈c l ，c 2 的组成元素，任意的口ei n t ( c 1 ) e 研， 任意的卢ei n t ( c 2 ) e 岛，由最小圈基的性质可知，i o lsi c i l ，蜘i c 2 i 。因此i 口ls i c i i i c i ；1 1 3 1si c 2 i i c i 。那么，最小圈基b = b lu b 2 中任意的瑾i n t ( c ) c 占， 有1 0 1 s l c | 则b = b iu 岛是图g 的最小圈基。定理2 2 3 证毕 口 下面讨论两个图交于一条非最短路的情况：如下图所示，图g 。，g 2 分别为除 了路p 口上的节点外无二度节点的图。图g = 0 lu g 2 ，g ln g 2 = ，并且 ，同时 为g “g 2 中连接x , y 两点，内部节点全为二度节点的路。如下图所示： g 1g 2 ( 图2 2 4 ) g = g l u g 2 下面分两种情况来讨论：定理2 2 4 中的路p 。是g l 中连接葺y 两点的最短路，定 理2 2 5 则考虑一般情形。 定理2 2 4 设g l ，g 2 为2 一连通的平面图，g in g 2 = p f ，g l ，g 2 中连接五y 两点的最短 1 0 第二章2 平面图的最小圉基结构 路分别为岛，砖，其中路的内部节点的度都为2 ，同时，g i 、尸9 ，g 2 中无2 度 节点那么g = g l u g 2 的最小圈基为：b = ( 甄l q ，c ；，磷j ) u i c ， u 岛 其中蜀，如分* q 为图g “g 2 的最小圈基，i q ，c ；，啡 为b t 中所有包含的圈的集 合，圈= q o u 砖，( f = 1 ，d 1 机，卢? y v 左为b l 中含p w 的豳4 右为g 2 中含的最短豳岛 豳基元素de 丑( 经过对称差运算得到) ( 图2 2 5 ) 证明：g m ，g 2 是2 一连通的平面图，咖，咖分别为g l g 2 的面圈数，则g l ，g 2 的圈基 维数分别为：i b l i = 九一1 ，i 玩l = 九一l 。图g = g lug 2 的面圈数为：矿= 劬i 一1 ) + ( 也一1 ) + l ，则图g 的圈基维数：例= 妒一l = 妒i + 锄一2 = ( 庐i 1 ) + ( 锄一1 ) = l 曰1 i + l b 2 i = i 曰1u 岛i 因为为g i , 0 2 中连接x , y 两点且其节点除x , y 之外都是二度节点的路， 则甄种存在某个含有路p 舸的圈口，若否，鼠中任意的圈口都不含有路尸。，由于 路中节点除x , y 以外的节点都是二度节点。说明含路的圈不可以完全由不 含路的圈生成，即含路p 胛的圈的生成元素中必须有含路的圈。而由假 设，路p 。不属于甄中的任何一个圈，则g l 中含路尸。的圈不可由马线性表示，这 与岛是g l 的最小圈基矛盾。因此，口l 中必然存在含有只，的圈，设鼠中有t 个圈含 有，将其按长度由长到短排列：i q ，q ，q 。同理，岛中也存在含有路p 母的 圈声，令c 矗是g 2 中含的最短圈，则岛= 砖u 岛，其中碌为g 2 中连接x , y 的 最短路。下面就图g = g lu g 2 中的圈c 分四种情况讨论如下： 情形1 、图g 2 中任意的圈c ，c 可由岛线性表示，而岛口，则圈c 可b 由线 性表示。同时对于任意的口i n t ( c ) b 2 有川si c l ，因此对任意的口i n t ( c ) 第二章2 平面图的最小霹基结构 口有m s i q 情形2 、图g l 中不含有路的圈c ，则圈c 的生成元素中也没有含路的 圈即i n i ( c ) n q ，c ； = o ，那么圈c 可由b j 中不含路的圈( a j l cm p ，q ) s 曰线性表示。并且，对于任意的口i n t ( c ) e ( 风、l q 。磷 ) 有l a i i c i ，因此对任 意的口i r a ( c ) b 有1 0 1 s i c l 。 情形3 、对于图g 1 中含有路的圈c ，即i n t ( c ) n i q ，q l o ，那么圈c 的 生成元素中有含有路的圈，设为c ，。由于砖为g 2 中连接x , y 两点的最短路， 那么臻的长度小于图g 2 中连接x , y 两点的所有路的长度，因此有磙的长度小 于岛的长度：i 砖i l 岛i 而圈岛由和焉对称差运算得到，岛= 砖o ， 对角中的集合l q ，哆i 做如下对称差运算：c 1 = q o c 0 ，= 磷毋岛 则c = o c ；o = 毋o c | y o ，由于c j 是由g l 中含有的圈q 与 图g 2 中含有的最小圈岛对称差得到的，则圈c f 的长度：i l = i q 毋岛l = 噼、l + i 岛、l = 瞬、i + l 砖l s 噼、l + i l = i q i ；而圈q 的长度：l q i _ 峨、l + i i l 岛i + i 焉| - i 岛l 则i c i 嘲之| c j f ，cl 岛i 。而对于圈c 的生成元素 中不含路尸匆的圈口，有aeb i 、l c ；，磷 且f 0 1 i c i 。因此圈c 的所有生成元素， 任意的口i n t ( c ) b ，有i 口i 蔓i c i 。 情形4 、如果圈c 不完全属于图g l 也不完全属于图g 2 ，即c n g l o 且c n g 2 - 1 o ，圈c 可由圈c l 和圈g 对称差表示：c = c l 峨，其中圈c i c 2 分别是图g “g 2 中 含有路的圈：e c te g i ，p 目c 2 g 2 。 设网c l 可由风中元素 口1 ，劬，l 线性表出：c l _ f f l0 6 t 2 0 o 吼，由于g t 、 中无二度节点，那么g i 中任意两个面圈的交：陋f n 口f i l ，则圈c i 的长 度l c i i ：l 嘶| _ 2 ( s 一1 ) = i o r l i + 1 0 2 i + + i 口，l - 2 0 1 ) 。由于g 1 户0 中无二度节 点，即构成c l 的每个生成元素至多给路c l 、p 0 提供一条边，则c l 的生成元素的个 数j i c l i l 尸一( 岛是g i 中连接x , y 两点的最短路) 。下而计算圈c 的长度， 由于c = c l 审c 2 = 口lo 毋毋c 2 ，则圈c 的长度：i c | - l c l 、p 聊i + i c 2 r v l l 口l l + i n 乜i + + l 口，i 一2 ( s 1 ) 一i 尸f i + i c j 、尸砂i 。 通过做差比较圈c 与圈c l 的生成元素嘶( f = l ，2 ，j ) 的长度的大小关系： 1 2 第二章2 平面图的最小圈基结构 l q 1 1 1 i i = i 口l l + + i 口卜i i + l 口“l l + + l 以i 一2 ( s 1 ) 一i p _ 竹i + i c 量、尸w i 3 ( s 1 ) 一2 ( s 1 ) 一i p f i + i c 2 尸f i 3 ( s 一1 ) 一2 ( s 1 ) 一j + i c j 、尸w l o i ) 一2 ( s 1 ) 一s + 1 = 0 即对任意的口j ，n t ( c 1 ) e b i ，有i c i c2 k i 对于c i 那些含有路的生成元素，属于b i 中含有路的集合l q ，c ：i ， 对c l 中的生成元素中某个c 二 q ，啡 ，设c i 可以这样表示；c l = 串o ， 则l c i i i c ，i 。圈c 由图g l g 2 中含有公共路的圈c i ，c 2 做对称差得到：c = c i o c 2 ；毋c ；o o c 2 = o c l o c 刍o o c 2 u = l ，助。由于砖是g 2 中 连接x , y 两点的最短路，赡的长度小于g 2 中连接x , y 两点的任何一条路的长 度：l 碍i 蔓i c 2 蹦，l 赡isl p 0 。又由于圈c l 与圈c 2 相交于路，则圈c 的长 度：i c l = i g 、岛 + i c j 、i 。而圈c j 是由图g i 中含路尸f 的圈c ，与图g 2 中含路 的最短圈c 匆对称差得到：c i = c ，o c 岛，则圈的长度：i i = l c ；、尸一+ l 岛、p 一= 怫、i + i 碍isi c i 岛i + 1 c 2 l = i c l ，即l q l c j l 。图g 2 中含路的最短圈岛由 路尸咿和图g 2 中连接五y 两点的最短路砖构成，则圈c _ f 的长度：i c 纠= i p 匆i + i 赡i i 碍i 2 ( 因为i 砧i l 砖i 时是类似的情况) 。分别 对集合l c ：，c ，c f ，l q ，q ，c ： 中元素做对称差运算：c ：= c ：e q ，c + = 砰oc i ，c i = c i o q ；q = q o c l ，q = q 毋c ：，凹= q o c j 。 对图g 中的圈c 分以下几种情况讨论： 情形l 、对于图g l ，g 2 中不含有路氏任意的圈c ，则圈c 的生成元素中也 没有含路的圈，即c g l 或c g 2 ，有i n t ( c ) n i c ：，口 = o 且l m ( c ) n i d ，a = o ，则经过图的运算g = g 1ug 2 后形成新的的最小圈基对其无影 响，c 可由b 线性表示，且对任意的口i n t l 【c ) ，有i c l 1 0 1 。 情形2 、对于图g l 中任意含有路的圈c ，则圈c 的生成元素中有含路 的圈，即ceg l 且l m ( c ) n c ：，讲l o ，则存在g l 中某个含路p 。的圈，设 第二章2 平面图的最4 、圈基结构 为d ，使得：c = o q o 。对圈q 做对称差运算：c i = 砰o c l o c ：， 其中钟由圈q 和图g 2 中含路的最短圈c ；对称差得到：四= qo q 。则 圈c = o c i o c i o c ：四的长度l 钟i = 叫毋q i = t c i 、岛i + 峨l _ 峨、户q + l 赡l 峨、，0 + i p 一= 瞄f ，因此经过对称差运算后得到的圈c 的长度小 于圈q 的长度：瞄l i c ? i 。由于圈c ：是由图g l 中连接x y 两点的最短路砖和p 匆的 对称差得到，则圈c ：的长度t c l t = 鸭o i = i i + i i 峨、i + l i = t o , l 对于由图g 。中含路的最短圈c ：和图g 2 中含路的最短圈c ：对称差得到的 圈c ：+ 有：i c ：i _ j c ：o c ；l - i 砖l + l 焉l i c i 、岛l + 1 l - 嘲，因此嘲 畔m 综上所述，有以下长度关系成立：i c i c 峨l i c i i ，i c ：i i c l i ，即圈c 的长度大于等 于新的最小圈基b 中其生成元素的长度。 于其没有受到新构成的最小圈基的影响， 意口e i n t ( c ) b ，有i c i 1 0 1 而对于圈c 中不含路的生成元素，由 长度仍然小于等于圈c 的长度因此任 情形3 、对于图g 2 中含有路的任意的圈c ，则圈c 的生成元素中必然有含有 路p 口的圈，即c g 2 且i n t ( c ) n l q ，q o 。存在g 2 中某个含路p p 的圈使 得：c = oc o = o 叫+ o c i 毋，且l c l i 叫| f h 于圈c ，由图g 2 中含 路的圈q 与图g l 中含路，0 的最短圈c ：对称差得到：= 创e c ：，则圈q 的 长度i c ；| - 吲、i + | c ：、i = 哆、i + l 砖l i g 。i 。有时f w ( g ) 用最短的不可收缩曲线于 图g 的公共交点的个数来表示。若一个嵌入的面宽度至少为2 ，则称这个嵌入为强嵌 入。显然，在一个2 一连通图的强嵌入中，每一个面边界都是一个圈( 叫做面圈) 。 定义3 1 1 定义圈基b 中所有元素边的长度之和为圈基的长度，记为i f b ) 定理3 1 1 设厂为图g 在射影平面土的大边宽度嵌入得到的面圈集合，8 是g 的最小 1 7 第三孝射影平面上嵌入困的最小圈基 圈基，则口中任意的面圈c 的生成元素都是可收缩圈 证明：对最小圈基口中任意的口i n t ( c ) cb ，由定理1 2 4 可得：口的长度小于等 于圈c 的长度。又由于图g 在射影平面可大边宽度嵌入，即图g 的最短不可收缩 圈的长度c w g 大于图g 最长面圈g 。的长度，因此大于图g 中所有面圈的长度， 即：州g ) i c 。l i cj 。那么图g 的所有不可收缩圈的长度大于面圈的长度，因 此图g 的面圈只能由可收缩圈生成，所以口是可收缩圈。定理3 2 1 证毕口 注：这条定理表明，如果图g 可在射影平面大边宽度嵌入，那么长度小于面圈 的圈都是可收缩圈。 定理3 1 22 - 连通图g 在射影平面上可天边宽度嵌入，得到面圈集合为尹若圈c 是 集合厂中唯一最长面圈，则图g 任意的最小圈基矗中都包舍集合尹一c 的充要条件 是：对于任恋的可收缩圈球，如果口不属于集合尹一c ，那么集合厂一c 中生成的口的 元素口的长度都小于口的长度 证明：( 充分性) 取图6 的某个与集合尹一g 。的交集的元素个数最少的最 小圈基b ，则存在圈ae ( 尹一g 。) 、b ，则圈基b 中圈c l 的任意生成元素口，都 有a 的长度小于等于圈c t 的长度，又由于图g 在射影平面上可大边宽度嵌入， 则e w ( a ) l g 。f l c i l 的长度，即长度小于内面圈的圈都是可收缩圈，可收缩圈不 可由不可收缩圈线性表示 令b = b i + 岛，其中玩是可收缩圈集合，历是不可收缩圈集合。由于玩是可收 缩圈集合，那么置可由集合尹一g 。线性表示。则任意的面圈g 尹一g 。，由 于可收缩嘲都是由可收缩圈生成的，则任意的口i n t ( g ) eb ，部有口eb l ， 即面圈集合尸一，可由可收缩圈集晶线性表示。若存在非面圈的可收缩 圈a b l 、( 尹一g 。) ，口可由面圈集合生成。由条件，任意的面圈c i n t ( a ) 尹一g 。，有i c i l 1 0 1 ，令集合群= b l 一口+ c i ，则蜀线性无关。 ( 若否， 对任意的圈c i i n t ( a ) c ( 9 - 一g 。) ，都有耳= b 1 一口+ a 线性相关，即圈c i 可 由b 1 一口线性表示，从而0 1 可由b l 一口线性表示，矛盾) ，而集合e 中元索的长度之 1 8 第三掌射影平面上嵌入困的最小圉基 和： f ( 耳) i l i ( b t ) i ，则基f = 蟛+ 晚的长度小于基8 的长度，这与丑= 甄+ b 2 是最小 圈基矛盾。因此b i = 尹一g 。，而占又是图g 的所有最小圈基中与集合尹一g 。交集 元素个数最小的最小圈基，因此图g 所有的最小圈基丑中都含有面圈集合尹一c 一。 ( 必要性) 若图g 的任意的最小圈基口都包含集合厂一c ，由最小圈基的 性质知。对任意非面圈的可收缩圈口，集合尹一c 中口的所有生成元酃，声的 长度小于等于口的长度。若存在某仰使得芦的长度等于口的长度，则构造新的 最小圈基：尻= 尹一c 一卢+ 口，则e 中元素线性无关，( 若否，可收缩圈口可 由厂一c + 卢线性表示，则豳口的表示不唯一，矛盾) 。而蜀中所有元素的长 度之和z ( 尻) = ，( 尹一c ) ，于是存在新的最小圈基：f = e + b 2 ，与最小圈 基b = b l + 岛相比：“伊) = f ( 固，而且尹一c 不属于最小圈基矿，矛盾因此，对 集合尹一c 中口的生成元素芦，都有口的长度小于口的长度。定理3 2 2 证毕口 1 9 定理3 1 32 连通图g 在射影平面上可大边宽度嵌入得到集合尹，其中c i ，c 2 g 分 别是图g 的t 条长度相等的最长面圈，则图g 的所有最小圈基b 都包含集合尹一g ( j = l ，d 的充要条件是：对任意不属于集合尹一c f 的可收缩圈口，都有任意 的卢ei n t ( f f ) 9 - 一0 ，使得卢的长度小于等于口的长度 证明：( 充分性) 若存在图g 的最小圈基b ，对图g 的k 条最长面圈c j ，( f = l ，t ) 都有面圈集合尹一c ，不是口的真子集，即口与集合厂一c f 交集的元素个 数：l 口n ( 9 - 一c 1 ) l 妒一1 ( 其中口表示图g 的面圈数) 。那么存在图g 的某个最小 圈基矿使得f 与面圈集合厂一g 的交集的元素个数达到最多。对于集合厂一c f 中 不属于b 的圈，由定理3 1 1 可得，最小圈基驴中所有生成圈c 的元素口都是可收缩 圈。 令b = b l + b 2 ，b l 是可收缩圈集合，现是不可收缩圈集合。由于b i 是町收缩 圈集合，因此口l 可由集合厂一c 线性表示，且蜀的维数小于等于集合厂一c 的维 数。而由定理3 2 t ，任意的面圈ce 尹一c i ，c 可由可收缩圈集线性表示，即面圈 集合厂一c j 可由日线性表示，因此最等价于集合广一c f 。 若存在可收缩圈口属于鼠而不属于厂一c j ，那么集合厂一g 中生成口的任 第三孝射影平面上姨入困的最小田基 意的圈c ，都有圈c 的长度小于等于口的长度而由于口是可收缩圈，则f i t 可 由厂一c j 线性表示，那么对于尹一g 中口的生成元素中那些不属于口的圈c ， 即c ( 尹一c j ) n ( i n t ( 、研，令耳= b i 一口+ c ，则曰中元素线性无关，( 若 否，如果圈cei n t ( 可由b l 一口线性表示，则口可由b i 一口线性表示，矛盾) 。 则e 的长度f ( 耳) 小于等于目的长度i ( b 1 ) 若故耳) = t ( b 1 ) 则g 的与集合厂一c f 的交 集的元素个数大于b i 的与集合尹一g 的交集的元素个数，矛盾：若h 耳) “蜀) 则 令f = 群+ b 2 那么最小圈基b i 的长度小于口的长度，矛盾因此b l = 尹一g ，即 图g 的任意最小圈基曰都包含有面圈集合尹一g 其中c i ( f = i 。2 幻为图g 的最长面 圈 ( 必要性) 对图g 的k 条最长面圈g ( i = l ，2 助都存在某个最小圈基口， 使褥集合厂一c f 曰，那么任意不属于面圈集合尹一c f 的可收缩圈口，都有集 合厂一a 中生成口的元素卢，使得旧i 翻。定理3 2 3 证毕。d 通过以上两个定理的证明，自然地，得到以下推论： 推论3 2 12 一连通图g 在射影平面上可大边宽度嵌入，则g 的任何最小圈基都含有 妒一1 个可收缩圈( 其中妒表示图的面圈数) 3 2计算最小圈基的个数 本章考虑一个图的圈空间中圈基的组合结构，证明了图的所有最小圈基具有唯一 结构，即任意的两个最小圈基之间存在1 1 对应，使得相互对应的圈具有相同长度。 由此可知，任两个最小圈基中所含k 一圈( t 3 ) 的数目相同。 事实3 1 1 3 】令8 是嵌入在某些曲面上的图的一个圈基，则当至少包含v ( x ) 个不可 分离圈，其中v ( ) 是曲面的e u l a 污格，即： “) ：l 2 9 2s j g ，= 第三掌射影平面上嵌入团的最小圈基2 1 下面定理说明一个嵌入图的最小圈基必须包含一个最短的不可分离圈( 也就是不 可收缩圈) ： 定理3 2 1 0 6 】令g 是嵌入在一个曲面上的2 连通图，c 是一个最短的不可分离圃，则 存在一个最小圈基包舍c ，另一方面，