不包含三邊形四邊形五邊形的極圖.pdf

1、圖論(Graph Theory)是數(shù)學的一個分支,它與數(shù)學的其他分支有密切的關(guān)系.這些分支包括群論、矩陣論、數(shù)值分析、概率論、拓撲學和組合論等.事實上,圖論為任何一個包含二元關(guān)系的系統(tǒng)提供了一個數(shù)學模型;利用圖直觀、漂亮的表現(xiàn)特性可以使人對現(xiàn)實的系統(tǒng)有清晰的了解.這個領(lǐng)域內(nèi)的許多問題,即使是對圖論一無所知的人,都是非常容易理解的,但是想要得到這些問題的結(jié)論卻要使聰明的數(shù)學家絞盡腦汁.隨著計算機科學與數(shù)學的發(fā)展,圖論已經(jīng)應(yīng)用到了各個領(lǐng)域,

2、其中包括物理學、化學、通訊科學、計算機技術(shù)、土木工程、建筑學、運籌學、生物遺傳學、心理學、社會學、經(jīng)濟學、人類學和語言學等等,幾乎包括了人類社會的所有領(lǐng)域.圖論已經(jīng)成為人們研究自然科學以及社會科學的一個重要工具.極圖理論是圖論中的重要組成部分.極圖問題中最主要的一類問題是:給定一族圖ψ={G<,1>,G<,2>,…,G<,m>},ex(n;ψ)表示由n個頂點組成的不包含任一G<,i>∈ψ的圖的最多邊數(shù).EX(n;ψ)表示由n個頂點組成的

3、不包含任一G<,i>∈ψ的邊數(shù)最多的圖(極圖)的集合.在不包含多邊形的極圖問題中,對于ψ={C<,4>}的極圖問題,Clapham等人給出了所有n≤21的極圖(Journal of Graph Theory,Vol.13,no.1,(1989),29-47),楊元生等人給出了所有22≤n≤31時的極圖(UTILITAS MATHEMATICA,41,(1992),204-210);對于ψ={C<,3>,C<,4>}的極圖問題,Garni

4、ck等人給出了n≤24的所有極圖(Journal ofGraph Theory,Vol.17,no.5,(1993),633-645).該文主要研究了ψ={C<,3>,C<,4>,C<,5>}時的極圖問題,給出了n≤42時ex(n;{C<,3>,C<,4>,C<,5>})的值以及n≤42時所有的極圖集合EX(n;{C<,3>,C<,4>,C<,5>});對于n>42時的情形,該文給出了ex(n;{C<,3>,C<,4>,C<,5>})的