不含c-%2c4-、c-%2c5-和不含c-%2c6-极图

《不含c-%2c4-、c-%2c5-和不含c-%2c6-极图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文摘要图论是数学的一个分支，它与数学的其他分支有密切的关系。这些分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合论等。随着计算机科学与数学的发展，图论已经成为人们研究自然科学以及社会科学的一个重要工具。极图理论是图论中的重要组成部分。极图问题中最主要的一类问题是：给定一族y---{GI，G2，⋯，G0>，积巧y)表示由撑个顶点组成的不包含任一G，∈y的图的最多边数。EX(n；y)表示由／,／个顶点组成的不包含任一G，∈1

2、fr的边数最多的图(极图)的集合。在不包含多边形的极图问题中，对于y={C4)的极图问题，Cla：pham等人给出了

3、所有砧≤21的极图，杨元生等人给出了所有22s丹s31时的极图；对于妒={C，C。}的极图问题，Garniek等人给出了ns24的所有极图。对于y={Cs，c。，C。}的极图问题，杨元生等人给出了珂≤42时瞰疗；{G，c4，G))的值以及相应的所有极图，并对于胛>42的情形给出了上界。．本文在此基础上主要研究了禁止子图族y={C。，C5)时的极图问题和禁止子图族y={c6}时的极图问题。本文主要采用的方法是：用已有的临界图构造算法对不含四边形五边形和不含六边形的临界图进行构造，以此构造的图的边数作为极图边数的下界，然后使用反证法和数学归纳法对边数的上界进行证明，

4、直到推出极图边数上界与下界相同，对于极图的证明也要采用数学归纳法对其正确性和完备性一一证明。主要给出如下结果：(1)当y={c4，C，)时，本文给出了顶点个数珂≤21时ex(n；{C。，C))的值以及相应得极图，并对极图的边数给出了数学证明；(2)当y={c6>时，本文给出了当顶点个数胛≤10时ex(n；{C。))的值和相应的极图，并对极图的边数以及极图集合的正确性和完备性给出了证明；对于顶点个数10<行≤29时，本文分别采用了不同的母图对不含六边形的图进行构造，比较其结果最终给出了对于y={c6}，给出了行≤10时ex(n；{C。))的值和相应的极图，并给出了

5、数学证明，对于10<刀≤28的情况，采用不同的母图进行计算机构造，给出了构造图的结果，同时也提出了ex(n；{C})的下界。关键词：极图；临界图；禁止子图；圈大连理工大学硕士学位论文TheExtremalGraphwithoutC4orC5andtheExtremalGraphwithoutGAbstractGraphTheoryisabranchofmathematics．Graphtheoryisalsointimatelyrelatedtomanybranchesofmathematics，includinggrouptheory,matrixtheory

6、，numericalanalysis，probability,topology,andeombinatories．Withthedevelopmentofcomputerscienceandmathematics．GraphTheoryturnsintoanimportanttooltoresearchtechnologyandnaturescience．evenforthesocialscience．ExtreirnltheoryisanimportantpartofGraphTheory．Theprimeexampleofallextrenlalproble

7、misthefollowing：givenasetofgraphsy={GI，G2，⋯，G埘，，let麟(胛；y)denotethegreatestsizeofagraphwithorder行thtcoI吐ai∞n0subgraphisomorphictoanyGl(1sfs所)，letEX(挖；妒)denotethes或ofgraphswithorder疗andm∞【iI姗sizethatcontainsnO如bgraphisomorpltictoanyGI(1≤fs掰)．Fortheextremalproblemscontainingnopolygon,fo

8、ry={c4)，Chpllaminvestigatedthevaluesof“印；y)仍s21)，Yuamhenginvestigatedthevaluesofex(n；y)(22≤万≤31)；Forlf，={C3，e}，Cramickim,estigatedthevaluesof以(月；妒)(栉s24)；Fory={C3，C4，G)，Yuanshenginvestigatedthevaluesof蹦(蚓矿)andgivethecorrespondingextremalgraphsr甩≤42)．Thispaperinvestigatesthevaluesof酬玎

9、；y)fory={C4，