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

ab s t r a c t i n t h i s p a p e r fi r s t s o m e b a s i c c o n c e p t s o f g r a p h t h e o ry a n d g e n e r a t i n g f u n c t i o n s a r e i n t r o d u c e d . o n t h e b a s i s o f t h i s , t h e n u m b e r s o f t h e l a b e l e d d i g r a p h s w i t h p v e r t e x a r e s t u d i e d , o f w h i c h t h e 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 d ( x ) i s g a i n e d . f u r t h e r m o r e , th e r e l a t i o n s b e t w e e n d ( x ) a n d t h e g e n e r a t i n g fu n c t i o n c ( x ) o f a l a b e l e d c o n n e c t e d d i g r a p h a r e s t u d i e d , 山。 c o u n t s o f c o n n e c t e d l a b e l e d a r e o b t a i n e d . i t i s a l s o s t u d i e d t h a t t h e r e la t i o n s b e t w e e n t h e 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 c ( x ) o f a c o n n e c t e d l a b e l e d d i g r 即h a n d t h e 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 b ( x ) o f a l a b e l e d d i r e c t e d b l o c k , m a k i n g u s e o f t h e r e l a t i o n s , t h e c o u n t s o f l a b e l e d d i re c t e d b l o c k s a re g a i n e d . a t l a s t , i t i s s t u d i e d t h a t t h e rel a t i o n s b e t w e e n t h e 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 q . ( x ) o f a c o n n e c t e d l a b e l e d d i g r a p h , w h i c h h a s o n l y o n e c u t p o i n t s o u r c e a n d e x a c t l y n l a b e l e d d i r e c t e d b l o c k s a r o u n d t h e c u t p o i n t s o u r c e , a n d t h e e x p o n e n t i a l g e n e r a t 吨 f u n c t i o n b ( x ) o f a l a b e l e d d i r e c t e d b l o c k . i t i s a l s o o b t a i n e d t h a t t h e re l a t i o n s b e t w e e n t h e 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 q n ( x ) o f a c o n n e c t e d l a b e l e d d i g r a p h w i t h o n l y o n e c u t v e r t e x a n d t h e 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 b ( x ) o f a l a b e l e d d i r e c t e d b l o c k , 勿t h e s e re l a t i o n s , i t i s s o l v e d t h a t t h e c o u n t p r o b l e m s o f t h e c o n n e c t e d l a b e l e d d i g r a p h s w i t h o n l y o n e c u t v e r t e x s o u r c e . k e y w o r d s : l a b e le d c o n n e c t e d d i g r a p he x p o n e n t i a l f u n c t i o n c u t v e rt e x 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于 收集、 保存、 使用学位论文的 规定， 同意如下各项内 容: 按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电 子版，并采用影印、缩印、 扫描、 数字 化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务: 学校有权按有关规定向国家有 关部门 或者机构送交论文的复印件和电 子版; 在不以赢利为口 的的 前 提下， 学校可以 适当复 制论文的部分或全部内容用于学术活动。 学位论文作者签名: 、 _ 粼 /y?-2 0 )7 * 一 年 月 哆 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月 各密级的最长保密年限及书写格式规定如下: 内 部 石 年长 最长苏 年头可 少录5 年) e ;kk * ic - 机密六z c年 斗 1呼 , 最 沃 0年，渺 滩 爷可 少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文，是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担 。 学 位 论 文 作 者 签 名 国 知 年, 月 砂 日 第一章引言 第一章引言 图论是研究图的 组合关系及结构的一个数学分支，其发展已 有2 0 0 多年的 历史。图论中所研究的图是由若干给定的点及连接两点的边所构成的图形，这 种图形是以一种揭象的形式来表达一些确定的对象，以及这些对象之间具有或 不具有某种特定关系的一个数学系统，是数学中经常采用的数学抽象直观思维 方法的典型代表， 是一种更全面、更系统的数学结构，是解决许多实际问题的 一种理想的数学模型， 便于计算机储存和分析计算。 因此近年来图论发展迅速， 已广泛应用于许多领域，越来越为数学家和实际工作者所喜爱。 图的计数是图论中一类重要问题，尤其是有向图的计数在网络领域中有着 越来越广泛的应用。了解具有唯一一个 “ 割点源”的有向连通图的计数，在实 际中可以减少许多不必要的麻烦。 f . h a r a ry和e . m . p a l m e r ( 2 ) 阐 述了 关于标号无向图和标号 有向图的 计数问 题， r . j . r i d d e l l ( 4 ) 讨论了 标号无向 连通图的指数型生成函数与标 号无向图的 指数型生 成函 数之间的关系， g . w. f o r d 和g . e . v h l e n b e c k ( 1 ) 以及r . j . r i d d e l l 讨论了 标号无向 块 ( 2 连通图) 的指数型生成函数与标号无 向 连通图的 指数型生成函 数之间的 关系， y . l . a n ( 3 ) 讨论了 具有唯一一个 割点的标号无向连通图的计数问题。 在本文中，我们首先要讨论标号有向连通图和标号有向块的计数问题，从 而讨论具有割点的标号有向连通图的计数即具有唯一一个 “ 割点源”的标 号有向连通图的计数。 第二章基本概念及其性质 第二章基本概念及其性质 第一节图的基本概念 我们这里所讨论的图并不是几何学中的图形，而是客观世界中某些具体事 物间联系的一个数学揭象。即，图是指表示具体事物的集合 v和表示事物间关 系的集合e所组成的偶对。集合v中的元素称为图的顶点，集合e中的元素称 为图的边。 从直观上来讲，可以把一个顶点集合和一个边的集合称之为图。因为它们 可以用一个几何图形表示。但要注意描述一个图的几何图形不是唯一的.一个 图的几何图形仅描绘出它的顶点和边之间保持的相互关系，至于顶点的位置以 及边的长、短、曲、直都是无关紧要的。所以图的本质内容是顶点和边之间的 关联关系。至于顶点和边是否用平面上的几何点和线段来表示，则是完全不必 要的，即图的概念可以抽象化。 定 义2 . 1 有 序积a x b =( ( a , b ) l a c- a , b e b ) 的一 个子集合， 称为a到b 的一个二元关系。 特别地，当a = b时， 集合a到集合b的二元关系称为集合a 上的一个二元关系。 如果组成偶对的两个事物a 和b 与次序无关，也就是说偶对 ( a , b ) 和偶对 ( b , a ) 相同，则称这种偶对为无序对， 用 a , b ) 表示。 用顶点代表事物， 用边 代表各事物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把 相应的顶点连成一条边，这种由顶点及连接这些点的边所组成的图就是我们图 论中所研究的图。 定义2 . 2设v为非空集合， e是v中不同元的无序二元对的一个集合， ( v = ( v , 、 v 2 、 . . . . . . ) ,e = ( ( v ， ” i v i , v e v ) ) ， 则 称 一 个 有 序 对( v ， e ) 为 无向图， 记为g = ( v, e ) 或。_ ( v ( g ) , e ( g ) ) 。 其中称v为顶点集合， e 为边 集合。 如果v , e都是有限集合，则称图g= 一个有p 个顶点 和k 条边的图称为 ( p， k ( v, e ) 为有限图，否则称为无限图。 ) 图。 一个( p， k) 图， 若它的p 个 第二章基本概念及其性质 顶点标以不同的名称，则称为标号的，否则称为非标号的。 定 义2 . 3对 任 意 两 个 标 号 图 g、 g z ， 如 果 存 在 一 个 从 v ( g) 到 v ( g) 的 1 - 1 映 射f , 并 且f 保 持 两 图 中 的 点 之 间 的 相 邻 与 标 号 关 系 ， 则 称g与 g 2 是 同 构 的 ， 记 做g. g z 。 如 图2 . 1 中 所 示 的 图 g和 g 2 在 对 应 v , h u j ( i = 1 , 2 , 3 , 4 , s , 6 ) 下 是 同 构的。 岑 vs v6 图 2 . 1 图中顶点的个数叫做图的阶。 若连接同一对顶点的边数大于1 ， 则称这样的边为 多重边，其边数称为重数。 定 义2 . 4 对于图g = ( v ( g ) , e ( g ) ) , v ( h ) c v ( g ) , e ( h ) c_ e ( g ) ， 且h中 边 的重数不能超过g中对应边的重数，则称h = ( v ( h ) , e ( 玛) 为图g的子图。记 作h c g 。如果v ( h ) c v ( g ) 或e ( h ) c e ( g ) ，则称h为。的 真子图。 如果 v ( h ) = v ( g ) 且 e o h ) c e ( g ) ， 则称h为g的生成子图。 图论中大多数定义和概念是根据图的表示形式提出的。一条边的端点称为 与这条边关联，反之一条边称为与它的端点关联。与同一条边关联的两个端点 称为邻接。如果两条边有一个公共顶点，则这两条边邻接。 假 如 v , 和 v i 是 图 g 的 两 个 顶 点 ， 如 果 v , 和 v , 邻 接 ， 则 在 v , 和 v , 之 间 有 一 第二章基本概念及其性质 条 边 e , 记 做 。 一 (v ,v , ) 或 简 记 作 。 一 v ,v , 。 如 下 图 2 .2 ， 顶 点 u 与 顶 点 v 是 邻 接 的 ， u 与w 不 邻 接 ; 边 e , 和 e 2 是 邻 接 的 ， 而 e , 和 e 3 不 邻 接 图2 . 2 图g=( v , e) 中形如 ( v， v ) 的 边 ( v e v ( g ) ) 也就是端点重合为一 点的边叫做环。如上图2 . 2。 无多重边，又无环的图称为简单图。 图g的 边数 用e ( g ) 表示， 记i ei ， 顶点 数用v ( g ) ，记i vi . 定 义2 . ， 设v ( d ) =( v t v 2 . . . . . . . ) 是一 个非空 有限 集合， a ( d ) 二 ( a , , a 2 . 是 与v ( d ) 不 相 交 的 有限 集 合 ， 一 个 有向 图d 是 指 一 个 有 序 三 元 组 ( v ( d ) , a ( d ) , f, ( d ) ) , 其 中 低是 关 联 函 数 。 它 使a ( d ) 中 的 每 一 个 元 素 ( 称 为 边 或弧) 对 应于v ( d ) 中 的 有序元素 ( 称为顶点或点 ) 对 ( 可以 相同) 。 若a 是一条弧， 而“ 和 v 是 使 得 低( a ) = ( u , v ) ( # ( v , u ) ) 的 顶 点 ， 则 称a 从u 指向 v , 称u 是。 的起点， v 是a 的 终点。 简记为a = ( u , v ) 。 即: 有向 图 就是每条边都有方向 的图。 定义2 . 有限 非空点边交错序列 w=v o e , v , e 2 * e k v k 使 e , 的 两 个 端 点 为 v ,- , , v , ,l s i s k , 或 记 为 w = v u v , v 2 * v k 称w 为 v o 到 v . 第二章基本概念及其性质 的 一 条 途 径 ， 顶 点 v o 和v l 分 别 称 为w 的 起 点 和 终 点 w 中 边 的 数目 k 为w 的 长 途 径 w 有 时 也 称 它 为 (v o .v k ) 途 径 。 如 果 v o 一 、， 称 它 为 闭 的 ， 否 则 称 为 开 迹:把边不重复的途径称为迹。 路:把点不重复的迹称为路。 定义2 . 7 任何两点之间都至少有一条路的图称为连通图。 定义2 . 8 在v 上定义一个关 系r ， 称为 连通关系。 x r y q x = y 或x 和y 有 即内部部分连通叫连通分支。 定义2 . ， 设v e v ( g ) , g中与顶点v 关联的边的数目 ，称为v( 在g中) 的路 的 度 ， 记 做d e 民(v ) 或 简 记 做 d e g ( v ) o 有向图g中，以顶点v 为起点的弧的数目，叫做v 的出度。 有向图g中，以 顶点v 为终点的弧的数目，叫做v 的入度。 显然，对有向图g中的任一顶点v ，有: 度 =出度 +入度 源:若有向图中某点的入度为零，则称这个点为源。 定义2 . 1 0 对图g的某一点v ， 若去掉顶点v 时， 其连通分支起变化 ( 增 加至少一个) ，则称顶点v为图g的割点。 定义2 , 1 1 如果一个图中有一个点既是割点又是源，那么我们就把它称作 割点源。 定义2 . 1 2对连通图g中的任意点v ， 若去掉顶点时， 其连通分支不起变 化，则称此图g为块 ( 或称为二连通图) 。 块的两点之间都至少有两条不同的路，而连通有可能必须只经过一点，即: 只有一条路。 定义2 . 1 3如果一个连通图至少含有一个源， 且把这个源去掉之后是一个 有向块，那么我们把这种图称为锥.且稼这个渡为锥的根。 第二章基本概念及其性质 第二节 生成函数及其性质 2 . 2 . 1 生成函数的基本概念 生成函数是计数的一个强有力的工具。 例如: ( 1 十 以 x 1 十 b x ) ( l + c x ) 一 1 + ( a + b + c ) x + a b + b c + a c ) 犷嵌 犷 其 中 ， 丫 的 系 数 表 示a ,b ,。 中 取 个 的 组 合 ( 一 。 ， 1 , 2 , 3 ) 注意:1 ) 1 表示什么也不取; 2 )若考虑顺序，则上式右端变为 3x-卫 1 + ( a + b + c )了十 ( a u + n a + n c + c u + a c + c a ) z x十 a b c 十 a c b + b a c + b c a + c a b 十 c b a ) 2! 由此可知，生成函数可分为两种: 定 义1 . 1 4称 形 式 幕 级 数 艺口 x 为普通型生成函数. 称 形 式 幕 级 数艺氏 x l i n ! 为 指 数 型 生 成 函 数 。 显然有: ( 2 . 1 ) ( 2 . 2 ) 一般地， f ( x ) 是没有意义的。 对于生成函数的收敛性也不做考虑。 第二章基本概念及其性质 一叫 -一一- 一.- . 户 目 一一一-目一 令 f (x)一 菩 二 、 ) = 蔫 。 、 “ 一 蔫 (n + 1)a *,x ， 贝 “称 f (x，为 ” 式 ” 数( 或 记 为 d f ) o 古 2 . 2 . 2 生成函数的应用 2 . 2 . 2 . 1 普通型生成函数 例2 . 1求当 元 素 允 许 重 复 时n 元素 的r 一 组 合 数 公 式a , . 设g ( x ) 一艺a , x 因为 对于n 个元 素中的 每一个元素允许重复 取r ( r = 0 , 1 , 2 ， 蹄 的生 成函 1 十 二 +2 + 3x x + . . .+ x + 二 ， ) 一 十 x + x 2 + ,z 3 + - . .少 为以 解数所 因 为 当 冈 1 时 ， 1 + 二 + f+. 一 1 一x 所以有: g (x ) ! ,牛r 一 (1 - x r 妙-x) 由推广的二项式定理得到: ( 1 - x y = ( 1 + ( x ) y 一 e (r n) ( x y 一 鑫 (- 1 c (n + 一 1,r )( ly x , 第二章基本概念及其性质 = i : c ( n + r 一 1 , r ) .x 所以 a , = c ( n + r 一 1 , r ) 例2 . 2 求从n 类不同的物体中选择r 个物体并且每类物体至少选一个的方式数 a, * ffi : 设 g ( x ) = 艺a, x 则对n 个元素中的每一个元素允许重复且至少选一个的生成函数为 z3 x +x + x 十 g (x ) = (x + x 2 + x 3 . . .) =x 心 + x 十 x 2x + 二 一./x .一x- x一一.尹iil -八妙. = x e( 二 )( x r ah) c (n + r - l,r )( - l l x 一 y_c ( n + r 一 i , r ) xn * ,x 令n + r = t ，则当r = 0 时，t = n , n + ， 一 1 = t 一 1 6护 c .艺闻 所以有:g ( x ) = 一 l t 一 n ) . 第二章基本概念及其性质 一 i c ( - 一 1 , r - n ) x 故有: a . 二 c ( - 一 1 , r 一 n ) 2 . 2 . 2 . 2 指数型生成函数 在含有若干个同一物体的袋中取0 , 1 , 2 , 个的指数型生成函数为 卜x- + x + . . . + x+ 二 1 ! 2 ! r ! =e 例 2 . 3求在n 个物体中，允许重复地取r 个的方法数。 瓜e -一 丫1|，产 解: 。2 3 ，.弄 . x.x 1 十 十 十 十 . 1 ! 2 1 3 1 例 2 . 4 因为 所以， 由 1 . 3次， _矛 x 一 l , n, _ o 万 方 法 数 为 a ， 二 n 2 , 3 , 4 能组成多少个五位数?要求这些五位数中1 出现2 次或 2 最多出现 1 次，4出现偶数次。 解:根据题意，所对应的生成函数为: 23 g. w 工十 工 l + x1! 1 + 三 十 /万1 - r卜ilwe了.卜.，、 1一，白十 -一 24 ( 因为:1 + x十 孟+ 2 ! 4 ! 1 + 三 + + 且 2 ! + 旦 + 时 十 3 1 4 1 第二章基本概念及其性质 xx =旦 二 e) z zx-6 所以，原式= 6 + 4x + x 2).e x 汽 令 十 4 x + a .( z 十 :) 因 为 所 求 的 五 位 数 的 个 数 为 g e (x ) 中 的 _x5 ! 的 系 数 。 且 g e (x ) 中 普 的 系 数 为 : 0 佗j 目.1 一一 、.!2 1一朴 x 们里 + 才-刀 5 5 ( 生 3 、兰 十 4 x 3 ! 所以，所求的五位数的个数为1 3 0 . 第三章标号有向块的计数 第三章标号有向块的计数 第一节标号有向图的计数 定理3 . 1 ( p , k ) 图的个数为 证明:， 点 中 任 取 两 点 均 可 产 生 一 条 边 ， 所 以 共 有 闭条 边 可 供 选 择 。 于 又设p 点标号 有向图的指数型生成函数为 ，鑫 d ， pd (x)= i d , p 其 中 d， 表 示 顶点个数为p的标号有向图的个数，由定理 3 .2知，p 点标号有向图的个数 d , = 2 p(p-1) . 例 如 : 叫个 点 的 标 号 有 向 图 的 个 数 为 2 2 ,4 2 - 1) = a 个 ， 如 图3 . 1 : . - 佣 1 2 们卜. . 一 1 2 图3 . 1 2 .艺p-l 从而得: d ( x 卜( 3 . 2 ) 第二节标号有向连通图的计数 我们利用指数型 生 成函 数d ( x ) 来讨论标号有向 连通图的计数。 设a ( x ) 为 标 号 图 g的 指 数 型 生 成 函 数 ， ” a(x l k k ( 3 . 3 ) 其中 ， q ! 表 示 顶 点 个 数 为k 的 具 有 性 质p ( a ) 的 图 的 个 数。 第三章标号有向块的计数 设b ( x ) 为 标 号 图g 的 指 数 型生 成函 数， 即 、客 、 ke b k x ， 反表示 顶 点 个 数为 k 的 具 有 性 质p 伪 ) 的 图 的 个 数。 则 有: 引 理3 . 1 ( 1 . 八) d ( x ) = a ( x ) b ( x ) 伽k 粼 k(e a k k ,)(e b k k ) .止 一 ed k x k = , 介k ! k ， _xk ! 的 系 数 d . 为 顶 点 个 数 为 “ 的 有 序 对 (g ,g z) 的 个 数 ， ( 3 . 4 ) ( 3 . 5 ) 即 : 中中 其其 d k = 】匕g z 以g z ) 代 表 图 g . , g z 的 二 元 有 序 组 合 图 。 g具 有 性 质 ， (a ) g z 具 有 性 质 p (b ) 。 即 : d ( x ) 为 图 g , 和 g ， 的 有 序 组 合 图 的 的 指 数 型 生 成 函 数 。 令 标 号 有 向 连 通 图 的 指 数 型 生 成 函 数 为 c (x )= 全 c p 菩 ， 其 中 c ， 为 顶 点 p 司尸 个数为p 的 标号 有向 连通图的 个数， 则c ( x ) c ( x ) 为两个标号有向 连通图的 有 序组 合图的指数型生成函数，而c ( x ) c ( x ) 2 旦 为含有两个连通分支的无向组合图的指数 型 生 成 函 数 ， 其 中 _x6 1 的 系 数 恰 为 含 有 两 个 连 通 分 支 的 * 点 标 号 有 向 图 的 个 数 。 几 : 第三章标号有向块的计数 定理3 . 3 标号有向 连通图的指数型生成函数 c ( x ) 和标号有向图的指数 型生成函数d ( x ) 具有如下关系: 1 + d ( x ) = e ( 3 . 6 ) 证 明 : 由 引 理 3 . 1 的 结 论 知 ， 己( x ) 中 善 ps系数为n 个标号有向连通图 的有序对的 个数， 它 们顶点的总数为p ， 显然已 x ) 月 ! 中 善的 系 数 为 顶 点 个 数 为 k! k 、连通分支的个数是n 的标号有向图的个数，因此，对n 求和即可得标号有向 图 的 指 数 型 生 成 函 数 : d ( x 艺 c ( x ) n ! = e 所以，d ( x 卜 .艺词 而 = t 卿 一 塑 面 m.块 故: 一c_e， 一 1 1 十 d ( x - e (” 从 而 得 出 : c ( x ) = l n ( d ( x ) + 1 ) 由 、 全 2 p(p-l)蓉可 得 c (x )的 前 9 项 为 : r - 1 p! 。，、3 z 5 4 3 3 8 3 4 i - ( x) =x+一 y 十 y 十 2 1 3 ! 粼 4 1 0 2 7 0 8 0 ， 1 0 6 7 3 0 8 4 8 8 x+ 一 一 ; 二 一 一 x十 一一 下 ; 一 一 x 4 3 9 0 4 8 0 1 9 3 9 0 4 ， 7 2 0 2 2 3 4 6 3 8 8 1 8 1 5 8 4 4 7 2 1 7 1 7 6 4 3 2 4 9 2 5 4 7 5 1 3 6 0 ， 石 1 x一 一一 下石 一x 。 .一 x + 。 . - 一 第三章标号有向块的计数 ( 3 . 乃 第三节标号有向块的计数 设 b ， 为 顶 点 个 数 为 p 的 标 号 有 向 块 的 个 数 ， 令 标 号 有 向 块 的 指 数 型 生 成 函 数为b ( x ) ， 即 : d , ., _ 矛。 px 。 气 ， 一l 力。 ， 了 p = 1p! ( 3 . 8 ) 且 规 定丑= 0 0 定理3 . 4标号有向 块的指数型生成函数b (x ) 和标号有向连通图的指数型 生成函 数c ( 习 具有如下关系: 1 . c ( . ) = b ( x c ( x ) )( 3 . 9 ) 其中:c ( x ) = d ( c ( x ) ) d x b (x ) = 鱼 望 ( x ) ) . d x 证明: 令r ( x ) 表示有根标号有向 连通图的指数型生成函数，则 px-p! r (x ) =艺r p ( 3 . 1 0 ) 因 为 对 所 有 的 p 都 有 r , = p c , ， 于 是 我 们 得 到 : r (x) = y- p c p p-1若 x ( p 一 1 ) c .艺p-l -一 .p - 1 。 x ) !. plp-1 c p .(p - 1 第三章标号有向块的计数 而 鑫 c l .高一 c (.). 所 以 : r ( x ) = x c ( x ) 0. 1 1 ) 令r . ( x ) 为 根 的 周围 恰 好有n 个 块的 有 根标 号 有向 连 通图 的 指数 型生 成函 数，显然有: r . ( x ) = x ( 3 . 1 2 ) 和r ( x ) 二 艺r . ( x ) ( 3 . 1 3 ) 又r , ( x ) 表 示 根 的 周围 只 连 接 一 个 块的 有 根 标 号 有向 连 通图 的 指 数型 生 成 二 . ， : 二r , ( x ) ， 二、 、 。 。 ， 土 、 。 * 。 * 播 ， ， * 二 : 斗 二 二 . ma几， 沪 ， 、: u不(/j、二 刁k叮目决 生 口 j wc l nvr ， 口，声 曰 i j =j m c a l目彗，日y m ss e - =- p j 4 m x几。 x 因此， 生成函数， ( r l x y _ _ * _ _ _ _ “ _ _ 、_ 、_ _ 二 _ _ _ 人 _ 二 _ _ _ ! 竺竺二 21 表示n个根未标号的有向连通图的有序组合图的指数型 x j ( r i(x )1 0 .八x， ， ，_ ， _， _。 . _、， 、 ._ . _ _ ， _. _ 则 一为根小称亏且恰a lt 连按 月个 块 的有很称 兮有 同连通 图 m. 的指数型生成函数。 如果这n 个根已 经确定， 我们可以用一个单独的标号来确定 它们，这样就对应一个根不标号且恰好连接n 个块的有根标号连通有向图的计 数。再对这个根进行标号，只需令这个级数乘以x ，从而我们得到: r( x ) = x ( 3 . 1 4 ) 综合( 3 . 1 3 ) 和( 3 . 1 4 ) 有: 第三章标号有向块的计数 r ( x )= ; 二.(ri(x)hxxn! =二.; 翠 ( 3 . 1 5 ) 下 面 我 们 设 法 用 b ( x ) 和 r (x ) 来 表 示 r : ( x ) . _ ( r (x h _ py 百 先， 生 成 函 数 i .!的各 l x 少尸 的系数表示具有p 十 k - 1 个顶点，且其中 包含k - 1 个未标号的 根的k - 1 个有向 连通图的计数 ( 注意: ( k - 1 ) 个图中的每一 个都是根节点未标号的有根连通图) 。而 ( k 一 1 ) 表示添加一个点，且与所给的k - 1 个根一起构成一个块 ( 此块以添加的点为根， 且所有的点都进行了标号)的有根有向连通图的计数。如图3 . 2 : 第三章标号有向块的计数 添加点 图 3 . 2 因 此 ， 由 r , ( x ) 的 定 义 可 知 : r j - ) = xi b k黔-k-i (k - 1) = x b ( r ( x ) ) ( 3 . 1 旬 由 ( 3 . 1 1 ) 变形为 o x ) 一 r (x ) 所以，再利用( 3 . 1 1 ) , ( 3 . 1 5 ) 和( 3 . 1 6 ) 可知: c ( x ) = e x p ( b ( r ( x ) ) = e x p b ( x c ( x ) ) ) 故: 1 n c ( x ) =b ( x c ( x ) ) 利用这个定理我们可以算出b ( x ) 的前8 项为: 。 ， 、 _ 3 o l xr - 内 二 传 盈 2 2 7 ， 2 4 3 0 8 2 3 7 7 0 ， 9 7 8 2 8 8 8 4.9 7 8 2 8 9 8 4 0 十 丽x十 二 不x 一亏 厂x+ 一 一 万 f -x 4 2 5 7 7 8 2 3 1 2 6 1 6， + 不了一一x 7 1 2 8 9 1 6 0 8 9 8 1 8 0 4 0 0 : 4 7 0 6 1 9 9 4 7 0 0 5 5 7 1 3 1 5 3 61 6 9 1 一一一 一 一 飞 丁 一 一一一一x 十9x+ ( 3 . 1 乃 第四章具有唯一一个 “ 割点源”的标号有向连通图的计数 第四章 具有唯一一个 “ 割点源”的标号有向连通图的计数 我们利用标号有向块的指数型生成函数来研究具有唯一一个 “ 割点源”的 标号有向连通图的计数。 用 q w.， 表 示 具 有 唯 一个“ 割 点 源 ” ， 且“ 割 点 源 ” 周 围 恰 有 ” 个 有 向 块 的 顶点数为p 的标号有向 连通图的个数。 令 q (x )= 鑫 - w.p 若 ( 4 . 1 ) 则级( .!,) 表 示 具 有 唯 一 个“ 割 点 源 ” ， 且“ 割 点 源 ” 周 围 恰 有 。 个 有 向 块 的 标号有向连通图的指数型生成函数。 定 理 4 .1 指 数 型 生 成 函 数 县( x ) 和 b ( x ) 具 有 如 下 关 系 式 _ (x ) = 二 . b ( 2 x 1 b x ( 4 . 2) 证明:令 s ( x )表示根不标号的锥的指数型生成函数。即: s w x p: ( 4 . 3 ) 其 中 s ， 是 去 掉 根 之 后 是 一 个 p 个 点 的 有 向 块 的 根 不 标 号 的 锥 的 个 数 从 根 出发 可以向 这p 个点最多引p 条线， 又因为这p + l 个点的图连通， 所以 这p 条 线 一 共 有2 p 一 1 种 组 合 于 是 ，s p = b p l a p 一 1) w 其 中 ， b ， 表 示 顶 点 个 数 为 ， 的 有 向 块 的 个 数 。 对p 求和， 有: s ( x ) = b ( 2 x ) - b ( x ) . 第四章具有唯一一个 “ 剖点源”的标号有向连通图的计数 用 s :,， 表 示 p 个 点 的 标 号 锥 的 个 数 ， 且 s : ( x ) = 则 由 s 1,， 一 p s , 可 知 ， .v 荟 s，pxe s 1p p ! _x p s p _ 1 p 卢 刁 知 向 所以 .s : ( x ) = x s ( x ) ( 毛4 ) 那 么 s 1(x ) 中 x 0 的 系 数 为 顶 点 个 数 为 ， + 1 x p: 的根不标号的锥的个数。 ( s ,(x )1 0 于 是由 引 理3 . 1 可 知， 兰 一 三 一乙 . 是n 月 ! 个这样的根不标号锥的无序组合的计 如果把这n 个根一起对应到一个点上，且对这个点标号，则这个点就成为 “ 割点源气 数了 由此可得 ( s 1( x ) ). q . (x ， 一 ， 一 一 xn ! ( s ( x ) ) 刀! . b ( 2 x ) 一 b ( x )j n i 利 用 这 个 式 子 可 以 计 算 出 q . ,， 来 ， 如 表 4 . 1 : 第四章 具有唯一一个 “ 割点源”的 标号有向连通图的计数 表 4 . 1 q + .vp月 p 4p巧p= 6p习p= 8p刁 n- 231 0 84 9 9 5 1 1 9 5 5 6 0 1 1 0 9 4 9 4 2 6 0 3 4 9 1 9 4 3 7 0 8 9 6 03 9 0 7 5 7 9 4 3 3 9 0 5 1 4 8 4 n= 3042 7 01 8 6 3 04 6 1 8 2 1 5 4 5 9 8 6 1 9 4 8 01 5 9 0 2 5 7 0 0 3 9 5 8 0 n= 40055 4 0 5 1 9 7 51 3 6 7 6 0 4 0 1 4 3 2 2 5 6 4 5 8 5 月= 500069 4 5 1 2 0 9 6 03 4 2 9 2 1 6 0 n 600007 1 5 1 22 4 8 3 4 6 例 如 : q . = 3 时 ， 如 下 图3 个 : 图4 . 1 进 一 步 ， 令 q ， 表 示 具 有 唯 一 个“ 割 点 源 ” ， 且“ 割 点 源 ” 周 围 的 每 个 连 通分支都是块的顶点数为p 的标号有向连通图的个数。 令 “ ， 二 鑫 。 ， pe q o p ( 4 . 5 ) 则q ( x ) 为具 有唯 一一个“ 割点源” 的标号有向 连通图的 指数型生 成函 数. 定理4 . 2指数型生成函数 b ( x ) 具有如下关系: q (x ) 一 二 公 ” ， 一 b ( 2 x ) + b ( x ) 一 ， ( 4 . 6 ) 证 明 ， 显 然 由 q v 的 定 义 可 知 ， q p = e q ., 第四章 具有唯一一个 “ 割点源”的标号有向连通图的计数 因此，由定理4 . 1 可知: q (x) = 1 q xp-3 p p ! e e q .pp-3 n-2 e e q n.p2 p-3 一 燕 q (x ) 一 e x b (2 x )- b (x )l- 2 n! 、.，1.1 目.且 f n月 (x b .-2 b 2 x b (xn! 鑫 b 2+ b x -o n! b ( 2 x ) - = 二 . f b2jr e” 一 ， (2 x ) + b (x ) 一 1 我们利用这个式子可以 算出q ( x ) 的前9 项: q ( x ) 1 1 2 4 5 2 7 0 + 丁x十5 ! ， 1 2 1 4 7 3 6 x +一 一 一-x 十 1 1 1 4 1 6 5 4 0 2 ， 月一一一又; 一x 3 4 9 6 5 5 6 1 2 6 9 6 0 + 一 8 ! 。 3 9 0 9 1 7 1 1 2 6 6 1 9 8 4 3 2 x十 一一一9 !闷 x + ， 。 . 。 。 ， ( 4 . 7 ) 由 上 式 可 得 q ， 与 p 的 关 系 如 下 表 : 第四章具有唯一一个 “ 割点源”的标号有向连通图的计数 表 4 . 2 p 34， 7皿9 l v 31 1 25 2 7 01 2 1 4 7 3 61 1 1 4 1 6 3 4 位3 4 9 6 5 5 6 1 2 6 9 6 0 例 均1 1 1 1 1 6 6 1 9 8 4 3 2 在此仅举三个顶点的例子。如下图: 凡， 八 2 图 4 . 2 致谢 致谢 经过一年多的思路酝酸和整理， 终