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

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

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

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

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

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

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