王 福，石 怡，杜智華

（1石河子大學師范學院，石河子832003；2新疆巴州教育局，庫爾勒，841000；3新疆師范大學數學科學學院，烏魯木齊830054）

一類超圖的橫貫

王 福1，石 怡2，杜智華3

（1石河子大學師范學院，石河子832003；2新疆巴州教育局，庫爾勒，841000；3新疆師范大學數學科學學院，烏魯木齊830054）

一般超圖橫貫數τ的上界是不能用匹配數ν的函數來界定的。本文討論了一類存在這種函數的超圖——圈區(qū)間超圖，得到了此類超圖τ與ν之間的關系：τ（H）≤4ν（H），并進一步獲得了圈區(qū)間超圖橫貫數的一些性質。

圈區(qū)間超圖；橫貫數；匹配數

橫貫是超圖中的重要概念，對刻畫超圖的性質具有重要作用。設H是V上的一個超圖，若集合T（?V）與H的每條邊相交，則稱T是H 的一個橫貫。H的橫貫數τ（H）是指H中最小橫貫的基數，簡記為τ。H的匹配數ν（H）是指H中兩兩不相交的最大邊數，簡記為ν。易知ν≤τ［1］。

一般而言，用ν的函數從上方界定τ是不太可能的。然而，1994年 Qing等［2－3］從理論上給出了超圖具有這種性質的一個充分條件。眾多學者也一直在研究存在這種函數關系的超圖類。Gallai得出了區(qū)間超圖滿足τ＝ν；Gyarfas和Lehel［4］證得樹的子樹超圖滿足ν＝τ；Kaiser［5］用拓撲理論證得：若圖G是一條路，超圖H的任一邊是由G的至多d個連通子圖構成的，則有：τ≤（d2－d＋1）ν；Alon［6］改進了Kalser的結果，簡潔直觀地證出相同條件下滿足：τ≤2d2ν；Alon［7］又證得：若圖G 是一棵樹，超圖H的任一邊是由G的至多d個連通子圖構成，則有：τ≤2d2ν；Tar dos［8］結合前人的工作，總結了由樹的至多d個連通子圖構成超圖的v與τ之間關系的三種方法。

本文主要通過橫貫數與分數橫貫數、匹配數與分數匹配數、橫貫數與匹配數之間的關系求得圈區(qū)間超圖的橫貫數與匹配數之間的關系，并進一步獲得了此類超圖橫貫數的一些性質。

1 相關定義與引理

定義1：設V＝｛v1，v2，…，vn｝是依次排列在圈上的有限頂點集。超圖 H＝（E1，E2，…，Em）被稱為V 上的圈區(qū)間超圖，若Ei（i＝1，2，…，m）是V 上的一個連續(xù)子集，且Ei＝V。

定義2［1］：超圖H 的分數橫貫是V上的實函數τ（ν），滿足：

①0≤τ（ν）≤1（?ν∈V），

定義3［1］：超圖H 的分數匹配是一個實函數g（E），滿足：

①0≤g（E）≤1（?E∈H），

Turan引理［2，9］：設G 為階數為n 的圖，若G 中不含r＋1個兩兩不相鄰的頂點，則G中至少有－1）條邊。

引理1：設超圖H有M 條邊，若H中不含k＋1個兩兩不相交的邊，則H中至少有－1）對相交邊。

證明：在超圖H 的基礎上定義圖GH，令V（GH）＝｛xi｜若Ei∈H，則xi∈V（GH）｝；xi與xj之間連一條邊當且僅當Ei與Ej相交?？芍獔DGH的階數為M，且不含k＋1個兩兩不相鄰的頂點。

由Tur dn引理得：

從H′中任取一條邊E′，不妨設v1與v2為在V上排列在首末兩處的頂點，由于與E′相交的邊必包含v1與v2之中一個頂點，故v1與v2中有一個頂點至少被條邊包含，考慮E′本身，結論成立。

引理3：設m和r是兩個正整數，V是圈上的有限頂點集。若R是V上的多重點集，且R中多重點數至多為r m，則存在V的子集S，使得｜S｜≤m，且V－S每個連通分支包含R中的多重點數少于r個。

證明：對圈上每個頂點v∈V，設其重數為x，顯然x≥1。按照下述規(guī)則確定子集S：

3）在圈上不斷重復這一過程，直至行遍V中所有頂點。設滿足條件的頂點集為｛，…｝，則它們構成了子集S。

事實上，如果說明了｜S｜≤m，就完成了證明。假設｜S｜＝m，恰為最末頂點。僅需驗證…＋＜r即可。由條件可知…＋≤r m－r（m－1）－1＜r。

引理4［1］：任一超圖 H 均滿足：v（H）≤v＊（H）＝τ＊（H）≤τ（H）。

2 定理及證明

定理1：設H 是一個圈區(qū)間超圖，則有：「v＊（H）?≤4v（H）。

證明：令k＝v（H），對V（H）中每一個頂點v，設H 的分數匹配g：H→［0，1］滿足（E）≤1，這里g（E）（E∈H）是一個正實數，且H 的分數匹配數v＊（H）＝（E）。令m是一個正整數，且對每條邊E∈H，mg（E）均為整數。設

｜H′｜＝M。

因為H′中不含k＋1個兩兩不相交的邊，由引理1可知：在H′中至少有－1）＞－4）對相交邊。又由引理2知：在V（H）上存在一個頂點v，它被H′中至少條邊包含。由于

由此得到：

「v＊（H）?≤4v（H）。

定理2：設H是一個圈區(qū)間超圖，則有：τ（H）≤「τ＊（H）?。

證明：對H的每條邊E，設H的分數橫貫t：V→［0，1］滿足（v）≥1，這里t（v）（v∈V）是一個正實數，且H的分數橫貫數τ＊（H）＝（v）。

令r是一個整數，對每一個v∈V，rt（v）都是整數；又令R是多重集，它由V中每一個頂點的rt（v）個拷貝組成。由于

那么H每條邊包含R中至少r個多重點。設

則有R中多重點數為：

由引理3可知，存在一個V的子集S，使得

｜S｜≤m＝「τ＊（H）?，

且V－S每個連通分支包含R中的多重點數少于r個，這蘊含著H的每條邊都包含S中至少一個頂點。因為若不然，在H 中就存在一條邊E，它不包含S中的任何一個頂點，這意味著E含在V－S的一個連通分支中，這個連通分支包含R中多重點數少于r個。但若如此，這與E包含R中至少有r個多重點矛盾。故有：

「τ＊（H）?≥｜S｜≥τ（H）。

由定理1和定理2，再結合引理4，可推得重要結論：

定理3：設H是一個圈區(qū)間超圖，則有：τ（H）≤4v（H）。

3 相關性質

結合引理4和定理2，有下面的推論：

推論1：設H是一個圈區(qū)間超圖，則有：τ（H）＝「τ＊（H）?。

定義4：設H是一個超圖，若H 每條邊均含r個頂點，則稱H為r一致超圖。若H中存在一個被所有邊包含的頂點，則稱H 是星。H 中邊的最小基數稱為下秩。

性質2：設H是一個n階圈區(qū)間超圖，若H的下秩為s，則有：τ（H）≤?。

［1］ Berge C.Hypergraphs－Combinational of Finite Sets［M］.Amster dam：Nort h－Holland，1989.

［2］帕赫J，阿格瓦爾P K.組合幾何［M］.丁仁，蘇戰(zhàn)軍，范立平，等譯.北京：科學出版社，2008.

［3］Ding，Sey mour P，Winkler P.Bounding the vertex cover nu mber of a hyper graph［J］.Co mbinatorica，1994，14：23－34.

［4］ Gyarfas A，Lehel J.A Helly－type problem in trees［M］／／Erdos.Co mbinatorial Theory and Its Applications.Amsterdam：North－Holland，1970：571－584.

［5］Kaiser T.Transversals of d－intervals［J］.Discrete Comput，1997，18：195－203.

［6］Alon N.Piercing d－inter val［J］.Discrete Co mput，1998，19：333－334.

［7］Alon N.Covering a hypergraph of subgraphs［J］.Discrete Mathematics，2002，257：249－254.

［8］ Tardos G.Transversals of d－interval－comparing three approaches［J］.Progress in Mathematics，1998，169：234－243.

［9］Bondy J A，Murty S R.Graph Theory With Application［M］.London：Macmillan Press，1976.

Transversal of a Hypergraph

WANG Fu，SHI Yi，DU Zhihua
（1 Department of Mathematics，Teachers College，Shihezi University，Shihezi 832003，China；2 Bazhou Education Bureau，Kuerle 841000，China；3 School of Mat hematics－Physics and Information Science，Xinjiang Nor mal University，Urumqi 830054，China）

In general，transversal nu mberτcannot be bounded fro m above by a f unction of matching nu mberνfor hypergraph.Circle－h(huán)ypergraph is discussed because it satisfies the function，and relevant relationship is revealed bet weenτandνof circle－h(huán)yper graph，that is，τ（H）≤4ν（H）.It follows that several propositions are obtained aboutτ.

circle－h(huán)ypergraph；transversal number；matching number

O157.5

A

1007－7383（2011）03－0378－03

2010－01－08

國家自然科學基金項目（60774073）

王福（1981－），男，講師，從事數學及其應用的研究；e－mail：wf＿tea＠shzu.edu.cn。