圖參數(shù)和滿足規(guī)定性質(zhì)的因子的存在性.pdf

1、匹配理論，或更廣的因子理論，是圖論的—個(gè)基本研究領(lǐng)域．因子理論在最優(yōu)化、網(wǎng)絡(luò)設(shè)計(jì)、社會(huì)經(jīng)濟(jì)等領(lǐng)域中均有許多現(xiàn)實(shí)的應(yīng)用．自從Lovasz和Plummer的經(jīng)典著作《匹配理論》問世二十多年以來，因子理論蓬勃發(fā)展，取得了許多新的和有趣的進(jìn)展，其中包括對(duì)各類因子的刻畫．通常來說，驗(yàn)證圖參數(shù)條件比驗(yàn)證其他刻畫條件更為簡(jiǎn)單，并且圖參數(shù)條件從不同角度反映了圖的結(jié)構(gòu)和性質(zhì)，因此很多已有結(jié)果都試著探究圖參數(shù)和因子存在性之間的關(guān)系，用圖參數(shù)條件來刻畫各類因

2、子．本文主要考慮了滿足規(guī)定性質(zhì)的因子的存在性問題，研究這些因子與韌度、捆綁數(shù)和特征值這三個(gè)圖參數(shù)之間的關(guān)系，本文有兩個(gè)主要任務(wù)，其一是用韌度或者捆綁數(shù)條件來刻畫具有包含/不包含性質(zhì)的因子；其二是討論特征值和諸如1-因子、[1,n]-奇因子、星因子這樣的特殊因子之間的關(guān)系。此外，本文還研究了一些特殊圖類中滿足規(guī)定性質(zhì)的1-因子的存在性問題．
　　 整篇論文的架構(gòu)如下．第一章先介紹了本文用到的一些符號(hào)和術(shù)語．1.2節(jié)致力于介紹圖參數(shù)

3、和因子的研究背景。首先我們給出了以韌度或捆綁數(shù)為條件的關(guān)于f-因子和[a，b]-因子的刻畫，然后我們例舉出一些已知結(jié)果，這些結(jié)果與韌度或捆綁數(shù)相關(guān)，也與具有邊（或者頂點(diǎn)）包含/不包含性質(zhì)的因子相關(guān)．最后，我們簡(jiǎn)要給出了本文的基本框架。
　　 第二章主要給出了基于韌度的滿足規(guī)定性質(zhì)的f-因子存在的充分條件．對(duì)于—個(gè)含有至少五個(gè)頂點(diǎn)的2-堅(jiān)韌圖G和—個(gè)函數(shù)f：V(G)→{1，2}，任給兩條邊el，e2∈E(G)，我們證明了G中存在—

4、個(gè)包含e1和e2的f-因子；—個(gè)不包含e1和e2的f-因子；以及—個(gè)包含e1、且不包含e2的f-因子。2.2節(jié)討論了滿足給定性質(zhì)的1-因子．首先，我們介紹了一些關(guān)于k-因子和圖參數(shù)的相關(guān)結(jié)果，以及具有邊包含性質(zhì)（可擴(kuò)性）或頂點(diǎn)不包含性質(zhì)（因子臨界性）的1-因子的相關(guān)結(jié)果．然后，我們主要研究了乘積圖中具有邊包含性質(zhì)和頂點(diǎn)不包含性質(zhì)的1-因子的存在性問題，即乘積圖的可擴(kuò)性和因子臨界性．在2.3節(jié)，我們給出了一些關(guān)于f-因子的后續(xù)研究問題，第

5、三章致力于研究[a，b]-因子中的類似問題．3.1節(jié)研究了韌度條件下滿足規(guī)定性質(zhì)的[a，b]-因子，我們證明了如下結(jié)果：對(duì)于一個(gè)不完全圖G，如果其韌度t(G)≥（a一1）＋a/b，其中a,b是滿足b＞a＞1的整數(shù)，那么對(duì)于任意給定的兩條邊e1和e2，存在—個(gè)包含e1，e2的[a，b]-因子；—個(gè)包含e1且不包含e2的[a,b]-因子；以及一個(gè)不包含e1，e2的[a，b]．因子，除非a=2且e1和e2具有一個(gè)公共頂點(diǎn)．對(duì)于完全圖，我們同樣

6、得到了一個(gè)類似結(jié)果．3.2節(jié)討論了用捆綁數(shù)刻畫滿足規(guī)定性質(zhì)的[a，b]-因子的問題．在3.3節(jié)，我們首先給出了包含任意七條獨(dú)立邊的[1，2]-因子存在的充分條件，然后考慮了在韌度條件下，包含任意一條邊的[2，b]-因子的存在性問題，在本章結(jié)尾，我們給出了兩個(gè)可以繼續(xù)研究的問題。
　　 第四章討論了特征值和[1，n]-奇因子之間的聯(lián)系，以及Laplacian特征值和星因子之間的聯(lián)系．一直以來，圖的特征值被廣泛地用來研究圖的性質(zhì)和圖