圖的正交因子和隨機正交因子分解.pdf

1、山東大學(xué)碩士學(xué)位論文圖的正交因子和隨機正交因子分解姓名：馮麗申請學(xué)位級別：碩士專業(yè)：運籌學(xué)與控制論指導(dǎo)教師：劉桂真20030410山東大學(xué)碩士學(xué)位論文圖的正交因子和隨機正交因子分解馮麗(山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，濟南250100)中文摘要本文考慮的圖均為有限無向簡單圖對于一個圖G，我們用v(c)和E(G)分別表示它的頂點集和邊集對任意的z∈y(G)，我們用dG(石)表示正在G中的次數(shù)設(shè)9和，是定義在V(G)上的兩個整數(shù)值函數(shù)且對任意的

2、正∈y(G)，有9(z)≤，(z)則圖G的一個(9，，)一因子是指G的一個支撐子圖F使得對任意的?！蕐(G)，有g(shù)(z)≤dF(T)S，(芏)如果對所有的z∈y(G)，有9(芷)=口，／(x)=6，則該(g，I)因子稱為G的一個【o，卅一因子；如果9(z)=，(z)，則該(g，，)一因子稱為G的一個，一因子；如果9(z)=，(霉)=k，則該(g，／)因子稱為G的一個％一因子如果一個圖G本身是一個白，，)一因子，則稱G為一個(9，，)一圖

3、類似地，可以定義【a，6】一圖，，一圖和k一圖等令日是G的一個子圖，如果日本身是一個(g，，)一圖，則稱日是G的一個(g，，)一子圖類似地可定義G的[a，講一子圖，，一子圖和k一子圖圖G的一個(9，，)一因子分解，=日，B，，最就是將G的邊集E(G)分成邊不交的(g，，)一因子Fl，如，，最類似地，可以定義【0，6卜因子分解，，一因子分解，后一因子分解等若日是圖G的一個子圖，如果G的因子分解蘆=最，乃，，最滿足fE(H)nE(墨)f=I

4、(2≤f≤七)，則稱，與日正交很明顯，G的因子F如果有fE(H)nE(F)I=1，則F與日正交G的有k條邊的子圖稱為G的女一子圖若Ⅳ是圖G的一個kr子圖，G的一個(g，I)因子分解，=F1，如，，F(xiàn)k，如果滿足IE(H)nE(只)J=r(1≤i≤七)，則稱，與日r一正交如果對邊集E(H)的任意劃分A1，A2，，A≈)滿足JAiI=r存在一個(g，I)因子分解，=Fl，尼，，F(xiàn)k)，使得A￡只，1≤iSk，則我們稱G有一個(g，，)一因子

5、分解隨機r一正交于日可以看出，隨機1一正交等價于l一正交，1一正交也稱為正交其它定義和術(shù)語可見文獻[18】圖的因子理論是圖論中研究的主要問題之一自從Tutte分別于1947年和1952年給出了因子理論的兩個基本定理后，尤其是從LLovdsz在1970年給出了(g，，)一因子存在性的判定準(zhǔn)則后，對圖的因子的研究才逐漸活躍起來圖的正交因子分解問題是近年來由BAlspach等人提出的新聞題本文主要討論了圖的正交因子分解問題，對隨機正交因子分解