《可帶負權的圖的p-中心和p-中位問題》是依託上海大學，由康麗英擔任項目負責人的面上項目。
基本介紹
- 中文名：可帶負權的圖的p-中心和p-中位問題
- 項目類別：面上項目
- 項目負責人：康麗英
- 依託單位：上海大學
中文摘要,結題摘要,
中文摘要
圖的中心和中位問題是圖論與組合最最佳化理論研究的重要內容，它在選址、通訊、複雜網路和環境科學等領域中有著廣泛的套用。與經典的中心和中位問題比較，國際上最近提出的可帶負權的圖的中心和中位問題在實際中更具有普遍意義。本項目側重以圖論和組合最最佳化為工具來開展對可帶負權的圖的中心和中位問題的研究，討論其算法實現問題。研究的主要內容為：(1)在具有特殊結構的賦權圖上，設計該類問題的多項式時間算法；(2)探索這些問題在一般賦權圖上的近似算法實現。在研究方法上側重圖的結構性質的深入分析，並充分結合組合最最佳化方法，力爭在理論方法上有新的突破。本課題將首次考慮該類問題的近似算法。對這些問題的研究，將推動圖論、組合最最佳化、選址科學和複雜網路的交叉研究與發展，同時對一些實際問題的解決也具有一定的理論指導意義。
結題摘要
圖的中心(center)和中位(median) 問題是選址科學的兩個核心問題，也是圖論與組合最最佳化理論研究的重要內容，在通訊、複雜網路、運輸和環境科學中有著廣泛套用。國際上最近提出的可帶負權的圖的中心和中位問題在實際中更具有普遍意義。本項目側重以圖論和組合最最佳化為工具來開展對可帶負權的圖的中心和中位問題的研究，討論了其算法實現問題。我們取得的主要成果如下：(1)關於p-maxian問題，討論了對塊圖、區間圖和仙人掌圖幾類圖的p-maxian問題。對具有單位邊長的塊圖p-maxian問題，證明了除3階完全圖外，塊圖的p-maxian問題是線性時間可解的；其次，給出了具有任意權區間圖的p-maxian問題的線性時間算法；對區間圖的任意權2-中位問題,若目標為MWD和WMD目標，分別給出了時間O(n2)的多項式算法；最後，我們證明了仙人掌圖的2-maxian問題具有時間為O(n2)的多項式時間算法。(2)討論了客戶具有子圖結構的可帶負權p-中位問題，對具有單位邊長塊圖的1-中位問題，若中位限制在圖的頂點上，我們提出了該問題的一個線性時間算法；對客戶具有子樹結構的p-中位問題, 分別給出了樹的1-中位問題和2-中位問題的多項式時間算法.（3）討論了可帶負權的p-中心問題的研究。p-中心問題是指在網路中放置p個設施，使得每個客戶到達最近設施的最大權距離最小。證明了塊圖的無權1-中心問題是線性時間可解的。對服務設施以一定機率失效的選址問題，證明了區間圖的備份2-中心問題是線性時間可解的。
