中国韩国日本在线观看免费,A级尤物一区,日韩精品一二三区无码,欧美日韩少妇色

當前位置:主頁 > 科技論文 > 數(shù)學論文 >

超圖的匹配數(shù)和控制數(shù)及其相關極值超圖刻畫

發(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-一致線性超圖.
【圖文】:

超圖,射影平面,引理,用圖


4"逡逑肩逡逑圖3.1.1示例[V逡逑引理3.1.4邋(邋[34])如果超圖丑e邐那么丑'中的任意一條邊至逡逑多含有一個度4點,并且△(丑')=r-1.逡逑引理3.1.5邋([34])如果丑e£r(r>3),那么片有一下一些特征:逡逑(i)邐n(H')邋=邋(r邋—邋l)2邋—邋(r邋—邋1)邋+邋1.逡逑(ii)邐7(丑0邋=邋1,并且把中的度-(r-邋1)點都是F的一個控制集?逡逑(iii)邐3(r邋—邋2)邋<邋m{H')邋<(r邋—邋l)2邋—邋(r邋—邋1)邋+邋1.逡逑進一步地,我們有以下這個引理.逡逑引理3.1.6設超圖丑■?如果r邋>邋5,那么有m(/T)邋2邋3r-5.逡逑證明.根據引理3.1.5有m(/T)23r-6.用反證法證明引理3.2.1的結逡逑論?假設m(H')邋=邋3r邋-邋6?根據引理3.1.4可知,存在一個點w邋#rP罰ǔ螅В,

本文編號:2612562

資料下載
論文發(fā)表

本文鏈接:http://www.lk138.cn/kejilunwen/yysx/2612562.html


Copyright(c)文論論文網All Rights Reserved | 網站地圖 |

版權申明:資料由用戶27b0d***提供,本站僅收錄摘要或目錄,作者需要刪除請E-mail郵箱bigeng88@qq.com