具有唯一一个“割点源”的标号有向连通图的计数论文

《具有唯一一个“割点源”的标号有向连通图的计数论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中文摘要中文摘要本文首先给出了有关图的基本概念以及两种生成函数，即：普通型生成函数和指数型生成函数。在此基础上讨论了Ｐ点标号有向图的个数，得出Ｐ点标号有向图的指数型生成函数Ｄ（ｘ）。进一步讨论了Ｄ（ｘ）与标号有向连通图的指数型生成函数Ｃ（ｘ）之间的关系，得出标号有向连通图的计数。同时也讨论了标号有向连通图的指数型生成函数Ｃ（ｘ）和标号有向块的指数型生成函数Ｂ（ｘ）之间的关系，并利用这一关系得出标号有向块的计数。最后，研究了具有唯一一个“割点源”，且“割点源”周围恰有ｎ个有向块的标号有向连通图的指数型生成函数Ｄ（∞与标号有向块的指数型生成函数Ｂ（ｘ）之间的关系，进

2、一步得出具有唯一一个“割点源”的标号有向连通图的指数型生成函数Ｑ（ｘ）与标号有向块的指数型生成函数Ｂ∞间的关系，并利用这个关系得出具有唯一一个“割点源”的标号有向连通图的计数问题。关键词：标号有向连通图指数型生成函数割点源ＡｂｓｔｒａｃｔＩｎｔｈｉｓｐａｐｅｒｆｉｒｓｔｓｏｍｅｂａｓｉｃｃｏｎｃｅｐｔｓｏｆｇｒａｐｈｔｈｅｏｒｙａｎｄｇｅｎｅｒａｔｉｎｇｆｕｎｃｔｉｏｎｓａｒｃｆｉｌｅｉｎ仃ｏｄｕｃｅｄ．Ｏｎｔｈｅｂａｓｉｓｏｆｔｈｉｓ．ｔｈｅｎｕｍｂｅｒｓｏｆｔｈｅｌａｂｅｌｅｄｄｉｇｒａｐｈｓｗｉｍＰｖｅｒｔｅｘｓｔｕｄｉｅｄ，ｏｆｗｈｉｃｈｔｈｅｅ

3、ｘｐｏｎｅｎｔｉａｌｇｅｎｅｒａｔｉｎｇｆｕｎｃｔｉｏｎＤ（ｘ）ｉｓｇａｉｎｅｄ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎＤ（ｘ）ａｎｄｔｈｅｇｅｎｅｒａｔｉｎｇｆｉｍｃｔｉｏｎＣ（ｘ）ｏｆａｌａｂｅｌｅｄｃｏｎｎｅｃｔｅｄｄｉｇｒａｐｈａ地ｓｔｕｄｉｅｄ，ｔｈｅｃｏｕｎｔｓｏｆｃｏｎｎｅｃｔｅｄｌａｂｅｌｅｄａ增ｏｂｔａｉｎｅｄ．Ｉｔｉｓａｌｓｏｓｔｕｄｉｅｄｔｈａｔｔｈｅｒｅｌａｔｉｏｎｓｂｃｔｗｅ，ｃ１］ｔｈｅｅｘｐｏｎｅｎｔｉａｌｇｅｎｅｒａｔｉｎｇｆｕｎｃｔｉｏｎＣ（ｘ）ｏｆａｃｏｎｎｅｃｔｅｄｌａｂｅｌｅｄｄｉｇｒ

4、ａｐｈａｎｄｔｈｅｅｘｐｏｎｅｎｔｉａｌｇｅｎｅｒａｔｉｎｇｆｕｏｃｔｌｏｎＢ（ｘ）ｏｆａｌａｂｅｌｅｄｄｉｒｅｃｔｅｄａｒｅＡｔｌａｓｔ，ｉｔｉｓｓｔｕｄｉｅｄｔｈａｔｔｈｅｒｅｌａｔｉｏｎｓｂｅ“嗍ｔｈｅｅｘｐｏｎｅｎｔｉａｌｇｅｎｅｍｔｉｎｇｆｕｎｃｔｉｏｎＱｎ（ｘ）ｏｆａｃｏｎｎｅｃｔｅｄｌａｂｅｌｅｄｄｉｇｒａｐｈ，ｗｈｉｃｈｈａｓｏｎｌｙｏｎｅｃｕｔｐｏｉｎｔｓｏｕｒｃｅａｎｄｅｘａｃｔｌｙｎｌａｂｅｌｅｄｄｉｒｅｃｔｅｄｂｌｏｃｋｓａｒｏｕｎｄｔｈｅｃｕｔｐｏｉｎｔｓｏｕｒｃ冶，ａｎｄｔｈｅｅｘｐｏｎｅｎｔｉａｌｇｅｎ

5、ｅｒａｔｉｎｇｆｕｎｃｔｉｏｎＢ（曲ｏｆａｌａｂｅｌｅｄｄｉｒｅｃｔｅｄｂｌｏｃｋ．ＩｔｉｓａｌｓｏｏｂｔａｉｎｅｄｔｈａｔｔｈｅｒｅｌａｔｉｏｎｓｂｃｔｗｅｅｌｌｔｈｅｅｘｐｏｎｅｎｔｉａｌｇｅｎｅｒａｔｉｎｇｆｕｎｃｔｉｏｎＱｎＯ【）ｏｆａｃｏｎｎｅｃｔｅｄｌａｂｅｌｅｄｄｉｇｒａｐｈｗｉｔｈｏｎｌｙｏｎｅｃｕｔｖｅｒｔｅｘａｎｄｔｈｅｅｘｐｏｎｅｎｔｉａｌｇｅｎｅｒａｔｉｎｇｆｕｎｃｔｉｏｎＢ（ｘ）ｏｆａｌａｂｅｌｅｄｄｉｒｅｃｔｅｄｂｌｏｃｋ，ｂｙｔｈｅｓｅｒｅｌａｔｉｏｎｓ，ｉｔｉｓｓｏｌｖｅｄｔｈａｔｔｈｅｃｏｔｍｔｐｒｏｂｌｅｍ

6、ｓｏｆｔｈｅｃｏｎｎｅｃｔｅｄｌａｂｅｌｅｄｄｉｇｒａｐｈｓｗｉｍｏｎｌｙｏｎｅｃｕｔｖｅｒｔｅｘｓｏｕｒｃｃ．Ｋｅｙｗｏｒｄｓ：ｌａｂｅｌｅｄｃｏｎｎｅｃ自ｅｄｄｉｇｒａｐｈⅡｅｘｐｏｎｅｎｔｉａｌｆｕｎｃｔｉｏｎｃｕｔｖｅｒｔｅｘｂｌｏｃｋ，ｍａｋｉｎｇｕ∞ｏｆｔｈｅｒｅｌａｔｉｏｎｓ，ｔｈｅｃｏｕｎｔｓｏｆｌａｂｅｌｅｄｄｉｒｅｃｔｅｄｂｌｏｃｋｓｇｄｎｅｄ．南开大学学位论文版权使用授权书本人完仝了解南开大学关丁收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并

7、采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务：学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校町以适当复制论文的部分或全部内容用于学术活动。刎、Ｚ¨明例ｆ年ｆｆ月吗经指导教师同意，本学位论文属于保密，在本授权书。年解密后适用ｌ指导教师签名：｜学位论文作者签名：ｌ解密时问：年月日各密级的最长保密年限及书写格式规定如下黼敝储鹳。羽溯一堋哆日日南开大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除

8、文中已经注明引用的内容外