關(guān)于一致超圖的導(dǎo)出匹配可擴(kuò)張性.pdf

1、本文我們所考慮的超圖都是有限的，簡單的。
　　 設(shè)H是簡單超圖，如果H的一個(gè)匹配M滿足：H|V(M)=M，那么我們就稱這個(gè)匹配M為導(dǎo)出匹配。特別地，如果H的每一個(gè)導(dǎo)出匹配都包含于H的某個(gè)完美匹配中，那么我們就稱H是導(dǎo)出匹配可擴(kuò)張超圖。更進(jìn)一步地，我們稱一個(gè)連通的超圖H是n可擴(kuò)張的，如果它滿足：
　　 （1)|X(H)|≥rn+r；
　　 （2)H有完美匹配；
　　 （3)對(duì)于H的每一個(gè)匹配M，如果|M|=

2、n，則存在H的一個(gè)完美匹配M*，使得M包含于M*。
　　 超圖的匹配和擴(kuò)張匹配在人員分配問題和最優(yōu)分派問題上有重要的應(yīng)用，特別是特殊的超圖一圖的問題。因此研究超圖的匹配具有重要的意義。
　　 圖的導(dǎo)出匹配和n可擴(kuò)張性最初由K.Cameron和M.D.Plummer在[4]和[3]中分別提出來。因此關(guān)于這方面圖的性質(zhì)，特別是特殊的圖類，已被文獻(xiàn)[6]，[7]，[8]，[9]，[10]，[11]，[15]，[16]，[18]

3、，[19]的作者所研究，受這些結(jié)果的啟發(fā)，我們給出了超圖的關(guān)于導(dǎo)出匹配和可擴(kuò)張性的一些性質(zhì)，關(guān)于超圖的其他的一些性質(zhì)（如關(guān)于他們積的一些性質(zhì)）在這篇論文中也將被提及，下面是我們的主要結(jié)果：
　　 （1)如果H是一個(gè)具有|X(H)|個(gè)定點(diǎn)的r一致超圖，n為一個(gè)大于等于2的正整數(shù)，這里，如果|X(H)|是r的倍數(shù)，而且H是一個(gè)n可擴(kuò)張的超圖，那么H也是一個(gè)(n-1)可擴(kuò)張的超圖。
　　 （2)如果H是一個(gè)n可擴(kuò)張的超圖，而且

4、H不含有導(dǎo)出匹配M使得|M|>n，那么H就是導(dǎo)出匹配可擴(kuò)張的超圖。
　　 （3)如果H是導(dǎo)出匹配可擴(kuò)張超圖，頂點(diǎn)集為X，而且滿足：X*真包含于X,Y*真包含于X,X*∪Y*∈H，使得：d(x)=2,d(y)=2，其中對(duì)任意x,y,x∈X*，y∈Y*那么Hx\(X*∪Y*)是導(dǎo)出匹配可擴(kuò)張超圖。
　　 （4)對(duì)于任意超圖H和任意一個(gè)正整數(shù)r，若令K<'r><,n>是r一致完全超圖，其中n=rk,k為一正整數(shù)，那么H×K<'