《圖的廣義（邊）連通度若干問題的研究》是依託浙大寧波理工學院，由李莎莎擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖的廣義（邊）連通度若干問題的研究
- 項目類別：青年科學基金項目
- 項目負責人：李莎莎
- 依託單位：浙大寧波理工學院
項目摘要,結題摘要,
項目摘要
連通度是圖論學科中最基本的概念之一，關於連通度，已經有了許多優美、強大的結論。圖的廣義連通度，是由Chartrand等人提出的，它是連通度概念的一個自然、漂亮的推廣。類似於廣義連通度，最近李學良教授等又提出了廣義邊連通度的概念，它是邊連通度概念的一個推廣。廣義（邊）連通度與圖論中的一些重要問題，例如生成樹打包問題、斯坦納樹打包問題等有著緊密的聯繫，已經吸引了越來越多的研究者的關注和興趣。 . 本項目將研究廣義（邊）連通度相關問題的複雜性，力爭給出確定圖的廣義邊連通度的多項式時間算法或證明是NP-困難的；從刻畫對κ_{3}=2是極小的圖入手，刻畫κ_{3}，λ_{3}等於1或2的極圖；研究不等式κ_{k}≤κ_{k-1}成立的充分條件甚至是充要條件，其中3≤k≤n；通過研究凱萊圖，對稱圖等圖類的結構性質，努力確定這些特殊圖類的廣義（邊）連通度的精確值。
結題摘要
連通度是圖論學科中最基本的概念之一，關於連通度，已經有了許多優美、強大的結論。圖的廣義（邊）連通度是（邊）連通度概念的一個自然、漂亮的推廣。廣義（邊）連通度不僅與圖論中的一些重要問題，例如生成樹打包問題、斯坦納樹打包問題等有著緊密的聯繫，而且在實際生活中也有著重要的套用。因此，對廣義（邊）連通度的研究是非常有意義的。 本項目在國家自然科學基金委的資助下，經項目組成員一致努力，完成了項目預期的各項主要目標。目前，項目組得到的主要結果有： (1)我們研究了對二部圖判定rc(G)(rvc(G))的複雜性問題。 (2)我們研究了極小2-連通且κ_{3}=2的圖的結構。另外，我們得到了一些可逆操作，這些操作均保持了“κ_{3}=2”，這對研究其它問題有重要意義及作用。 (3)我們研究了由星生成的凱萊圖Sn和由路生成的凱萊圖Bn的廣義3-連通度，得到Sn和Bn的廣義3-連通度均為n-1。 (4)我們對社交網路相關問題進行了研究。提出了以影響-距離為基礎的影響者檢測問題，並提供了一個3-近似算法。其次我們提出了用最大似然估計法檢測影響者，並證明了對有向無圈圖可以在多項式時間內得到最優的MLE。
