各種圖形類型的意義

Question

有很多named graph types。我想知道這個分類背後的標準是什麼。不同的類型適用於不同的環境嗎？而且，從商業應用程序（從設計和編程的角度來看）是否可以從這些分類中獲益？這類似於設計模式嗎？

Answer 1

我們給名圖的普通家庭有以下幾個原因：

• 圖的某些家庭擁有不錯的，簡單的屬性。例如，trees具有許多有用的屬性（任何一對節點之間只有一條路徑，它們最大程度地是非循環的，它們最小連接等），不包含任意圖。 Directed acyclic graphs可以是topologically sorted，正常圖不能。如果您可以使用這些類型的圖表之一對問題進行建模，則可以使用它們上的專用算法來提取不一定能從任意圖表獲得的屬性。

• 某些算法在某些類型的圖表上運行得更快。許多圖上的NP難問題，到目前爲止還沒有任何多項式時間算法，可以很容易地在某些類型的圖上求解。例如，maximum independent set problem（選擇沒有兩個節點通過邊連接的節點的最大集合）是NP-hard，但可以在樹和bipartite graphs的多項式時間內求解。 4着色問題（確定一個圖的節點是否可以用四種不同顏色中的一種着色，而不向相鄰節點分配相同的顏色）通常是NP-hard，但對於planar graphs（這是着名的四 - 色原理）。

• 某些算法在某些類型的圖上更容易。圖中的matching是圖中沒有兩個邊共享端點的邊的集合。可以使用最大匹配來表示將人員組合成組的方式。在二分圖中，可以使用最大匹配來表示將人員分配給任務的方式，使得沒有人被分配兩個任務並且沒有任務被分配給兩個人。有許多快速算法用於在雙向圖中找到最大匹配，該算法工作迅速且易於理解。一般圖的相應算法明顯更復雜，效率略低。

• 某些圖表具有歷史意義。許多命名圖是以某人使用該圖來反駁關於任意圖的屬性的猜測的名字命名的。例如，Petersen graph是許多定理的反例，對於圖似乎是正確的，但事實上並非如此。

• 某些圖表在理論計算機科學中很有用。一個expander graph是一個圖，直觀地說，任何節點集合都必須連接到圖中比例較大的節點集合。並非所有圖都是擴展圖。 Expander圖用於理論計算機科學中的許多結果，例如PCP定理的一個證明和證明SL = L。

這不是我們爲什麼關心不同的圖科一個詳盡的清單，但希望它有助於激發他們的使用和研究。

希望這會有所幫助！