圖的度序列和競(jìng)賽矩陣.pdf

1、摘要本文研究了極值圖論中經(jīng)典Woodall定理的變形和得分向量偏序集上Schur函數(shù)的應(yīng)用，第一章討論了經(jīng)典Woodall定理的變形：求最小正偶整數(shù)a(。Q，n)，使得所有滿足一(”)2a(。q，n)的n項(xiàng)亙里生型”是蘊(yùn)含。q可圖的我們給出了，當(dāng)4sfs8，n≥l時(shí)，a(aG，n)的值和n≥12時(shí)，a(3Cs，n)的值第二章中討論了得分向量偏序集上Schur函熬的應(yīng)用：所有n維得分向量集合k在優(yōu)超關(guān)系下是一個(gè)偏序集L。上的實(shí)函數(shù)g(s)

2、為(嚴(yán)格)Schur凸的，若對(duì)任意s，s7∈L。，s≠s7，s優(yōu)超s7，恒有g(shù)(s)≥()g(s，)我們證明了，，(s)=STs和得分向量為s的競(jìng)賽圖％中3一圈個(gè)數(shù)C3(s)在三。上分別是嚴(yán)格Schur凸和嚴(yán)格Schur凹的稱(chēng)n維得分向量s為奇異的，若得分向量為s的每個(gè)n階競(jìng)賽圖咒的鄰接矩陣都是奇異的應(yīng)用L。上嚴(yán)格Schur凸函數(shù)，(s)，我們給出了得分向量為奇異的一個(gè)充分條件，211基本概念第一章蘊(yùn)含sG可圖序列所有滿足n一1≥dl≥

3、d：≥≥d?！?的整數(shù)序列”=(dl，d2，，如)的集合記作NS。設(shè)”∈NS。，稱(chēng)”是可圖的，若”是n階簡(jiǎn)單圖的度序列這樣的圖稱(chēng)作”的一個(gè)實(shí)現(xiàn)記G(”)為”的所有實(shí)現(xiàn)的集合所有n項(xiàng)可圖序列的集合記作GS對(duì)可圖序列”=(d1，d2，，d。)∈GS，記∥(”)=dd2d。，稱(chēng)口(”)為”的度和另記，(Ⅱ)=mazi：dl≥i，lSiSn)為”的跡記，I(dl～1，，dk—l一1，dkl—l，一，ddk1—1，dd^2，，d。)，若dk≥k，

4、一1(d1一l，，d以一1，ddk1，一，dk一1，dkl，一，d。)，若d≤k一1，則”’稱(chēng)為從”刪掉(1ayingoff)dk后得到的剩余序列對(duì)給定的z∈Ⅳ晶，定義n階矩陣萬(wàn)(z)=(aij)如下：當(dāng)1≤i曼，(”)時(shí)，f1，l≤J≠idi1，％，21o，其它，而當(dāng)，(”)l莖iSn時(shí)，％=‰菇劍”稱(chēng)萬(wàn)(丌)為”的對(duì)角限制極左矩陣對(duì)任意的n階矩陣A=(Ⅱ。)，記7“i=∑墨。aij，sj=∑≥，n。1≤i，JSn，向量(‰r21，h

5、)與(s1】％，s。)分別稱(chēng)為A的行和向量與列和向量由萬(wàn)(”)的定義可知萬(wàn)(”)的行和向量為”記其列和向量為開(kāi)，開(kāi)稱(chēng)為”的校正共軛易知a(”)=一(_)一個(gè)可圖序列”是蘊(yùn)含(強(qiáng)迫)G可圖的，若存在”的實(shí)現(xiàn)含有子圖G(”的每個(gè)實(shí)現(xiàn)都含有子圖G)設(shè)n和l是正整數(shù)，且n≥f≥3稱(chēng)n階簡(jiǎn)單圖G具有性質(zhì)3a，若G含長(zhǎng)為r的圈G，其中r=3，4，，l特別的，當(dāng)l=n時(shí)，也稱(chēng)G是泛圈的稱(chēng)可圖序列”為蘊(yùn)含。af可圖的，若”有一個(gè)實(shí)現(xiàn)具有性質(zhì)。白稱(chēng)可圖序