【摘要】：在過(guò)去的半個(gè)世紀(jì)里,圖論的研究隨著科學(xué)技術(shù)的飛速發(fā)展而呈現(xiàn)出異常活躍的趨勢(shì).對(duì)圖的控制數(shù)、匹配數(shù)和橫貫數(shù)的研究是圖論研究的一個(gè)重要方向,在計(jì)算機(jī)科學(xué),生物系統(tǒng),網(wǎng)絡(luò)通訊,人工智能以及管理科學(xué)等學(xué)科領(lǐng)域中得到了廣泛地應(yīng)用.超圖是最一般又最復(fù)雜的離散結(jié)構(gòu),可以看做是一般圖(無(wú)向圖)的一類自然推廣.一般圖上的關(guān)于控制數(shù)、匹配數(shù)和橫貫數(shù)的問(wèn)題已經(jīng)得到了廣泛而深入的探討,但是超圖上的相關(guān)問(wèn)題是近些年來(lái)才被提出并得到研究的.在本文中,我們主要考慮了超圖的控制數(shù)和匹配數(shù)之間的關(guān)系,并刻畫了相關(guān)的極值超圖.首先,我們給出了超圖上控制數(shù)的一個(gè)上界,該上界與其匹配數(shù)相關(guān).眾所周知,控制數(shù)γ(H),匹配數(shù)v(H)和橫貫數(shù)T(H)是超圖的三個(gè)重要參數(shù).Ryser猜想是討論關(guān)于r-部超圖的橫貫數(shù)和匹配數(shù)之間關(guān)系的著名猜想,它表述為:對(duì)于任何一個(gè)r-部超圖,都有T(H)≤(r-1)v(H).這一猜想是一個(gè)很困難的問(wèn)題,對(duì)r ≥ 4的情形始終沒(méi)有實(shí)質(zhì)性的進(jìn)展.受Ryser猜想的啟發(fā),我們考慮一致超圖上控制數(shù)與匹配數(shù)之間的關(guān)系,證明了:如果H是一個(gè)r-一致超圖,那么控制數(shù)和匹配數(shù)之間滿足關(guān)系γ(H)≤(r-1)v(H),并通過(guò)構(gòu)造一族超圖說(shuō)明超圖的控制數(shù)的這一上界是緊的.其次,我們考慮達(dá)到上界γ(H)=(r-1)v(H)的極值交超圖.由于超圖的結(jié)構(gòu)十分復(fù)雜,在一般情形下刻畫滿足γ(H)=(r-1)v(H)的超圖顯得非常困難.因此我們將目光聚焦在結(jié)構(gòu)相對(duì)簡(jiǎn)單的線性交超圖上.利用線性交超圖的特性,我們通過(guò)3-階有限射影平面構(gòu)造出所有滿足γ(H)=4的5-一致線性交超圖.最后,我們研究了v(H)≥ 2的極值線性超圖.回溯現(xiàn)有的滿足等式γ(H)=(r-1)v(H)的超圖,可以發(fā)現(xiàn)當(dāng)r3時(shí)所刻畫的極值超圖都局限在交超圖(v(H)=1)上,并且刻畫已十分復(fù)雜.我們給出了 v(H)≥2的線性超圖的一些特性,并刻畫了滿足γ(H)=6的2-匹配4-一致線性超圖.
【圖文】：

４＂逡逑肩逡逑圖３．１．１示例[V逡逑引理３．１．４邋（邋［３４］）如果超圖丑ｅ邐那么丑＇中的任意一條邊至逡逑多含有一個(gè)度４點(diǎn)，并且△（丑＇）＝ｒ－１．逡逑引理３．１．５邋（［３４］）如果丑ｅ￡ｒ（ｒ＞３），那么片有一下一些特征：逡逑（ｉ）邐ｎ（Ｈ＇）邋＝邋（ｒ邋—邋ｌ）２邋—邋（ｒ邋—邋１）邋＋邋１．逡逑（ｉｉ）邐７（丑0邋＝邋１，并且把中的度－（ｒ－邋１）點(diǎn)都是Ｆ的一個(gè)控制集？逡逑（ｉｉｉ）邐３（ｒ邋—邋２）邋＜邋ｍ｛Ｈ＇）邋＜（ｒ邋—邋ｌ）２邋—邋（ｒ邋—邋１）邋＋邋１．逡逑進(jìn)一步地，我們有以下這個(gè)引理．逡逑引理３．１．６設(shè)超圖丑■？如果ｒ邋＞邋５，那么有ｍ（／Ｔ）邋２邋３ｒ－５．逡逑證明．根據(jù)引理３．１．５有ｍ（／Ｔ）２３ｒ－６．用反證法證明引理３．２．１的結(jié)逡逑論？假設(shè)ｍ（Ｈ＇）邋＝邋３ｒ邋－邋６？根據(jù)引理３．１．４可知，存在一個(gè)點(diǎn)ｗ邋＃rP罰ǔ螅В，

本文編號(hào)：2612562