圖的正交因子分解及具有某些性質的因子.pdf

1、山東大學博士學位論文圖的正交因子分解及具有某些性質的因子姓名：馮好娣申請學位級別：博士專業(yè)：運籌學與控制論指導教師：劉桂真2000.3.1圖的正交因子分解及具有某些性質的因子摘要本文考慮的圖均為有限無向簡單圖對于一個圖G，我們用y(G)和E(G)分別表示它的頂點集和邊集，時任意的z∈y(G)，我們用dG(口)表示z在G中的次數(shù)設g和，是定義在州G)上的兩個整數(shù)值西數(shù)且對任意的z∈y(G)，有F(。)S，(z)剮圖G的一個(g，，)一因子

2、是指G的一個支棒子圖F使得對任意的$∈y(G)，有9(z)≤如(z)S，(茁)如果對所有的?！蕐(G)，有g(。)=a，，(彳)=6，則該(9，，)一因子稱為G的一個(Ⅱ，6J一因子；如果g扣)=，0)，則該(g，，)～因子稱為G的一個，一因子；如果Pp)=，扛)=磚剮稱該因子為G的一個％一因子，如果一個圖G本身是一個(g，，)一因子，剮稱G為一個(9，，)一圖類似她，可以定義【Ⅱ，6卜圖，，一圖和k一圖等令日是G的一個子圖，如果日本身

3、是一個(9，，)一圖，則稱日是G的一個(g，r)一子圖類似地可定義G的k，6J一子圖，，一子凰I和七一予圖圖G的一個(9，，卜因子分解，=R，足，，，k)是指把G的邊集E(G)分劃成m個邊不交的(g，，)一因子月，B，，F(xiàn)’仇類似地，可以定義【d，6】一因子分解，，_因子分解，％一因子分解等設奄l，島，，k是m個整數(shù)如果把G的邊集E(G)分劃威邊不交的fo，b卜因子日，【o，矧一因子見，fo，k卜因子矗，則，=最，B，，R、稱為G的一個

4、【o，女jl，一因子分解令日是G的一個有mr條邊的子圖，簡稱圖G的mr_予圖圖G的一個因子分解蘆=R，馬，，jm)稱做與日r～正交(或當r=1時稱為正交)如果每個最，1≤i≤竹l恰好與日有r條公共邊令日是圖G的一個mr_子圖如果對日舯任一平均分劃玩，瑪，，髓。，其中I玨=r，1≤i≤m且日in瑪=口如果i≠J，都存在G的一個因子分解F=R，B，，fkl使得E(甄)∈E(只)，1Si≤m，貝!|稱，是與日隨機(m，r)一正交的，而G被稱作

5、隨機(m，r)一正交的0，，)一可因子化圖其它定義和術i爵見文獻f6)圖的因子理論是圖論中研究的主要問題之一自從n“e分別于1947年和1952年給出了因子理論的兩個基本定理后，尤其懸從L_Lo盹觴在1970年給出了hn一因子存在性的判定準則后，對圖的因子的研究才逐漸活躍起來圖的正交因子分姆問題是近年來粵BA18pach等人提出的薪問蔓％弦文主要討論了圖的正交因子分解問題，對具有某些性質的因子也稍有研究本文第一章簡單介紹了因子理論和正交