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

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

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

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

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