關(guān)于圖的因子與分?jǐn)?shù)因子的若干結(jié)果.pdf

1、二十世紀(jì)六十年代以來,圖論已經(jīng)成為發(fā)展最快的數(shù)學(xué)分支之一.應(yīng)用圖論來解決運(yùn)籌學(xué)、化學(xué)、生物學(xué)、網(wǎng)絡(luò)理論、信息論、控制論、博弈論和計(jì)算機(jī)科學(xué)等學(xué)科問題已顯示出極大的優(yōu)越性.圖論在各個學(xué)科分支、工程技術(shù)領(lǐng)域及社會科學(xué)有著廣泛的應(yīng)用,它作為組合數(shù)學(xué)中的一個分支,受到了各方面的普遍重視.因子理論是圖論的一個重要分支,在圖論研究中得到了極大關(guān)注.在日常生活中,許多諸如編碼設(shè)計(jì)、積木設(shè)計(jì),計(jì)算機(jī)網(wǎng)絡(luò)的文件傳輸、進(jìn)度表等關(guān)于運(yùn)籌和網(wǎng)絡(luò)設(shè)計(jì)問題都涉及到

2、圖的因子,因子分解和正交因子[2].其中,文件傳輸問題可以模擬為因子和(O,f)-因子分解(或f-染色),拉丁方塊和空間方塊的設(shè)計(jì)則涉及到圖的因子和正交因子問題.本文所考慮的圖都是有限簡單圖.設(shè)G是一個圖,V(G)是頂點(diǎn)集,E(G)是邊集.對V(G)的子集S,G-S表示由V(G)\S導(dǎo)出的子圖,G[S]表示由S導(dǎo)出的子圖.圖G的點(diǎn)割是V(G)的子集S,使得G-S是不連通的.K-點(diǎn)割是有K個元素的點(diǎn)割.G的連通度k(G)是使得G有k-點(diǎn)割