图的子树的计数

发布时间：2021-01-28 11:21

　　图论是一门新兴且发展迅速的学科,与计算机、化学、物理等有很多紧密的联系,受到国内外很多学者的关注。本论文主要研究图的子树数,主要内容分为以下两部分:首先,论文第二章研究顶点数为n ≥ k的树集中含Pk最多的树结构。当k=2r为偶数时,则顶点数为n的树T含Pk的个数至多为「（n-2r+2）/2」「（n-2r+2）/2」,并刻画出Pk数目达到该数值时所对应唯一的极值树;当k = 2r+ 1为奇数时,则存在整数t ∈[2,（n-1）/r],顶点数为n的树T含Pk的个数至多为Fn,k,t =（s 2）（q+1）2+（t-s 2）q2+s（t s）q（q+1）,其中整数n,t,q,s满足n-（（k-1）/2-1）t-1=tq+s,0≤s<t,并刻画出达到极值时所对应的树的结构。特别地,当= 5时,刻画出达到极值时所对应的极值树。其次,论文的第三章研究一些图类中子树的计数情况,包含给定边数时所含子树数的最大值及最小值,并刻画对应的极值图;给定度序列的树中P4最多的树的结构。 

【文章来源】：上海师范大学上海市

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT（英文摘要）
1 第一章 绪论
    1.1 基本概念
    1.2 研究背景
    1.3 主要结果
n中含P_k最多的树结构">2 第二章 树集J_n中含P_k最多的树结构
n中含P_k（k=2r为偶数）最多的树结构">    2.1 树集J_n中含P_k（k=2r为偶数）最多的树结构
        2.1.1 预备知识
        2.1.2 定理的证明
n中含P₅最多的树结构">    2.2 树集J_n中含P₅最多的树结构
        2.2.1 预备知识
        2.2.2 定理的证明
4的情况">3 第三章 一些给定图类含子树数和P₄的情况
    3.1 预备知识
    3.2 定理的证明
4 第四章 归纳展望
参考文献
n又中含P_K最多时t的取值">附录 树集J_n又中含P_K最多时t的取值
致谢
附件


【参考文献】：
博士论文
[1]图的结构与图的子树个数[D]. 张修梅.上海交通大学 2014

硕士论文
[1]树的子树的计数[D]. 王书晶.华中师范大学 2013
[2]关于子树数目若干问题研究[D]. 刘名.青海师范大学 2012



本文编号：3004907