圖的正交因子和隨機(jī)正交因子分解.pdf

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

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

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

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

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