類競賽圖的結構性質研究

《類競賽圖的結構性質研究》是依託山西大學，由王瑞霞擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：類競賽圖的結構性質研究
• 項目類別：青年科學基金項目
• 項目負責人：王瑞霞
• 依託單位：山西大學

項目摘要

競賽圖是得到研究最早且結果最豐富的一類有向圖，其理論和方法已經滲透到許多學科和領域。競賽圖的推廣圖，也稱為類競賽圖，包含k準傳遞有向圖和弧局部內半完全有向圖等。它是近年來有向圖領域的研究熱點之一。圖的特徵刻畫能夠對研究它的其它性質和參數提供幫助；Hamilton性問題與有向圖中的最長路、最長圈、泛圈性等問題有一定的聯繫，而且Hamilton性問題本身的計算複雜性也是值得關注的；核和王與有向圖的直徑、半徑等問題密切相關。所以刻畫圖的特徵，研究其Hamilton性以及圖中的核和王等問題是有意義的。本項目將綜合運用圖論、組合最佳化及數學規劃的方法來研究類競賽圖的上述問題，具體如下：首先刻畫k準傳遞有向圖和弧局部內半完全有向圖的結構特徵；其次研究k準傳遞有向圖和弧局部內半完全有向圖的Hamilton性；最後解決“k準傳遞有向圖中存在k+1核”這個猜想，並研究k準傳遞有向圖中k王的存在性。

結題摘要

類競賽圖，也稱為競賽圖的推廣圖，是有向圖中一個非常重要的圖類，擁有大量的難題和猜想。本項目主要研究了類競賽圖的結構性質，並取得了下述成果： 1. 研究類競賽圖的Hamilton性。我們證明了當k為大於等於4的偶數時，直徑大於等於k+2的強連通k準傳遞有向圖中存在Hamilton路；給出了平衡二部有向圖中存在Hamilton圈的控制對條件；部分解決了二部有向圖中關於最長圈的一個猜想。 2. 刻畫類競賽圖的結構。我們刻畫了直徑大於等於k+2的強連通k準傳遞有向圖的結構特徵。 3. 研究類競賽圖中(k+1)核和k王的存在性。證明了“k準傳遞有向圖中存在k+1核”這個猜想；給出了k準傳遞有向圖中存在k王的充要條件；給出了強連通的k傳遞有向圖中存在k-1核的充要條件。 本項目的研究在一定程度上推動了類競賽圖的研究進展。項目執行期間共發表學術論文10篇，參加學術會議6次，培養碩士研究生2名。