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

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

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

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