WikiEdge:ArXiv-2409.05678v1/methods

編輯

這篇論文的工作部分詳細介紹了如何研究平面n, m-圖的類比四色定理問題。以下是這部分的主要內容：

1. (n, m)-圖的定義：
   • 定義了(n, m)-圖的概念，即一個圖包含n種類型的弧和m種類型的邊，每種類型的弧或邊用不同的符號標記。
2. (n, m)-完全圖的性質：
   • 研究了(n, m)-完全圖的性質，這是沒有環路或多重邊的圖，並且任意兩個頂點的識別會導致具有不同標籤的環路或並行鄰接。
3. 平面(n, m)-完全圖的頂點數上界：
   • 證明了對於所有(n, m) ≠ (0, 1)，平面(n, m)-完全圖的頂點數不能超過3(2n+m)^2 + (2n+m) + 1，並且這個界限是緊確的。
4. 特殊2-路徑和鄰接關係：
   • 使用特殊2-路徑的概念來表徵(n, m)-完全圖，即如果兩個頂點通過特殊2-路徑相連，則它們必須相互「看見」。
5. 支配數和區域劃分：
   • 利用圖的支配數和區域劃分來構建證明，特別是當支配數為2時，詳細分析了圖的結構特性。
6. 計數和平面嵌入障礙：
   • 結合計數和平面圖的嵌入障礙來處理證明中的一部分，特別是當(n, m)的值較大時，如何避免指數級增長的子情況。
7. 應用和動機：
   • 討論了(n, m)-圖同態在圖數據庫查詢評估問題中的應用，以及它們在社交網絡、信息網絡、技術網絡和生物網絡中的潛在用途。