不含C、C和不含C的极图

摘要

图论是数学的一个分支，它与数学的其他分支有密切的关系。这些分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合论等。随着计算机科学与数学的发展，图论已经成为人们研究自然科学以及社会科学的一个重要工具。 极图理论是图论中的重要组成部分。极图问题中最主要的一类问题是：给定一族ψ={G<,1>，G<,2>，…，G<,m>}，ex(n；ψ)表示由n个顶点组成的不包含任一G，∈ψ的图的最多边数。EX(n;ψ)表示由n个顶点组成的不包含任一G，∈ψ的边数最多的图(极图)的集合。 在不包含多边形的极图问题中，对于ψ={C,,4>}的极图问题，Clapham等人给出了所有，n≤21的极图，杨元生等人给出了所有22≤n≤31时的极图；对于ψ={C<,3>，C<,4>}的极图问题，Garnick等人给出了n≤24的所有极图。对于ψ={C<,3>，C<,4>，C<,5>}的极图问题，杨元生等人给出了n≤42时ex(n；{C<,3>，C<,4>，C<,5>})的值以及相应的所有极图，并对于n>42的情形给出了上界。 本文在此基础上主要研究了禁止子图族ψ={C<,4>，C<,5>}时的极图问题和禁止子图族ψ={C<,6>}时的极图问题。本文主要采用的方法是：用已有的临界图构造算法对不含四边形五边形和不含六边形的临界图进行构造，以此构造的图的边数作为极图边数的下界，然后使用反证法和数学归纳法对边数的上界进行证明，直到推出极图边数上界与下界相同，对于极图的证明也要采用数学归纳法对其正确性和完备性一一证明。主要给出如下结果： (1)当ψ={C<,4>，C<,5>}时，本文给出了顶点个数n≤21时ex(n；{C<,4>，C<,5>})的值以及相应得极图，并对极图的边数给出了数学证明； (2)当ψ={C<,6>}时，本文给出了当顶点个数，n≤10时ex(n；{C<,6>})的值和相应的极图，并对极图的边数以及极图集合的正确性和完备性给出了证明；对于顶点个数10}，给出了n≤10时ex(n；{C<,6>})的值和相应的极图，并给出了数学证明，对于10})的下界。

目录

文摘

英文文摘

声明

引 言

1极图的相关概念

1.1本文涉及的图论概念

1.1.1图的基本概念

1.1.2路

1.1.3树

1.1.4常用的图和标记

1.1.5常用的图的运算

1.2极图问题

1.2.1 Turán原始极图问题

1.2.2一般极图问题

2不包含多边形的极图问题

2.1不包含三边形的极图问题

2.2不包含四边形的极图问题

2.3不包含三边形四边形的极图问题

2.4不包含三边形四边形五边形的极图问题

2.5其他相关的极图问题

2.6本文工作

3不包含四边形五边形极图的边数的数学证明

3.1基本定义

3.2基本引理

3.3顶点个数不超过21的不包含四边形五边形极图的边数

4不包含六边形极图的数学证明

5不包含六边形的图的构造方法

5.1相关定义及引理

5.2母图为M0的图的构造

5.3母图为Mi(1≤i≤3)的图的构造

5.3.1母图为M1的图的构造

5.3.2母图为M3的图的构造

5.3.3母图为M3的图的构造

5.4结果讨论

5.5不包含六边形的极图的计算机构造

5.5.1相关定义

5.5.2构造临界图的步骤

5.5.3构造临界图的结果

结论

参考文献

附录A EX(n;{C6})中的图(5≤n≤28)

攻读硕士学位期间发表学术论文情况

致 谢