《離散過程若干問題：結構，模擬和算法》是依託上海交通大學，由吳耀琨擔任項目負責人的面上項目。
基本介紹
- 中文名：離散過程若干問題：結構，模擬和算法
- 項目類別：面上項目
- 項目負責人：吳耀琨
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
許多重要的現實對象， 如傳染病分布，物種演化，網路信息傳播，計算過程模擬，線上資源分配，交通狀態控制，社會觀念的演化，社交網路平衡性等等，需要利用離散數學來建模，對應著一些離散的過程。同時，純粹數學和科學自身的發展中出現的拓撲動力系統分類，量子動力系統各種模型的可控性，非齊次馬氏鏈的動力學刻畫等等也都要求對各種離散過程進行研究。本項目研究各種具有簡單相變規則的圖上動力系統的整體狀態空間描述，研究本原性這一動力學研究中重要概念從一個矩陣到多個矩陣的各種推廣，研究串列動力系統的穩定性，研究不同動力系統之間的模擬的存在性,刻畫,枚舉和相應的算法，研究可以鑑別網路結構的圖上有效搜尋規則的設計，研究區間圖線上染色以及與排序算法有關的偏序集1/3-2/3猜想。我們一方面要揭示一些簡單組合結構如何影響其上的動力學過程，也同時分析和設計一些用來了解組合結構的動力學機制。
結題摘要
本項目對離散過程若干問題取得研究進展，相關結果部分在項目執行期發表。我們獲得限亮西格瑪博弈相空間的完全分類，引入了模2線圖的關鍵概念，發掘了這一新概念的相關算法和代數表現。我們在區間圖和一般圖上系統發展了圖搜尋方法並對其中一類重要的圖上訪問過程進行了仔細考察，由此導出區間圖4步LBFS掃描的認證識別算法，獲得固定一個端點的區間圖上最小路覆蓋問題二次方時間算法，獲得固定兩個端點的區間圖上哈密頓路問題多項式時間算法，並在一篇80多頁的長文中系統引入圖厚度的概念以及利用此概念對大量的圖與區間圖中支撐連通度的問題進行系統考察。我們引入多變數圖論的概念，並在此框架下對基本概念進行了初步整理，並發現單變數與多變數的不同，我們在多變數情形引入的不可約，本原等概念與目前活躍的張量與超圖研究中引入的相關概念不一樣。我們在系統發生組合學的領域中開始取得若干有自己特色的結果，我們從圖上組合流，Lipschitz多面體，基本多面體，定向擬陣，緊支撐等多個角度對樹狀結構和相關結構進行分析，揭示不同數學分支之間的豐富聯繫和獲得對最簡單數學結構的更深入的表示和理解。
