《連通圖中的可收縮子圖問題》是依託南京航空航天大學，由崔慶擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：連通圖中的可收縮子圖問題
- 項目類別：青年科學基金項目
- 項目負責人：崔慶
- 依託單位：南京航空航天大學
項目摘要,結題摘要,
項目摘要
圖的連通性是圖論研究的核心課題之一。Tutte是此領域的開創者之一，並做出了許多奠基性的工作。過去二十多年來，國際著名圖論學家Robertson和Seymour發展了圖子式理論，該理論在計算機科學和其他數學領域有著廣泛且重要的套用。收縮邊（與收縮連通子圖）是圖子式理論的主要思路。本項目旨在對k連通圖（特別是5連通圖）找到好的簡化技巧。例如：在k連通圖中是否存在可收縮（連通）子圖，在所期望的可收縮（連通）子圖不存在時，能否得到有用的結構信息。我們計畫研究並刻畫一些特殊圖類，如臨界k連通圖等。另外，我們將深入研究收縮子圖方法在Malkevitch關於4連通平面圖具有泛圈性的猜想、圖論算法以及網路可靠性等問題中的套用。這些問題都是圖的連通性研究中的前沿課題，對這些問題進行系統的研究，將有助於圖的連通性理論的進一步發展。
結題摘要
圖的連通性理論是圖論研究的核心課題之一，在計算機科學和其他數學領域有著廣泛且重要的套用，近年來吸引了國內外眾多圖論學者的研究興趣。本項目只要針對k連通圖中可收縮子圖的存在性問題展開了深入研究。首先，我們證明了如果一個k連通圖不包含導出4-圈和某些特殊圖作為子圖，則一定含有一個可收縮三角形或者一條有3個頂點的可收縮路，改進了Fujita和Kawarabayashi的結果。其次，我們研究了臨界k連通圖的刻畫問題，得到了關於臨界k連通圖的一些有用的結構信息。此外，我們刻畫了給定獨立數時周長達到最小的所有k連通圖，從而回答了著名圖論學家Saito提出的一個問題。這些問題都是圖的連通性研究中的前沿課題，對這些問題進行系統的研究，將有助於圖的連通性理論的進一步發展。
