圖的度序列和競賽矩陣.pdf

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

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

3、d：≥≥d?！?的整數(shù)序列”=(dl，d2，，如)的集合記作NS。設(shè)”∈NS。，稱”是可圖的，若”是n階簡單圖的度序列這樣的圖稱作”的一個實現(xiàn)記G(”)為”的所有實現(xiàn)的集合所有n項可圖序列的集合記作GS對可圖序列”=(d1，d2，，d。)∈GS，記∥(”)=dd2d。，稱口(”)為”的度和另記，(Ⅱ)=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，則”’稱為從”刪掉(1ayingoff)dk后得到的剩余序列對給定的z∈Ⅳ晶，定義n階矩陣萬(z)=(aij)如下：當(dāng)1≤i曼，(”)時，f1，l≤J≠idi1，％，21o，其它，而當(dāng)，(”)l莖iSn時，％=‰菇劍”稱萬(丌)為”的對角限制極左矩陣對任意的n階矩陣A=(Ⅱ。)，記7“i=∑墨。aij，sj=∑≥，n。1≤i，JSn，向量(‰r21，h

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