（运筹学与控制论专业论文）几类图的亏格分布问题.pdf

摘要 本文研究连通图嵌入拓扑曲面的分布，即嵌入的有限个组合等价类的分布 间题. 在图的最小亏格和最大亏格得到广泛研究的同时，只有少数几类图 的亏格分布或全嵌入分布得到了解决. 对亏格分布的研究始于二十世纪八 十年代后期，在随 后的十几年中逐步得到发展. 1 9 8 9 年，fur s t 等首先 得出c l o s e d - e n d l a d d e r s l 。 和c o b b l e s t o n e p a t h s 人的 亏 格 分布， 接 着， g r o s s 等人给出了 环 束氏 的亏格分布的 计算公 式.以 上三类图的亏格分 布的 单峰性 也相应得到了 证明.t e s a r 于2 0 0 0 年计 算 得出r i n g e l l a d d e r s 凡 的亏格分布. 1 9 9 4 年，c h e n 等将亏格分布推广到全嵌人分布， 并给 出了项链图n和l, 人的全嵌入分布.2 0 0 2 年，k w a k 和l e e 进一步 建立了环束 b 和双极图d n 的全嵌入多项式的递推公式. 该文主要解决了 类树图 和类圈图的亏格分布问 题. 首先，在环束的亏格分 布的基础上， 利用切分与还原运算建立了 类树图的亏格多项式， 并将这种 运算推广到带割边的 一般情形.其次， 应用刘彦佩提出的联树嵌入法， 进 一步解决了标准类圈图 和类圈图的亏格分布. 最后， 讨论了类树图的亏格 分布的单峰性问题. 关键词:图;曲 面; 嵌入;亏格; 类树图. 木壮件言、 毛师问惫 勿全文公布 1 1 1 a b s t r a c t t h i s t h e s i s i n v e s t i g a t e s t h e d i s t r i b u t i o n o f c o n n e c t e d g r a p h e m b e d d i n g s i n t o t o p o l o g i c a l s u r f a c e s , t h a t i s , t h e d i s t r i b u t i o n o f t h e fi n i t e s e t o f c o m - b i n a t o r i a l e q u i v a l e n c e c l a s s e s o f e m b e d d i n g s . wh e r e a s t h e m i n i m u m g e n u s a n d m a x i m u m g e n u s a r e s t u d i e d e x t e n s i v e l y , t h e g e n u s d i s t r i b u t i o n s o r t h e t o t a l e m b e d d i n g d i s t r i b u t i o n s f o r o n l y a f e w c l a s s e s o f g r a p h s a r e s o l v e d t h e r e s e a r c h o f g e n u s d i s t r i b u t i o n i s c o m m e n c e d i n t h e l a t e r 1 9 8 0 s , a n d g r a d u a l l y d e v e l o p e d i n m o r e t h a n o n e d e c a d e s u b s e q u e n t l y . i n 1 9 8 9 , f u r s t e t a l fi r s t l y o b t a i n e d t h e g e n u s d i s t r i b u t i o n s f o r c l o s e d - e n d l a d d e r s 乙 。 a n d c o b b l e s t o n e p a t h s 人. t h e n , g r o s s e t a l f o u n d t h e g e n u s d i s t r i b u t i o n s f o r b o u q u e t s o f c i r c l e s 凡i t w a s p r o v e d t h a t t h e g e n u s d i s t r i b u t i o n o f a n y m e m b e r o f t h e a b o v e t h r e e c l a s s e s w a s u n i m o d a l a c c o r d i n g l y . t h e g e n u s d i s t r i b u t i o n s f o r r i n g e l l a d d e r s 凡 w e r e g o t b y t e s a r i n 2 0 0 0 . i n 1 9 9 4 , c h e n e t a l d e v e l o p e d t h e g e n u s d i s t r i b u t i o n i n t o t h e t o t a l e m b e d d i n g d i s - t r i b u t i o n a n d p r o v i d e d t h e t o t a l e m b e d d i n g d i s t r i b u t i o n s f o r n e c k l a c e凡 a n d l, 人.k w a k a n d l e e e s t a b l i s h e d a r e c u r s i v e f o r m u l a o f t h e t o t a l e m b e d d i n g d i s t r i b u t i o n s f o r 氏 a n d d i p o l e s 氏 t h e g e n u s d i s t r i b u t i o n s f o r t r e e - l i k e g r a p h s a n d c i r c l e - l i k e g r a p h s a r e s o l v e d i n t h i s p a p e r . f i r s t , b a s e d o n t h e g e n u s d i s t r i b u t i o n f o r 氏 a n d u s i n g t h e t e c h n i q u e s o f b i s e c t i o n a n d i t s i n v e r s e , w e e s t a b l i s h t h e g e n u s p o l y n o m i a l f o r t r e e - l i k e g r a p h s , w e a l s o a p p l y t h e m e t h o d t o t h e g e n e r a l c a s e c o n - t a i n i n g a c u t - e d g e . s e c o n d , 勿 a p p l i n g t h e j o i n t t r e e m e t h o d fi r s t ly p o s e d 妙 l i u y a n p e i , t h e g e n u s d i s t r i b u t i o n s f o r s t a n d a r d c i r c l e - li k e g r a p h s a n d 1 v c i r c l e - l i k e g r a p h s a r e o b t a i n e d . f i n a ll y , t h e u n i m o d a l i t y o f t h e g e n u s d i s - t r i b u t i o n s f o r t r e e - l i k e g r a p h s i s d i s c u s s e d . ke y w o r d s :s u r f a c e ; e m b e d d i n g ; g e n u s ; t r e e - l i k e 第一章引言与综述 1 . 1 引 言 对于同构图的 不变氮 性质的研究， 是图论的核心内 容 这些属性独 立于图的标号或图的表示 众所周知， 点数、 边数、 色数及圈秩等是同构 图 的不变 量， 然而， 它幻都不 是完 全不变 量， 即 都不足以 用来区 分不同构 的图. 拓扑图 论主 要研究如 何嵌入不同的 拓扑曲 面， 为得到同 构图的完全不 变 量提供了 一种途径. 1 9 7 9 年， 刘彦佩教授在图的 嵌人表示匡 9 1 的 基础 上， 揭示了 联树嵌入法 长期以来， 大多数拓扑餐论的研究人员 都将研究重 心放在图的最小亏格的确定上， 也有一些人主要钻研图的最大亏格或是具 有 高 度 对 称 性的 特 殊 类 型的图 1 9 8 7 年，g r o s s 和f lu r 叫8 1 系 统 地 研 究了 嵌入空同 的不 变量及其层级关系 ， 考察了一个图 在所有闭曲 面上 的所 有嵌、 人的分布， 即亏格分布， 而不再仅仅讨论一个嵌入或一个图能 否嵌入某个 曲 面的问 题. 亏格 分布给出 了不变量的一个有序 集， 把所有图 的 集合 分成 了 更细的 子范畴， 而不只是对应最小兮格或任何其它单一的嵌入曲面. 通常， 计算一个图 的整个亏格分布要比 只计算其最小亏格难度大得 多 对于任一 特定的图 或一 类图， 如完 全图， 推导其整个亏格 分布的 计算 公式要比 得到其最小亏格的公式困难得多. 另 一方面， 由 嵌入的随机样本观察亏格分布的性质也是可能的. 然旅. 对于作为图的 不变量的亏格分布的信息， 至今所知甚少 例如，亏格分布 是否总是单峰的. 目 前侧重子首先考虑些特殊图类的亏格分布及其性质 ， 进而由 特殊 第一章 引言与综述 到一般，得到一般图的亏格分布及相关性质， 对于各 类图 的 号格分布的公式推导正处于 探索之中， 而且有待子作为 一 个重 要课 题 进行深入 研究f u r s 吐 6 等已 经 得出 两类 梯图c l o s e d - e n d l a d d e r s 和c o b b l e s t o n e p a t h s 的亏格 分 布， 这 两 类 梯图 的 最 大亏 格随 着图 的阶 的 增 大而 增大g r o s s 侧等 人 应用j a c k s o 城 咧 关 子 置 换的 循 环结 构 的 一个计数公式， 得到了 环 束 氏 的亏 格分布的递推公 式. t e s a r (3 0 ) 于 2 0 0 0 年 导出r i n g e l l a d d 二 的 亏格 分布 式c h e n 阁等 将 亏 格 分 布 推广到 全嵌入分粼 即包含亏格分布和叉帽分布， 并给出了项链图n 的全嵌入 分 布 及 上面 提 到的 两类 梯图 的 全 嵌 人分布. 对 子 轮图 和 完 全图 ，mull(23) 等虽然没有完整给出这两类图的亏格分布， 但 为计算这些图的亏格分布提 供了一 种 方法k u a k 和l e e 扭 句改进了 这种 方法， 并于2 0 0 2 年得到环束 和双极图( d i p o l e s ) d 。 的 全嵌人多 项式的 递推式k i m和z e e 1 4 则开始 着手研究双极图 和环束组成的新的复合图的亏格分布 另 外， 环束 g ( 和上 述 两 类梯图6 l 的 亏 格 分 布的 单 峰 性已 经分 别在 相 应文中 给出了 证明. 以 下给出 拓扑图 论中 的重要定 义及基本事实. 文中的 术语可参见参考 文 献 1 1 , 7 和!2 1 1 . 2 图的嵌人 l图的定义 一 个图g , 是由 非空 的 节点 集v 岭) 和节 点 集中 无 序 的 点 对( 称为 溯 的 集合e ( g ) 构成的. 两点重合的 一条边称 为一 个白 环 连接不同 的两点 的 边多于一条时、 称之为重边 不含自 环或重边的图， 称为简单图， 第一章 引言与综述 在拓扑图 论中， 通常指的是非简单图，即可以带自 环和重边的图. 为简单起见， 在不会混淆的 情况下， 图的节点集 v ( c ) 和边集e ( g ) 分别简写为 v和e . 以下讨论的所有图均为连 通且无向的图 u拓扑曲面 两个拓扑空间的同 胚是连续区间上的一个 连续的双射. 设x和y是 两个拓扑空间， 若存在从x到y的一 .十双射h : x*y ， 则称x和y同 胚 一个连通的2 维流形或曲 面是一个拓扑空向， 其中 每个点的邻域都与 闭的单位圆 盘同胚 以下考虑的是闭曲 瓦 即紧致的无 边缘的曲面 事实上，可以视为平 面上的一个偶数条边的正多边形， 每边分配一个方向 且两两成对， 将同一 对边依同 方向 合而 为一所得到的. 在 合而为一中， 可以 收缩或伸长， 但不 能断裂. 曲 面闭 曲 线 公理四 在曲 面上 的 任 何一 条闭曲 线， 要么 有两 侧( 左 侧 和右侧) ， 要么只有一侧， 二者必居其一 有两侧的闭曲 线称为双侧曲线 否则， 称为单侧曲线. 一个曲面， 若其上 的所有闭曲线全是双侧的，则称它为定向曲面; 否 则， 称为不可定向曲面 在保持连通性不变的 条件下， 一个曲 面所能劈分的闭曲线的最大数 目，称为这个曲面的准亏格 定理1 , 1 2 1 定向曲 面的准亏 格总为偶数. 第一章 引言与综述 对于一个定向曲面， 我们定义曲面的亏格为它的准亏格之半; 而对于 不可定向曲 面， 定义曲 面的叉帽为它的 准亏格. 例如， 球面的亏格是 0 . 环 面的亏格是 1 ， 射影平面的叉帽是 l 亏格为k 的定向曲 面记为乓认=0 , 1 , 2 . . . ， 叉帽为k的不可定向曲 面记为n , ( k =1 , 2 , ) . i i i图的嵌入 图在曲面上的嵌入是从图的拓扑表示到曲面的一个连续的双射.图的 拓扑表示的像也常简称为图. 两个嵌入称为等价的， 如果它们之间 存在一个同胚. 我们认为等价的 嵌入是相同的，所以关于嵌人的计数都是在等价意义下的计数. 设 g-s是图 g在曲面s上的一个嵌入， 则 g的像的补称为面或 区 如果每一个面都与一个开的圆 盘同 胚， 则称该嵌 入为一个胞腔嵌入( 或 2 胞腔嵌幻. 以下讨论的都是胞腔嵌入， 简称嵌入 由图g的-个支撑树 t连同每条非树边， 分为带相同字母的 两边而得到的图， 称为 口的联树， 记 为g . 通 过分 析 联树g在 平面 上的 不同 嵌 入 及 数目 ， 进而 得到图g在 曲面上的嵌人及分布的方法， 称为联树嵌入法. 设g=( 认e ) 是一个图 ，f是g在曲 面s上的嵌入g*s的 面的 的集合， 有以下著名的 e u l e r 公式: i v 一 e l + i f c =2 一 p 其中p 匆如 果s 是 一 个亏 格为9 的 定 向 曲 面 ;p =k 如 果s 是叉 帽 为 k 的不可定向曲面 称八必二司一 ! 州+1 为图g的b e t t i 数， 简 记为口由e u l e r 公式 第一章 引言与综述 。 ， 。， ， 尽 ， ， 、 *、; 飞 、_ 一，任 二. 二，、，。，。二 ma 导 9愁 上 万j 气 阅 1 士j 总夕 ; 支 及. ， i 1 - f 】 i 1 t j , .浏 狡a19 k x 1 , 泛 尸一 刁 三。 月 嵌 入 亏 格 为 _a2 的 定 向 曲 面 ， 贝 。称 。 是 上 可 。的 ， i v旋系( r o t a t i o n s y s t e m ) 设g是一个图，v v ( g ) , 。 处的旋 是指与点。 关 联的 边的循环 置 换 . 自 环 对 应 的 两 条半 边在 旋中 各自 独立出 现 . 显 然， 度 为d 的 点 有( d - 1 ) ! 个不同的旋. 图g的所有点的旋构成的集合， 称为图g的旋系. 若图g有n 个点 v 1 , v 2 , , v ， 对 应 度 分 别 为d i , 内 ， 二 ， 嵘 ， 则g的 旋 的 总 数 为 回 图的所有定向 嵌人组成的集合与图的 旋系之间 有一个一一对应关系 (3 1 ) . 从而有以下定理 定理1 .2 17 1惫图g的定向嵌入总数为 h e ff t e r 于十九世纪， 其后近一个世纪， i i ( d i 一1 ) ! i =1 e d mo n d s将这种对应关系应 用 于简 单图 中 ， 其系 统内 容 则由y o u n g s 3 3 给出 .g 。 和a l p e r t 将 其 推广到带自 环和重边的情形， 1 .3 亏格分布 g r o s s 和f u r s t 闭最 先引 入图 在闭 的 定向 曲 面上 嵌 入的 集 合按亏 格划 分.以下给出一些定义和基本结论. 对于任何连通图g , g在亏格为 k 的定向曲 面上的嵌入数记为 9 k ( g ) , 使 得9 k ( g ) 为正 值的无 的最小 值称为g的 最小亏 格， 记为、in ( g ) . 类似 第一章 引言与综述 地， 使得g k ( g ) 为正值的k 的最大值称为g的 最 大亏 格， 记为勺 r_( g ) . 区 间!、试g ) ,y . - ( g ) 称 为g的 亏 格 范围 通 常称 一 个曲 面 在亏格 范围内 即指该曲 面的亏格在亏格范围内. 定 理1 .3 17 )设g g k ( g ) 都是正的， 图g的亏格分布， 亏格多项式的形式 是任一连通图， 对于任何在亏格范围内的整数 k数 指的 是序列g o ( g ) , g 1 ( g ) , 9 2 ( g ) , . ， . 有时 将其记为 g g ( 二 ) =g o ( g ) + 9 l ( g ) x + g 2 ( g ) x 2 +( 1 . 2 ) 在 不会 混淆 的 情况 下，g k ( g ) 简 写 为g k由 于 亏 格 范围 是 有 限 的， 这 是一 个有限次的多项式. 亏格分布是平凡的图只有两类: 树和单圈图. 显然， 球面是树能嵌人 的唯一曲面 边数和点数相同的连 通图称为圈. 和树一样， 圈也不存在非球面上的 嵌入 作为圈的推广， 设 g是一个连 通图， 若去掉 g中的某条边后得到 g的 支 撑 树 且 仍 连 通， 则 称g为 单圈图 应 用x u o n g 公 式!3 2 ， 可 证明 单 圈图只能嵌入球面 定理1 .4 12 4 设图g既非树也 非单圈图 ， 则g的 亏 格范围 至 少包 含两 个整数 设g k ( g ) 表示连通图g在定向曲面 +s k 上的嵌入数， 以下给出五类 连 通图 在定 向曲 面 上的 亏 格分布:c o b b l e s t o n e p a t h s , c lo s e d - e n d l a d d e r s , r in g e l l a d d e r s , 环束和 双极图 定 理1 .5 16 1将。 点 路p的 每 条 边 增加 一 条 重 边 且 两 端 点 各增 加 一个 第一章 引言与综述 自 环，所得的图称为c o b b l e s t o n e p a t h j . . 则 圈 9k(jn)4n-k3k( 、 “) = 2 .4n-k3、一 (nk 二 :) 定 理1 . 6 同 将。 点 路p与k 2 作 笛 卡 儿 积 并将 对应的 两 对端点 分 别 增加一 条 重 边， 所 得图 称 为c l o s e d - e n d l a d d e r l n . 则 gk(l .) = 2n- i+k /n + 1(l k 一 “1 2n + 2 - 3kjjj n + l - k ( 1 . 4 ) 定理1 .7 13 0 1分别将l ， 两 端的 重 边之 一上 增加 一个新点。 然后将这两 个新点用一条新的边连接 起来， 所 得图 称为r i n g e l l a d d e r 风. 则 二 (、 ) 一 2 3k+ 1 ( n - “ 、 + 2 3k j n 一 k 、 (2 n + k _ ， 、一 。) t n - “ 士 、 邵、 一 ”一 k/ 一 k 一1 -一 、k 一2/ + (2n+k-1 - 2 3k-2) cn -k 全 奋 ) ( 1 . 5 ) 定 理1 .8 19 1由 一个 点二 个自 环 构 成 的 图 称 为 环 束凡. 设9 k ( 凡) 简 记 为夕 、 ( 。 ) ， 则 ( 1 ) 当k 1 时 ，9 k ( 2 ) 二0 ; ( 4 ) 当二 2 时，9 k ( 动可由 以 下递推式求得: ( 。 十1 ) g k ( 二 )二 4 ( 2 。 一 1 ) ( 2 。 一 3 ) ( 。 一 1 ) 2 ( 二 一 2 ) 9 k - , ( 。 一 2 ) + 4 ( 2 。 一 1 ) ( 。 一 1 ) b k ( n 一 1 ) ( 1 . 6 ) 第一章 引言与综述 定 理1 . 9 12 $ 由 两个 点 及两 点 之间 有。 条 边相连的图 称 为双极图 d i p o l e ) d n ， 有 9 k ( d n ) 2 ( 。 一1 ) f 。 ( 二 +1 ) is ( n + 1 , n 一2 k ) )( 1 . 7 ) 其中可 。 +1 , 。 一2 劝是第一类s t i r l i n g 数. 1 . 4 文章结构 本论文主要讨论了两大类图的亏格分布问题，即类树图和类圈图. 第一章主要介绍 研究背景、 发展现状、 基本概念、 原理及已 有结论. 第 二章在环束的亏格分布的基础上， 利用切分与还原的方法， 通过研究 m系 列图的亏格多项式， 解决了类树图 的亏格分布， 并将这一方法推广到带割 边的一 般图上，为其亏格分布间 题的解决提供了一种途径. 在此基础上， 第三章运用联树嵌人法原理首先得出标准类圈图的亏格分布的递推公式， 通过进一步探索给出了 类圈图的亏格分布多项式， 第四章证明了 类树图的 亏格分布是单峰的 如无特别说明，以 下考虑的均是连通图在定向曲 面上的嵌入间题. 且 有时将定向嵌入简称为嵌入. 第二章类树图的亏格多项式 2 . 1 相关概念 设r是带若千自 环的图， 若去掉所有自 环后的图是r的支撑树t ， 则 称r是类树图 . 类树图 是带环束的图中 最简单的一类图， 其亏格分布的解 决， 对于所有 带环 束的图 来说， 具有基础性的 作用. 设亡 en且t y- -6 。 ， 从环束凡 的唯一节点引出t 条连杆，所得图 定义 为州， 由s 和t 的 所有 可 能 取值 构成 的码 的 集 合定 义 为m系 列图 ， 即 m = m al , m .2 ， 一， m ol ， 二 ， m i m 2 _ _ _ ， i , a j ， 叫， m 2 ， ， ， t_ , _ m ， 二， 二 今 以 下八 习简 记 为m , 定义 2 . 1 设。 是图g的边，将。 从它的一个内点。一分为二，使 e 切分为两条新的 边e + 和e - ， 每边中 新增加的1 度点。 + 和矿 称为 切分新 点， 对边e 的 这一运算称为对边。 的切分运算， 若再将切分运算所得的两 条边还原为原来的一条边， 称这一运算为对边 己 的 还原运算. 边 。 的 还原 运算是切分运算的逆运算. 2 . 2 m系列图的亏格多项式及性质 下面通过m系列图 与环束之间的联系， 逐步求得m系列图的亏格多 项式 第二章 类树图的亏格多项式 引理2 . 1 !2 1 1任何树都只 能嵌入在球面上， 任何图g都可嵌入到定向 曲面上， 设。 ， 为图g中p 次节点的数目 ， 则其嵌入总数为 n o ( g ) =n( ( f 一 1 ) !) 引 理2 .2 12 1 1设。 。 为图g中p 次 节点的 数目 ( 2 . 1 ) q为图 g的 b e t t i 数，则 g嵌入不可定向曲面的数目 为 ( 2 a 一 1 ) 1 i ( ( ; 一 1 ) !) n 0 定 理2 .1对于m s 与b , ， 有p o ( m) = 证明根据联树嵌入法 12 1 1 原理， 当 2 s f o ( b b ) ( 2 . 2 ) ( s 全1 ) ( 2 .3 ) s 引出一条连杆，不改变 g嵌入定向曲面的亏格。 1 时， 从环束 b s 的节点 只使各嵌入数同倍，设 为原来的: : 倍， 则 。 o ( m . ) =。 ， n o ( b . ) ， 由引 3m 2 .1 知，n o ( m) = ( ( 2 s + 1 ) 一1 ) ! , n o ( b , ) =( 2 s 一1 ) r ， 故: ， =2 s ， 从ff p o ( m . ) =2 s p o ( b s ) 另 外， 当 =0 时， m o 与b o 的 亏格多项 式 相同 ， 即p o ( m o ) =p o ( b o ) 引理2 .3 令g为只有一条边不是自 环的图， 则g在定向曲面上不是 上可嵌入的， 当 且仅当 ， 每一个 节 点都与奇数个自 环关联. 证明g在定向曲面上不是上可嵌入的，等价于说，g可嵌入的定 、 ， 、 二撬，方止渭 、， ， q 一2 、 、二 月。 、 、，_ 二 ， - 一一一 一、 ， 一 ， 向 曲 面 的 亏 格 至 多 为!知一 1 = (- 未 二 ， 这 就 是 说 ， 在 所 有 字 母 都 为 异 号 的 - 一一 一 一 - 一一 l z j 一 z j ， 盯 . 份 “ ，户， ， 门j- 1 , a 分 i. , 联树(2 l 上， 每 个节点 处一定有一条 上树边( 即自 环) 所 对应的 字母在 拓扑 等价中被抵消，也即每个节点处一定有奇数个自 环 反之， 若 g的每一个 二二 二 二.，、止 ， 口 一2 ， 曲 四 倒 ，恨 -t - 3v 力i -i l 节点都与奇数个自 环关联。则 g可嵌人的定向 ， 即g不是上可嵌入的 第二章 类树图的亏格多项式 定理2 .2 设g的定义同引理2 .3 ， 并设 其两节点处所带自 环个数分别 为 8 l 和 s 2 ， 则 p o ( g ) =p o ( ms j p o ( m s 2 )( 2 . 4 ) 证明 据 文 献间， 环 束 是 上 可 嵌 入的 ， 从 而m系 列 也 是 上 可 嵌 入 的 . 故a ff e , , m e ， 的最大亏格分别为 。 一 、 一 (、 ，) 一 :l , 1,2 k 2 =,r -( ms a ) = 臀1 设m , m , ， 的亏格多项式分别为 p o ( m 8 , 卜 艺a rn x , xz p o ( m s z ) 二艺b m x - , 由 引理 2 .3 , g的最大亏格为 k = 7 . . ( g )= 当， : ， ， : 均为奇 数时 其它情形 从而k=k l +凡 不 妨设m i n k 1 , k 2 ) =凡, m a x k l , k 2 二k 2 ， 并设g的亏 格多项 式 为 x p o ( g ) =艺c _ x - 第二章 类树图的亏格多项式 1 2 其 中c - = 9 - ( g )由 联 树 嵌 入 法叫， 有 价= m e a i b m - , i =0 k, e a i b m - x 坛 =0 k, e a i b m _ , 当0 mk , 时 当凡 仇 k 2 时 当k 2 。 1 )( 2 . 5 ) 证明( 归 纳法) ( i ) 当t =1 时，由 定理 2 . 1 结论成立 ( i i ) 假 设t =k 时 结 论 成 立， 当t =k 十 1 时，m ek + 1 比心 多 一 条 连杆， 不影响嵌入曲 面的亏格，但使嵌入数目 同倍增长， 设为 # 2 倍， 即 p o ( 心+ ) = 6 2 p o ( 码) 又 。 。 ( 心+ ， ) =( 2 s + ( k + 1 ) 一 1 ) ! =( 2 s + k ) ! 第二章 类树图的亏格多项式 且 n o ( 衅) =( 2 s + k 一 1 ) ! 故 2 =2 s +k 由 归 纳 假 设p o ( 衅) 二 所以 ( 2 s +k 一1 ) ! ( 2 s 一1 ) ! p o ( b s ) , 。 (、 一 卜 (， 十 “ )(2s + k - 1)i(2s - 1)! 二 二 ) p o ( b a ) . 由 数学归纳法， 原命题成立， 推论 2 . 1 推论 2 . 2 推论 2 . 3 p o ( 码) = p o a d= p o ( 衅 ) = ( 2 s 十t 一1 ) ! ( 2 s ) . p o ( ms ) r l ( 2 s +t 一 i i ) p o m ) j 工 =z 2 s - 2r i ( 1 十 言 牛- )p o (m 0 ) 方=7 l s一7 2 9 2 . 3 类树图的亏格多项式 类树图的定义见本章第一节， 以下分析解决其亏格多项式 图g的亏 格多项式的 各项系数所构成的序列即表征了图口的亏格分布 引理 2 .4 设连通图g有一条割边 。 ， 对 。 作切分运算后有两个连通 分支， 分别设为 g i , g 2 ， 则 句劝 份伶 p o ( g ) 证明 类似于定理2 .2 . 当g , =几( g i ) p o ( g 2 ) =风 g 2 =入 么 z 时， 即得定理2 . 2 . 引 理2 . 5设图g由g i , g 2 , . n o ( g ) 二， g ti 共w个连 通分支构成， 则 二h n a ( g w 第二章 类树图 的亏格多项式 p o ( g ) 二np o ( 味) ( 2 .8 ) 举 =1 证明由引 理2 . 1 及连通性的概念容易得式( 2 .7 ) ， 据组合学中的乘法 原 理及多项 式乘 法可得式( 2 .8 ) . 由 于自 变量取1 时 ，p o w) 即为。 o ( g ) , 故令式( 2 .8 ) 两边自 变量取1 也可得式( 2 了 ) ， 图 2 . 1 连通图 g 引理 2 .6 设g是一连通图( 如图2 . 1 ) , 设。 en且石 e 1 1 , 川门 n ， 子 图风通 过 割 边今与 子图e o 相连， 对气作 切 分 运算 后 有 。 十习个连 通 分 支f o , f i ， 二， f n ， 且f f 对应乓. 若n o ( g ) 表 示图g在 定向 曲 面 上的 嵌 人总数。则 n o ( g ) =rl n o ( f e ) 心 -_ o 证 明 设 对e ( 1 c c 司作 切 分 运 算 后 所 得图 为g ， 则g ( 2 s ) =f, f f . 由 ” ，理 2 .5 , 。 “ ， 一 立 n o (f f )#= d ， 又 由 “ 到 g ， 除 了 增 加 2 n e = d 个不带自 环的 1 度点 外 ， 图 的 其 它特 征 保持不变，由 引 理2 .1 , n o ( g ) = n o ( g ) , 所以 n o ( g ) = i i n o ( f e ) . 第二章 类树图的亏格多项式 引理 2 _ 7 设氏 同引 理 2 .6 中的g ， 二 e o 二b y ， 对e 作 切分 运 算 后f 对应e # ， 则 1 5 en且石 1 , 司n n ， 并 取 p o ( g n ) 二 p o ( 衅) rj p o ( f ) ( 2 . 1 0 ) ( =王 证明对 九归纳证明. ( 1 ) 当n =1 时， 对。 ， 作 切 分 运 算 有2 个连 通分 支叭 和f 1 ， 由 引 理 2 4 , p o ( g i ) =f o ( m , ) p o ( f) . ( i i ) 设二 =k 时命 题成 立， 当n =k +1 时， 由 引 理2 .4 , p o ( g k + i ) =p o ( g k + e k + i ) p o ( f k + i ) , g k 添加连杆e k + 1 后不影响g k 嵌入曲 面的亏格，只使各嵌入的 数目 同倍 增长，据引理 2 . 6 n o ( 口 * + e k + 1 ) k =n o ( m , + ) 1 1 n o ( f t ) 七 = 1 k =( 2 7 + k ) n o ( 衅) fl n o ( f t ) e =z 二 ( 2 -y + k ) n o ( g k ) , 故 p o ( g k 十。 、 十 ; ) =( 2 y 十k ) p o ( g k ) . 又由归纳假设 p o ( g k ) = p o ( m y ) fl p o ( f c ) , 第二章 类树图的亏格多项式 k+ln脚 所以 p o ( g k + l ) = ( 2 y k ) p o ( 衅)p o ( f e ) 由 推论2 .2 p o ( 衅+ s ) 二 2 : 十 k ) p o ( 衅) ， 所以 七 +1 p o ( g k + i ) 二 p o ( m k + 1 ) fi p o ( f e ) e _1 即。 =k +1 时命题仍成立. 定理 2 . 4 b ( e n ) 个. 设类树图r的每个节点都带有自 环， 带奇数个自 环的点为 r 的 支 掸 树 为t , 令 d 一 臀 寿 间 ， “ 氏 司 n n , t 中 度 点 有r e ( e n ) 个， 且 在图r中 依 次 对 应y , y 2 ， 一 y % 个自 环， 则 ( 1 ) 图r可嵌 人定向曲 面的 最大亏格 、 一 (r ) 一 !)3(r )2卜 叠 ( 2 . 1 1 ) ( 2 ) r的亏格多项式 d , p o (r ) 一 旦 卫 p o (a ?. ) ( 2 1 2 ) 证明( 1 ) 由 题设，g中与 奇数 个自 环 关联的 点为d 个。 对应设 为 u l , u 2 ， 二， u ,j ， 在 构 成 最 大 亏 格 且 所 有 字 母 为 异 号 的 联 树(2 i ) 上， 。 : u 2 ， 二 ， ， 4 t d 处有且仅 有一条自 环所对应的字母在拓扑等价中 可抵消， 根据可定向亏 格 的 概 念 ， * 可 嵌 入 的 定 向 曲 面 的 最 大 亏 格 上 界 减 少 夸 )2 ， 即 得 结 论 . ( 2 ) 对d 用归纳法证明. 当d =1 时，t只有两点一边，由定理 1 2 知结论成立 第二章 类 树图的 亏格多项式 设d 无 时结论 成立， 当d=k 十i 时，r的支撑树t中有r k + ， 个( k + l ) 度点， 设为 。 : ， 、 ， 二、 k + t . 设0 e (1 , r k + i i i n , v , 带咭 十 个 自 环 . 将 与 所 有 点、 关 联 的 连 杆 作 切 分 运 算 得 若 干 个 连 通 分 支 ， 除 m k-k 1 ， 一h 芯 ) 外 ， 分 别 记为卿。 理， ， 即( 其中: =k r k + i + 1 ) ， 使 得衅， 二 ， 殊 1 是含。 ， 的 关联 连 杆 的 分 支 记 r 。 一 ，霆 1 f 9o,， 由 引 理 2 .5 , p , (r o) - p o ( 暇) . r o 中 各 点所带自 环数与r中 对应点所带自 环数相同， 去掉这些自 环后所得 r o 的 支撑树t 0 的 最大度为k ， 且当2 1 时， 运用上述方法继续 对v 3 , . ， 帆+ : 作 还原， 直 到r 0 共 经 过r k 十 : 次 还 原 运 算 得 到凡 p o (r ) 一 p o (r r*一_ p o (m 7 + ,， )k 3 p o (m y + , ) p o (r 0) 、n归 n阔 见 po ( k+ 1p a ( k3)m p o ( 嵘) ) p o ( 嵘 ). 、n月 k+lfl间 即d =k +l 时结论仍成立， 从而原命题成立 当 某 些临= 。 时 上 述 定 理 仍 成 立 ， 而 且丑中 某 些 点 带自 环 ， 某 些 点 则不带自 环是更为一般的倩形.以 下定理应用起来更为方便. 定理 2 .5 r是一个类树图，r的不带自 环的点集中 a度点有 n a 个 ， 带自 环 的 点 有h 个 ， 分 别 对 应m y 11 3 m 1y s2 . . . , m c n ( -y ( qy h:n 十 , 27 。 l , h 门 n ) ， 则 p o ( r ) 二i i ( ( x 一 1 ) !) - 入 2 i p o ( 嵘 )( 2 .1 3 ) 第二章 类 树图的 亏格多项式 图 2 .2 类树图 r 例2 . 1类树图r如图2 .2 ， 应用上述推论可得r的亏格多项式为: p o ( r )=(4 一 : ) ! f o ( m i ) p o ( m 2 ) z p o ( m 3 ) 1 o ( i ) f o ( i ) i o ( m z ) 一 6 2 1 - 4 p o (b 2) 6 p o (b 3) ，3 ! 4 ! 易 p o (b 2) = 6 . 2 . 1 6 . 6 . 6 . 2 4 - 2 0 p o ( b 2 ) 3 p o ( b 3 ) 3 3 1 7 7 6 0 2 ( 2 + 二 ) 3 4 0 ( 1 + 2 x ) 1 0 6 1 6 8 3 2 0 0 - ( 2 + x ) 3 ( 1 + 2 x ) = 1 0 6 1 6 8 3 2 0 0 ( 8 + 2 8 x + 3 0 x 2 + 1 3 ?+ 2 x 4 ) 易 验算上述的各项系数之和与嵌人总数是相等的: p o ( g ) i = = i =8 5 9 9 6 3 3 9 2 0 0 , n o ( g ) =3 ! . 2 ! 6 ! 3 ! 5 ! 4 ! - 4 ! a ! =8 5 9 9 6 3 3 9 2 0 0 , 即p o ( g ) 二 二 : =n o ( g ) . 以上定理中关子亏格多项式的结论同 样适用于不可定向情形， 即对于 全嵌入多项式也成立. 这样，类树图的 全嵌入分布就完全得到了解决.下