（应用数学专业论文）具有n条边n个顶点的连通图的计数.pdf

ab s t 住 昭t _- 一粇钾，.， ab s t 旧c t his川 o reth 阳z ooy e 田 旧 th at脚p h t h eo 叮h asbeend e v e l o p i n g s 吟 ari甄 e 可 ” c i al lya n e r the l970，s，the 即p e ar a n c 七ofl ar g e c o m p ut i ng m a 肠 n om 目e it poss ible toso lvethe p r o b l em of脚atsc 日 e . t b e a p p l i c a t ionofgrap h t h eo ryh asm ad e e 川 e 璐 i vep r o gr e s s inp h y s i c s，che 川 i s t ry， 0 pe ia t 1 o na1 艘 ar c 城。 。 m p u t e r sc i e o c e ， el e c tr o n l c s，i n fo n 刀 a t i o n t h 句rylc y b e m c t l cs ， n e 幻 阳 。 rkt h e o ry，soc过sc i e o c e ， . 。 n o n ” c m ana g e m e n t ， 胡d evenallthc s l lbj e ctfiel ds . at此 5 刃 刀 e t i m e ， 叩h th e o 仃ti gh勿 比 latestom 肚 lymat h e lr la t i cal su bj ec 招 ，访 c 】 u d i ng g l o up t h ，ry， mat ti xt h e o 琳 。 m b i n at o d cs ，al g e b ra，c o m b i n at o ri ai o p t im 故，。 两以 i o na】 眼权 i l n e a l p ro g 别 m lxun g ， 印 m p u t e r sc l e n c e ， numerical an a 】y s is ， p r o b a b i l ityt h e o ry，to poto gy胡 d soon， g 口 p h 山 即 rypl ays ani m 即rtan t ro le inthe o t h e r n 旧 l b e 双 ia 桩 c ais u bj ec ts ， 1 8 8 9 ， c ay1 e y so l v e d the e n u m e iati o n p ro b l em o f the t r e es . 1 9 7 3 ， f. h 肚 别 ry明d e m.p al m e r s 段 a t e dthe e n u m e rat1 on p r o bl e mofthe 1 a be1 目 朋d i r e 日 比 dgr a p hs， the l a 玩】eddi 代 c t e d g m p h s ， 即d the l a be】 edund l r “ 玄 e d c o 刊 国 沁 t edgr a p h s . 1 956，q w.f o rd ， q e. u b l e n beck and凡j. 几d d e l ldi sc u s se dthe 化 l a t io nbet w 既nt b .“卯n e ntiai 9 即e 心访 gfo n c t in nofthe l a 吮 l ed u n d 证以 曰 bl ocksandthe 】 al 笼 l ed 坦 ld i 政t e d connec囚 9 扭 p hs . 2 002 ， y j 诚 s. t 出 必 w a 朗 dt. s hi 妞 如 阳solv 目the enume 旧i on p r o b le mof此 l a be l e d un d ir ec t edc o 助ec t ed a p ha初ththe k c ul . v erti a 绍on咖 b l 倪k . 刀 五 s p a 户 ， 功 a 词y 山 义 璐 “ 月the enu m 。 旧 石 onp r o b lem ofthe 】 a 加 l edu n d i 在 沁 抚 月 connec l edgrap hawil b allthe k 廿 e e s onone bl ock t 七 掀15 ， so l v e d 阮 即u m e ra t l on p r o b le mofcon n e c t e d 粤 a p hs ， 口 c h ofw b i chhas n v 日 rt l ce s 阳 d n edg es . k 叮w o rds:c ycle ， c onne c 抚 幻即 叩 h ， t r 既 ， 阮 e x 卯口 即t i alg e n e ra l i n g fi m c t i on 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电 子版; 在不以 赢利为目 的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 “ % a- “ 20 6 年 ，月对日 经指导教师同意， 本学位论文属于保密，在 本授权书。 年解密后适用 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 2 0 年 ( 最长2 0 年，可少于2 o 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中已 经注明 引 用的内 容外， 本学位论文 的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内 容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 : a 2 翻 年 /，月2 s日 第一章引言 第一章 引言 图论 ( g r a p h t h e o r y )的产生和发展历经了二百多年的历史。从1 9 3 6 年到 1 9 世纪中叶，这时的图论处于萌芽阶段，多数问题是围绕着游戏产生的，最具 有代表性的 工 作是 著名的 瑞 士数学家l . e u l e r 于1 7 3 6 年的k - o n i n g s b e r g 七桥 问 题， 他的 那篇论文认为图 论历史上第一篇论文。 从1 9 世纪中叶到1 9 3 6 ， 这个 时期中图 论问题大量出 现， 如四 色问 题( 1 8 5 2 年) 和h a m i l t o n 问 题( 1 8 5 6 年)， 同时出 现了以图为工具去解决其他领域中的一些问题的成果，最具有代表性的 i作是k i r c h h o f f ( 1 8 4 7 年 ) 和c a y l e y ( 1 8 5 7 年) 分别用树的概念去研究电网络 方程组问题和有机化合物的分子结构问题。1 9 3 6 年以后由 于生产管理、军事、 交通运输、 计算机和通信网 络等方面许多 离散 性问 题的出 现， 大大促进了图 论 的发展。 进入7 0 年代以 后， 特别是大型电 子计算机的出现， 使大规模问题的求解成 为可能，图的理论及其在物理、化学、运筹学、计算机科学、电子学、 信息论、 控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用 得到了广泛发展。同时，图论与许多数学学科密切相关，包括群论、矩阵论、 组合学、代数、 组合优化、 运筹学、线性规划、 计算机科学、 数值分析、 概率 论、拓扑学等，彼此之间相互渗透，相互促进，图论对于其它数学学科的发展 起着重要的作用。 1 8 8 9 年， c a y l e y ( 1 1 ) 解决t树的计数问 题, 1 9 7 3 年f . h a r a r y . 和e m . p a l m e r ( 3 )阐述了 关于标号无向图和标号有向图以及标号无向连通图的计数问 题。 1 9 5 6 年， g . w . f o r d 和g . e . u h l e n b e c k( 2 )以 及r . j . r i d d e l l 讨论7标号 无向 块 ( 2 连通图) 的指数型生成函数与标号连通无向图的指数型生成函数之间 的关系， 2 0 0 2 年， y . j i n 和s . t a z a w a 以 及t . s h i r a k u r a( 4 )讨论t所有 的k 个割点均在一个块上的标号连通无向图的 计数问 题。 本人基于上面学者的 研究成果，已 经有选择的阅读了文献 1 - 6 ， 运用组合理论和图的计数理论方 法， 解决了 具有k 个树， 并且这些树均分布在一个圈上的无向标号连通图的计数 问 题。 即解决了 具有n条边n个顶点的 连通图的计数问 题。 第二章 图的基本定 义及其有关定理 第二章 图的基本定义及其有关定理 这一章主要介绍图的基本概念和一些图的计数问题 定义2 . 1图是由一些点及一些点之间的连线( 不带箭头或带箭头) 所组成。 记为g= ( v , 习， 其中v 表示 顶点集合，e 表示边集合。 简单图:如果图g没有多重边 ( 也没有环) ， 则称g为简单图。 完全图:设g为n ( n - 1 ) 个顶点的简单图， 若g中每个顶点 均与其余n - 1 个 顶点相 邻， 则 称g为” 阶 完 全图， 记作k . . 1 9 7 3 年f . h a r a r y . 和e m . p a l m e r ( 3 1 ) 阐 述了 关于 标号 无向 图 的 计 数问 题。 有关标号无向图的计数问题，可表述如下一些定理: f f ， 、 、 定 理 “ ” 个 顶 点 ， “ 条 边 的 图 的 个 数 为 l 2 ) 1 . l k) 证明 : p 点中 任取两 点 均可 产生 一 条 边， 从这些边中选出k 条边的种数有 所 以 共 “ p 2 ) 条 边 可 供 选 择 于 是 ， 、一少 、飞.2 pzk 矛!、 /tles月.、 定 理 : . : 点 的 个 数 为 。 的 标 号 图 的 个 数 为 2 () . 证 明 : 设 吼 ( x ) 表 示 p 个 顶 点 标 号 图 的 生 成 函 数 ， 其 中 气(x)中 x , 的 系 数 为 具 有 p 个 点 k 条 边 的 标 号 图 的 个 数 ， 则 当 v ( g ) 卜 p 时 ， p 个 点 中 任 取 两 点 均 可 产 生 一 条 边 ， 所 以 共 有 p ) 条 边 可 供 选 择 。 于 是 ， 从 这 些 边 中 选 出 * 条 边 的 种 数 一 - - - ， - 一 瞬少 (f)艺脚 一一 g , ( x ) 2(p) 一 。 + 。 闭 k) 令 : = 1 ， 正 是 我 们 需 要 的p 个 点 的 标 号 图 的 个 数 g , ， 于 是 第二章 图的基本定义及其有关定理 g p = g p (1 ) 一 2 (g) 定 义2 . 2 道( 途 径) : 有 限 非 空 点 边 交 错 序 列tiy = v o e iv ie 2 . . . e k v k ， 使 e , 的 两 个 端 点 为 v i- ,一 1 5 i 5 k ， 或 记 为w = y p y w 2 - v k ， 称w 为 y o 到、 的 一 条 途 径， 顶 点 y o 和、 分别 称为w 的 起点 和终点。 整数k 为w 的 长。 注意: 在途径中 ， 点 或 边可 以重复。 迹:边不重复的途径 路:点不重复的迹，即点和边都不重复的途径. 定义2 . 3 连通: 设u , v 是图g中的两 个 顶点， 若u , v 之间 存在一条路， 则称u , v 是连通的。 图的连通: 若图g中任意两点均有路 ( 任意两点都是连通的) ， 则称g是连 通的。否则为不连通。 连通分支:在顶点集v上定义一个关系r，称为连通关系。 x r y 22， 2 3 2 3 2 3 - v2 3 设凡( x ) 表示在根的周围 恰好含有n 个块的有根标号连通图的指数生成函 数。 显 然，凡= x ， 且 r (x ) = 艺 k ( x ) 则 a(x) 表 示 根 的 周 围 只 含 一 个 块 且 根 节 点 未 标 号 的 连 通 图 的 指 数 生 成 函 数 。 x 例如，r , ( x ) 不 _ x 1_ x = x十-+l吕十. 。 2 ! 3 1 * z z 1 2 1 2 2 1 1 2 由此可知，具有n 个根 ( 根不标号)连通图的指数生成函数为 不妨设f r , (x ) 丫.j ( 无( x ) 丫 、 x j 刀 ， 其中a表 示m 个点 放在n 个根不标号， 其它点 标 1 0 第三章 k 个割点均在一个块上的标号 连通图的 指数型生成函数 号，无序的n 元序对图形中的图形个数。 将这n 个根看成一个点， 且对这个根点 进行标号， 则成为在根的周围 恰好含 有” 个块的有根标号连通图的指数生成函数 : .凡( x ) = x r ( x ) f p i ( x ) 1 = x e p5 1 tx) 黔一川钊一? 。、-.一。r一一 廿仁卜、一了!、-， 下面我 们 设 法用b ( x ) 和r ( x ) 来表示凡 ( x ) 。 首 先 ， 生 成 函 数 r (x) t -1x 的 x 0 的 系 数 表 示 具 有 ， + * 一 1 个 顶 点 p. ，且其中包 含k - 1 个未标号的根的k - 1 个连通图的计数。( 注意:( k - 1 ) 个图中的每一个 图中都是根节点未标号的有根连通图。 )而 k b , ( r (x ) 丫 “ . x k 二 二 . “ x j k ! b t ( r ( x ) 尸 ( k 一 1 ) ! 表示添加一个点，且与所给的k - 1 个根一起构成一个块 ( 此块以 添加的点 为根，且所有的点都进行了 标号)的有根连通图的计数. 因 此 ， 由 r , ( x ) 的 定 义 可 知 ， r , ( x ) = 二 艺b , ( r (x ) )一 _ ( k 一 1 ) ! x b ( r ( x ) ) 。 * (。 = 二 .c (x), r (x)= x - p w l1 x 。 : .。 ，(。 = 一 a (x)lx 可得 c (x ) = e x p 1 咧 = e x p b (r (x ) = e x p i n (x c (x ) l 万) l d g c ( x ) = b ( x c ( x ) ) 第三章 k 个割点均在一个块上的标号 连通图的指数型生成函数 2 0 0 2 年， y . j i n 和s . t a z a w a 以 及t . s h i r a k u r a( 4 ) 讨论t 所有的k 个割点均在一个块上的标号 连通无向图的计 数问题，表述如下一些定理: 定理 3 . 4具有 n个块， k个割点在一个块上的连通图的指数型生成函数 凡 r ( x ) 和 标 号 块 的 指 数 型 生 成 函 数b ( x ) 之 间 的 关 系 如 下 : b , ( x ) = s ( n 一 l , k ) x k b k ( x ) . ( n ( x ) -, ( ” 一 1 ) ! 其中 证明 o _k ) ( x ) 表 示关 于x 的k 阶导 数。 凡 ， : p 阶 有 根 标 号 块 的 个 数 。 凡: p 阶 标 号 块 的 个 数 显 然 ， 气= p . 凡。 .a(x) = 郭 ， v. b ,tx)= b.v x tp !v=落 p bv釜 落 、 蒜 b tx) b , ( x ) _ ， 1 _ 、。 n b , ( x ) , f , x 0n l r .% e h，二_ . ， 。*， ， ，*、。、 一 弋 丁 一一l l v -t 下 n j fr c n c i j ( ri y l l f 3 t ! r l 3 t t i k i f t t 7， a不p里 标号块的个数。 如果将s 个这样的图与一个割点上含有s 个块的标号图( 割点本身没有标号) 对应起来， 那么一个割点上含有s 个无序块的生成函数为 令 l ( t x ) s , ! ( b ( x ) 广 ( b ( x ) 广 s z ! s , ! i 气 , 毛十 冲电州刁 则a k ， 表 示 含 有k 个 有 根( 根 不 标 号) 连 通图 的 具有二 + k 个点的 有 序 组图 的 个 . 其中 ，k 个有 根( 根 不 标号) 连通图 分 别 包 含3 1 个块， 个 块， ( s , + s 2 + - - - s , = n - 1 ) 圈 b,aer 丫 ) :新 添 加 ， 一 个 “ ， “ 这 ” “ ” 个 根 构 成 一 个 块 ， s t 个 并将 数块 ， 所 有点( 共有m + p 个点) 用1 , 2 , 二 m + p 重 新标号的， 具有n 个块，k 个割点， 并且所有k 个割点都在一个块上的连通图的个数。 第三章 k 个割点 均在一个块上的标号 连通图的指数型生成函数 : p 个中 取k 个作为根 、.户矛 pk m+p p) :二 ， 个 点 中 “ ， 个 “ 放 在 块 上 。 2忆.、了.健、 一 b, (。 一 级p 、 ， m + p ) x00 (k )b0ak( p ) (m + p )! - i (p )bvj ak,(x )(v (x) r ( x ) 的 前+项为 r (x) = 子 + 15 箭 + 2 22 普 + 3660 箭 + 68296 哥 + 1436 568 箭 + 337 79340 岳 + 8 8 0 10 7 84 0 x u + -.-10 ! 当p = 3 时， 3 个顶点3 条边的标号连通图只含有一个圈。 第四章 具有n 条边n 个顶点的连通图的计数 当p = 4 时， 4 个顶点4 条边的标号连通图分两种情况: 4 个顶点4 条边在一个圈上不带树。 ，.j4 ，.1叹甘 3 个顶点在一个圈上带一个树。 1丫2 3丫. 1丫。 一罕. 致谢 致谢 本文 是在金老师的悉心指导下完成的. 论文完成之际，首先向 金老师 表示 最衷心的 感谢! 感谢金老师给予我的教育，感谢对我的关怀和理解，更要感谢 金老师 在人文修养上对我的榜样作用. 感谢南开大学数学科学院的各位老师，老师在学业上的谆谆教导，令我受 益匪 浅.我 所取得的 每一份进步， 都凝聚 着金老师和其他老师 们的汗 水， 衷心 感谢你们. 感谢南 开大学同班支持、 帮助我的同 学. 最后，感谢南开大学! 在人文教育浓厚的南开大学度过的学习 时光， 令我 终生难忘. 祝愿南开大学的明天更加辉煌灿烂! 参考文献 参考文献 1 j a t h e o r e m o n tr e e s , q u a r t . j . m a t h . o x f o r d s e c 2 3 , 3 7 6 - 3 7 8 ( 1 8 8 9 ) ; c o l l e c t e d p a p e r s , c a m b r i d g e l 3 . 2 6 - 2 8 ( 1 8 9 7 ) . 2 g ,1 . f o r d a n d g e . u h l e