發(fā)布時間：2020-04-02 23:11

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

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

本文編號：2612562