關于圖的因子與分數(shù)因子的若干結果.pdf

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

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