论文部分内容阅读
图论(Graph Theory)是数学的一个分支,它与数学的其他分支有密切的关系。这些分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合论等。事实上,图论为任何一个包含二元关系的系统提供了一个数学模型;利用图直观、漂亮的表现特性可以使人对现实的系统有清晰的了解。这个领域内的许多问题,即使是对图论一无所知的人,都是非常容易理解的,但是想要得到这些问题的结论却要使聪明的数学家绞尽脑汁。 随着计算机科学与数学的发展,图论已经应用到了各个领域,其中包括物理学、化学、通讯科学、计算机技术、土木工程、建筑学、运筹学、生物遗传学、心理学、社会学、经济学、人类学和语言学等等,几乎包括了人类社会的所有领域。图论已经成为人们研究自然科学以及社会科学的一个重要工具。 极图理论是图论中的重要组成部分。极图问题中最主要的一类问题是:给定一族图ψ={G1,G2,…,Gm},ex(n;ψ)表示由n个顶点组成的不包含任一Gi∈ψ的图的最多边数。EX(n;ψ)表示由n个顶点组成的不包含任一Gi∈ψ 的边数最多的图(极图)的集合。 在不包含多边形的极图问题中,对于ψ={C4}的极图问题,Clapham等人给出了所有n≤21的极图(Journal of Graph Theory,Vol.13,no.1,(1989),29-47),杨元生等人给出了所有22≤n≤31时的极图(UTILITAS MATHEMATICA,41,(1992),204-210);对于ψ={C3,C4}的极图问题,Garnick等人给出了n≤24的所有极图(Journal of Graph Theory,Vol.17,no.5,(1993),633-645). 本文主要研究了ψ={C3,C4,C5}时的极图问题,给出了n≤42时ex(n;{C3,C4,C5})的值以及n≤42时所有的极图集合EX(n;{C3,C4,C5}):对于n>42时的情形,本文给出了ex(n;{C3,C4,C5})的上界。