群連通度和子圖存在性及相關(guān)問題的研究

本項目主要研究圖論中整數(shù)流、群連通度問題、歐拉子圖的存在即網(wǎng)絡(luò)容錯性及相關(guān)問題，它包括圖的處處非零的3-流問題、群連通度（Group connectivity）、 群著色問題及相關(guān)問題。 著名數(shù)學(xué)家Tutte教授（1954）提出的3-流猜想(Bondy和Murty的《Graph with applications》中未解決問題48):任何4-邊連通圖有非零3-流: 法國數(shù)學(xué)家 Jeager教授(1992) 把整數(shù)流問題推廣到群連通度問題。而群著色問題作為群連通問題的對偶問題提出來的。 平面圖的染色是與平面上的整數(shù)流等價。因此， 整數(shù)流問題、群連通問題和染色問題是圖論研究的主流問題之一。 我們對對這些問題進行深入、系統(tǒng)的研究，取的一批重要成果。我們刻畫了度條件與群連通性、 度系列與群連通性、禁用子圖與群連通性、平面圖的群著色。因為平面上整數(shù)流的問題和染色問題是等價的， 因此我們研究了平面圖的著色以及強邊著色等問題。我們還研究了線圖的Hamilton性、度條件與歐拉連通子圖的存在性, 因子的存在性和網(wǎng)絡(luò)的容錯性等問題。 2100433B

1954年，Tutte教授在研究四色問題時，引進了整數(shù)流的概念。四色定理等價于任何平面圖有處處非零4流。后來人們發(fā)現(xiàn)整數(shù)流問題與圈覆蓋等圖論問題有緊密的關(guān)系。1992年, Jaeger教授將整數(shù)流的概念推廣為群連通度(group connectivity），群著色 (group coloring)作為群連通度的對偶提出來。群連通度本身在研究整數(shù)流時，有應(yīng)用價值。Thomassen在1986年提出任何4-邊連通的線圖是Hamilton的。任何超歐拉圖的線圖是Hamilton的。因此，超歐拉圖對研究Thomassen這個猜想有應(yīng)用價值。超歐拉圖、Hamilton圈的研究 本身就是子圖的存在性問題。本項目的主要內(nèi)容是：研究群連通度及相關(guān)問題， 包括群著色、3-流問題等；研究子圖的存在性, 包括線圖Hamilton性、超歐拉圖等；作為子圖存在性的應(yīng)用，研究算法的容錯性。

有向圖的結(jié)構(gòu)問題是圖論的一個重要的研究領(lǐng)域，而泛弧和點不相交圈的存在性是有向圖結(jié)構(gòu)問題的一個重要分支，它和圖的因子理論及染色問題等有著非常密切的關(guān)系。本項目主要研究有向圖的泛弧和點不相交圈的存在性，關(guān)于這個課題還有很多問題沒有解決。首先，本項目研究強連通、圈連通等條件下有向圖泛弧的存在性，深入討論有向圖中泛弧的數(shù)量，力求找到盡可能多的泛弧。其次，我們還研究有向圖的另一種重要結(jié)構(gòu)，即有向圖中點不相交圈的存在性，試圖解決或部分解決Bermond-Thomassen 猜想的相關(guān)問題。最后，我們考慮圈的長度，研究有向圖中點不相交的具有指定長度的圈，力求尋找最好的度條件。本項目的研究涉及到組合數(shù)學(xué)，計算機網(wǎng)絡(luò)，交通運輸及生物信息學(xué)等學(xué)科，問題的解決對組合數(shù)學(xué)，圖論，計算機網(wǎng)絡(luò)及交通運輸業(yè)等的發(fā)展都有重要的意義。