（基础数学专业论文）具有k个割点的标号有向连通图的计数.pdf

最终解决了所有割点都在一个块上的标号有向 连通图的计数问题。 关键词: 标号有向 连通图 指数型生成函数 第二类s t i r l i n g 数 割点 计数 ab s tra c t ab s t r a c t g r a p h t h e o ry i s a b r a n c h o f m a t h e m a t i c s , s t u d y i n g t h e re l a t i o n o f t h e g r a p h i c c o m b i n a t i o n a n d s t r u c t u r e , a n d i t h a s a h i s t o ry o f m o re t h a n 2 0 0 y e a r s . t h e g r a p h s s t u d i e d i n g r a p h t h e o ry a r e o n e s w h i c h a re c o m p o s e d 妙 a c e r t a i n n u m b e r o f g i v e n p o i n t s a n d e d g e s w h i c h a r e c o n n e c t e d b y u s i n g a n a b s t r a c t f o r m t o e x p r e s s s o m e s p e c i f i c o b j e c t s a n d s o m e s p e c i f i e d r e l a t i o n e x i s t i n g o r n o t e x i s t i n g a m o n g t h e s e o b j e c t s . b e s i d e s , t h i s k i n d o f g r a p h s a r e t h e t y p i c a l r e p re s e n t a t i v e s o f a b s t r a c t a n d d i r e c t m e t h o d a d o p t e d i n m a t h t h i n k i n g , a k i n d o f m o re c o m p re h e n s i v e , a n d s y s t e m a t i c d a t a s tr u c t u r e , a n i d e a l m a t h e m a t i c a l m o d e l u s e d t o re s o l v e m a n y p r a c t i c a l p ro b l e m s . a n d t h i s k i n d o f g r a p h s i s e a s y t o b e s t o r e d i n c o m p u t e r s a n d a n a l y z e d a n d c a l c u l a t e d . s o g r a p h t h e o ry d e v e l o p s r a p i d l y i n re c e n t y e a r s , a n d i t h a s b e e n t h e m o s t a c t i v e b r a n c h i n t h e f i e l d o f c o m b i n a t i o n ma t h . i n a d d i t i o n , i t s c o n c l u s i o n a n d t e c h n i q u e s h a v e b e e n t r a n s f o r m e d w i d e l y i n t o v a r i o u s fi e l d s s t u d y . s u c h a s c o m p u t e r s c i e n c e , e l e c t r o n i c s , n e t w o r k山 e o ry , i n f o r m a t i o n t h e o ry , c y b e rn e t i c s , o p e r a t i o n a l re s e a r c h , , m a n a g e m e n t s c i e n c e a n d s o c i a l s c i e n c e . i n p e o p l e s s o c i a l p r a c t i c e , l o t s o f t h i n g s o r o b j e c t s i n r e a l w o r l d c a n b e s h o w e d t h e i r t o p o l o g i c a l s t r u c t u r e b y g r a p h s . t h e s t u d y o f p r a c t i c a l p r o b l e m s i s t r a n s f o r m e d i n t o t h e s t u d y o f g r a p h s ; t h e a n a l y s i s a n d j u d g m e n t a re m a d e 妙 u s i n g t h e r e l e v a n t c o n c l u s i o n a b o u t g r a p h s . s o g r a p h t h e o ry h a s b e c o m e a k i n d o f e ff e c t iv e t o o l t o r e s o l v e m a n y p r o b l e m s i n d i ff e re n t fi e l d s , s u c h a s n a t u r a l s c i e n c e , e n g i n e e r i n g t e c h n o l o g y , s o c i a l s c i e n c e , b i o l o g i c a l t e c h n o lo g y , e c o n o m i c a l a n d m i l i t a ry a r e a s , a n d t h i s t h e o ry i s p re f e r r e d m o r e a n d m o re b y m a t h e m a t i c i a n s a n d p r a c t i c a l w o r k e r s . e n u m e r a t i o n o f g r a p h s i s a s o r t o f im p o r ta n t q u e s t i o n s i n g r a p h t h e o ry , e s p e c i a l l y t h e w i d e r a n d w i d e r u s e o f e n u m e r a t i o n o f o r i e n t e d g r a p h s i n t h e s t u d y n e t w o r k fl o w t h e o ry , c i r c u i t n e t w o r k a n d c o m p u t e r s c i e n c e . k n o w i n g t h e c a l c u l a t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s w i t h k c u t v e rt i c e s m a y d e c r e a s e a l o t o f u n n e c e s s a ry b l i n d n e s s i n p r a c t i c a l c a l c u l a t i o n . a c c o r d i n g t o t h e b a s i c c o n c e p t o f g r a p h t h e o ry , t h e b a s ic n a t u r e o f g r a p h e n u m e r a t i o n a n d l e m m a o f l a b e l e d e n u m e r a t i o n a n d u s i n g e n u m e r a t i o n o f l a b e l e d ab 滋口d . . . . . . . . . . . . 目. . o r i e n t e d g r a p h s , t h i s e s s a y fi r s t d i s c u s s e d t h e r e l a t i o n s h i p b e t w e e n e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d g r a p h s a n d e x p o n e n t i a l g e n e r a t i n g fi m c t i o n o f l a b e le d o r i e n t e d c o n n e c t e d g r a p h s a n d i n t h e o ry , g a v e a s t r i c t t e s t i m o n y t o c o n c l u s i o n a n d fi g u r e d o u t t h e fi r s t n i n e t e r m o f e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s . s o t h e e n u m e r a t i o n q u e s t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s i s re s o l v e d . o n t h e b a s i s , t h e e s s a y h a s a f u r th e r s t u d y o n t h e re l a t i o n s h i p b e t w e e n e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s a n d e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d b l o c k s a n d t e s t i fi e d s t r i c t l y o n t h e c o n c l u s i o n a c c o r d i n g t o t h e t h e o ry , c a l c u l a t e d t h e fi r s t e i g h t t e r m o f e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d g r a p h s , 山 u s r e s o lv i n g t h e q u e s t i o n o f e n u m e r a t i o n o f l a b e l e d o r i e n t e d b l o c k s . a t l a s t , b y i n t r o d u c i n g t h e s e c o n d s o rt o f s t i r l 吨 n u m b e r s , u s i n g t h e c o m b i n a t i o n m e a n i n g o f t h e s e c o n d s o rt o f s t i r l i n g n u m b e r s a n d t h e g i v e n c o n c l u s i o n , t h i s e s s a y s t u d i e d t h e re l a t i o n s h i p b e t w e e n e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d b l o c k s a n d e x p o n e n t i a l g e n e r a t in g f u n c t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s w i t h o n l y o n e c u t v e r t i c e s , t h u s re s o l v i n g t h e q u e s t i o n o f e n u m e r a t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s w i t h o n l y o n e c u t v e r t i c e s , i n a d d it i o n t o t h i s , fi n d o u t t h e re l a t i o n s h i p b e t w e e n e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d b l o c k s a n d e x p o n e n t i a l g e n e r a t i n g f u n c t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s t h a t a l l o f c u t v e r t i c e s a r e i n s a m e b l o c k . a n d g i v e a s t r i c t t e s t i m o n y . s o t h e q u e s t i o n o f e n u m e r a t i o n o f l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s t h a t a l l o f c u t v e r t i c e s a r e i n s a m e b l o c k i s fi n a l l y re s o l v e d . k e y w o r d s : l a b e l e d o r i e n t e d c o n n e c t e d g r a p h s , e x p o n e n t i a l g e n e r a t i n g f u n c t i o n , t h e s e c o n d s o r t o f s t i r l i n g n u mb e r s , c u t v e r t e x , e n u m e r a t i o n 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本:学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版; 在不以赢利为目的的前 提下，学校可以 适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 体 ac 0 b 年 月月l s 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 一一 - 一一 - - 一一 一, t. 1 内部 5 年 ( 最长5 年，可少于5 年) 秘密*1 0 年 ( 最长1 0 年，可少于1 0 年) 机密2 0 年 ( 最长2 0 年，可少于2 0 年) _、. . _ _ _尹; 广. 、! 一 益 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集 体， 均已 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 : r, a a-6年 i l月2 s日 第一章引言 图论是研究图的组合关系及结构的一个数学分支，其发展己 有 2 0 0多年的 历史。图论中所研究的图是由若干给定的点及连接两点的边所构成的图形，这 种图形是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或 不具有某种特定关系的一个数学系统，是数学中经常采用的抽象直观思维方法 的典型代表，是一种更全面，更系统的数据结构，是解决许多实际问题的一种 理想的数学模型，便于计算机存储和分析计算。因此近年来图论发展迅速，目 前已成为组合数学领域最活跃的分支，其结论和技巧已经广泛移植到计算机科 学，电子学，网络理论，信息论，控制论，运筹学，管理科学，社会科学等众 多领域的研究中。在人们的社会实践中，现实世界中的许多事物或对象都能用 图表示其拓扑结构， 把实际问题的研究转化为图的研究，利用图的相关结论对 这些问题做出分析和判断。因此目 前图论己成为解决自 然科学，工程技术，社 会科学，生物技术以及经济，军事等领域中许多问题的有力工具，越来越受到 数学家和实际工作者的喜爱。图的计数是图论中一类重要问题，尤其是有向图 的计数在网络流理论， 电路网络以及计算机科学的研究中有着越来越广泛的应 用。 了解具有k 个割点的标号有向连通图的计数， 在实际计算中可以减少许多不 必要的盲目性。 f . h a r a r y 和e . m . p a l m e r( 幻) 阐述了 关 于标号无向图 和标号有向图的 计数问 题， r . j . r i d d e l l ( 6 7 )讨论了标号无向 连通图的指数型生成函数与标 号无向图的指数型生成函数之间的关系， g . w . f o r d 和g . e . u h l e n b e c k ( i d 以 及r . j . r i d d e l l 讨论了 标号无向 块的指数型生成函数与标号无向 连通图的指 数型生成函数之间的关系，y . j i n ( 3 7 )讨论了具有唯一一个割点的标号无向 连通图的指数型生成函数与标号无向块的指数型生成函数之间的关系，y . j i n 和s . t a z a w a 以 及t . s h i r a k u r a ( 4 7 ) 讨论了所有的k 个割点均在一个块上的 标号无向 连通图的计数问 题， y . j i n 和c . j i n ( 7 1 ) 讨论了 具有割点的标号e u l e r 图的计数问题。 由于具有k 个割点的标号有向连通图的计数比较复杂， 因此在本文中， 我们 主要讨论所有割点都在一个块上的标号有向连通图的计数问题，至于一般情况， 做为今后继续研究的课题。 第二章 基本概念及其性质 第二章 基本概念及其性质 第一节 图的基本概念 定 义 2 . 1 设 v 一 v i, v z , . 为 非 空 集 合 ， e 一 伽v j v +av i 。 弓 是 v 中 不 同 元 的 无 序 二 元 对的 一 个 集 合， 则 称 有 序 集 对( v , e ) 为 简 单 图 ， 记 为g = ( v , 习或 g 一 ( v ( g ) , e ( g ) ) 。 称 v ( g ) 为 顶 点 集 ， v 中 元 称 为 g 的 顶 点 ， 顶 点 数 记 为 回或 v ( g ) ; 称e ( g ) 为边集，e 中 元称为g 的 边， 边数记为囚或e ( g ) 设 x = ( u , v ) e e ， 则 称 u , ， 为 x 的 端 点 ， 并 称 u , ， 是 相 邻 ， 又 称x 是 联 结 二 和 ， 的 。 ， 点 图 : g = ( v , e ) ， 其 中 。 一 卜 、 ， ， 幼， e 二 伽, v j ) iv v , e v v , 叻 ( 夕 ， ; ) 图 显然有: : g = ( v , e ) ， 其 中 个p 囚= 9 。 二 (g )s v(2 ) i 例 2 . 1 设 v = v l , v l , v , , v 4 , v 7 j ， e - l ( v h v 2 j , lv l, y 3 ) t v 2 v 3 j j l2 , v 4 ) t v 3 , v 4 1 l v 3 , v 5 1 l v 0 a v 5 ) ) ， 则g= ( v , e ) 是一个图。 通常用平面上的一些点分别表示图的顶点，用连接相应两个顶点而不经过 其它顶点的直线 ( 或曲线)来表示图的边。 例如( a ) , ( b ) 分别给出了例2 . 1 中图go 巧 v 巧砂 矛.、 凡 图 2 . 1 第二章基本概念及其性质 定 义2 . 2图 g 中 k 条 边 的 序 列 v . , v i ( v i , v 2 ; 一 v k - 1 r v k 称 为 连 接v o 到 、 的 一 条 长为k 的 路。 它 常 简 单 地用 顶点 的 序列v o v i v 2 、 、 、 来 表 示. 若v o # v k ， 则 称 路v o v i v 2 v k - 1、 为开 路。 若v o = v k ， 则 称 路v o v t v 2 . . . y k - i、 为回 路 若 开 路v o v i v z . . . v k - i v k 中， 所 有 顶点 互不 相同( 此时 所有 边也 互 不相同 ) ， 则称 此开路为真路. 在 图 g 中 ， 若 存 在 一 条 路 连 接 v 和 v i ， 则 称 顶 点 v , 和 v i 是 连 接 的 。 定义 2 . 3在图g中，若任意两个不同的顶点都是连接的，则称g为连通图， 否则， 称g为非连通图。仅有一个孤立顶点的图定义它为连通图。 例2 . 2 下图 中 ( a ) 为 连 通图 ， ( 句为 非 连 通图 。 ( a )( b ) 图 2 . 2 定 义 2 . 4 设 图 g = ( v ( g ) , e ( g ) ) ， 图 h = ( v ( h ) , e ( h ) ) ( )若v ( h ) c_ v ( g ) , e ( h ) g v ( g ) 则称h = ( v ( h ) , e ( h ) ) 是图 g = ( v ( g ) , e ( g ) ) 的 子 图 . ( 2 )如 果 v ( h ) 二 v ( g ) , e ( h ) c v ( g ) 则 称 h = ( v ( h ) , e ( h ) ) 是 图 第二章基本概念及其性质 ( 3 ) g = ( v ( g ) , e ( g ) ) 的 真 子 图 。 ( 4 )如果v ( h ) 一 。 ( g ) , e ( h ) s v ( g ) 则 称h = ( v ( h ) , e ( h ) ) 是图 g = ( v ( g ) , e ( g ) ) 的 生 成 子 图 。 定 义2 . 5 若 图 g 的 顶 点 集v ( g ) 可 划 分 为 若 干 非 空 子 集k ， k ， ， k ， 使 得 两 顶点 属 于 同 一 子 集 当 且 仅当 它 们 在g中 连 通， 则 称 每 个子图 g ( v , ) 为 图 g 的 一 个 连 通 分 支。 = 1 , 2 , , , 劝 则由定义可知:( 1 )图g的连通分支是g的一个极大连通子图。 ( 2 )图g连通当且仅当k=1. 定 义2 . 6 设 - ( g ) 为 图 g 的 连 通 分 支， ， 是g 的 顶 点 ， 如 果 w ( g 一 v ) w ( g ) 则 称， 是 图 g 的 割 点 。 其中 ， g - ， 是 指 在图 g 中 掉【 v 和 与 v 的 关 联 的 所 有 边 定 理2 . 1 如 果 点 ， 是图 g 的 一 个 割点， 则 边 集e ( g ) 可 划 分为 两 个 非 空 子 集 耳 和凡， 使 得g ( e , ) 和g ( e z ) 恰 好 有 一 个 公 共 顶 点， 。 推论2 . 2对连通图g，顶点v 是g的割点当且仅当g- v 不连通。 例2 . 3下图 中、 r v 6 均是 割点。、 第二章基本概念及其性质 定义2 . 7对连通图g中的任意点v ， 若去掉顶点v 时， 其连通分支的个数不 起变化，则称图g为块或2 连通图。即没有割点的连通图称为块或2 连通图。 定 义2 . 8 有向 图d 是 一 个 有 序 二 元 组( v , x ) ， 其中 顶点 集v 是 一 有限 非 空 集 合 ， 边 集 一 ( u , v ) l u , v e 玛是 v 中 不 同 元 素 的 有 序 二 元 对 构 成 的 集 合 设 x = (u , v ) e x， 称x 为 d 中 的 有向 边， 称u 和v 相 邻， 称x 和u 相 互 关 联。 点: 的 出 度 是 以 “ 作 为 第 一 个 顶 点 的 有 向 边 的 个 数 ， 即 为 w l w e v ,( u , w ) e x ， 点 二 的 入 度 是 以 二 作 为 第 二 个 顶 点 的 有 向 边 的 个 数 ， 即 为 w l w e v , ( w , 二 ) e x 小 例2 . 4设d = ( v , 刀， v = v v z , v 3 , v 4 卜 x 一 v l v i l v l v 4 / v 3 v 2 v 3 s v t v 7 r v 4 ( v ( 3 . 8 ) 其 中 ， c , 为p 点 标 号 有 向 连 通 图 的 个 数 。 由 标 号 计 数 引 理 可 知 ， c ( x ) c ( x ) 为 标 号 有向 连 通 二 元 有 序 组 合图 的 指 数 型 第三章 标号有向块的计数 生成函数。 因此指数型生成函数c ( x )c (x ) 中 x p 前 的 系 数 恰 为 含 有 两 个 连 通 分 支 2 ! p ! 的p 点标号有向图的个数，从而c (x ) 中 x 0 前 的 系 数 恰 为 含 有 m . p. n 个连通分支的 p 点 标号 有向图的 个数。 于是有 。 ， 、矛c ( x ) ll x ) =乙一 ， 二 一 . , n! ( 3 . 9 ) 其中d ( x ) 为 标 号 有向 图 的 指 数 型 生 成 函 数 扩-川 .艺间 e x= 所以 d ( x ) 一 全 掣 一 掣 = e c (=) - 1 于 是 ， 我 们 找 到 t d ( x ) 与 c ( x ) 的 联 系 定 理3 . 5 标 号 有向 图 的 指 数 型 生 成 函 数d ( x ) 与 标 号 有向 连 通图 的 指 数型 生 成函 数c ( x ) 有 如 下 关 系: 1 + d ( 小 e c (r ) ( 3 . 1 0 ) 利 用 此 定 理 可 算出 c ( x ) 的 前9 项: c (x ) 一3 x 2 + 54 x , + 3 83 4 x 4 + 102 7 0 8 0 x- + 10 6 7 3 0 84 8 8 x 6-2 ! 3! 4 ! 5! 6 ! + 4 3 9 0 4 8 0 1 9 3 9 0 4 x , + 7! 7 2 0 2 2 3 4 6 3 8 8 1 8 1 5 8 4 8 ! 4 7 2 1 7 1 7 6 4 3 2 4 9 2 5 4 7 5 1 3 6 0 十一 9 鱼 x 9 十 例如:2 点标号有向连通图的个数为3 0 1 2 .，- . - ，. 1 2 .心 -. 1 2 气二- 图3 . 2 第三章标号有向块的计数 第三节 标号有向块的计数 设标号有向块的指数型生成函数为: . . v b ( x ) - y b p ; t 声 ， . n ) 例 如 : 集 合a = 1 , 2 , 3 , 4 有7 个2 分 划， 它 们 是 1 , 2 , 3 , 4 = 毛 1 ) u 2 , 3 , 4 卜( 2 ) u 1 , 3 , 4 = ( 3 ) u ( i , 2 , 4 卜( 4 ) u 1 , 2 , 3 二 1 , 2 ) u ( 3 , 4 卜笼 1 , 3 ) u ( 2 , 4 ) = 1 1 , 4 ) u 2 , 3 ) 故 s ( 4 , 2 ) = 7 . 4 . 1 . 2第 二 类s ti r lin g 数s ( n ,k ) 的 组 合 意 义 1 . 先 把n 个 球 构 成 的 集 合a = + x x 划 分 成k 个 非 空 子 集 第四章所有割点都在一个块上的标号有向连通图的计数 a , a 2 . . . . . . k 即 a = 鸿u 人u . . u 人 然 后 ， 将 每 个a , ( 1 5 i 5 劝放 入 一 个 盒 子 里 ， 构 成 一 个 没 有 空 盒 的 分 配 方 案 。 这 里k 个 盒 子 是 完 全 相 同 的 。 则人 ， 人 ， ， 人是a 的 一 个k 分 划， 其 方 案 数s ( n , k ) n 2 . 飞 一 * !s ( n ,k i n k ) 从而有 引 理 4 . 1 又( ” ) 一 * !s ( n ,k ) + h n x - - 4 t . n l n l n 2 二 ， n k j ( 7- 1 2 ;-习 ( 4 . 1 ) 其中k 和从 八， 、都 是 整数， 且 有k )2 3 . 把n 个完全不同 的 球放入k 个不同 的 盒子e l , e 2 , e k ，并且 每个盒子是非 空 的 放 法 ， 可 看 成 多 重 集 合s = , o . e , o o . e 2 , . . . , c o . e k 的 n 排 列 中 每 个 e , ( 1 5 i :5 k ) 至少出 现一次的 排列aa。 所 以a , = k !s ( n , k ) 而 排 列 数 序t a n 的 指 数 型 生 成函 数 为 : 第四章所有割点都在一个块上的标号有向连通图的计数 、.少 刃.二 一 ex 了j.飞， 一一 幼.!产 x x 2 一 + 1 ! 2 ! 口lee吸、， = 、.少 x 了.、 关 )(一 ， e(k-l) 几。， .艺闭 - 一 ky (k ) ( - 1 了 i1 ( k - iy x kd a y ( 4 . 2 ) 了一川 一!tlj 功夕 一 虎 、.!了 k。于 /!1、 .艺词 一- 所以 凡 = k- (一 叮 ( n z k ) ( 4 . 3 ) 协夕 -口舀 k 矛.、 、ij.j k.了