隱式圖

在圖形算法的研究中，隱式圖表示（或更簡單的隱式圖）是一個圖形，其頂點或邊緣在計算機內存中並未表示為顯式對象，而是從其他一些輸入中確定算法，例如可計算的算法功能。

鄰里表示

隱式圖的概念在各種搜索算法中很常見，這些算法用圖描述。在這種情況下，隱式圖可以定義為一組規則，以定義任何指定的頂點的所有鄰居。這種隱式圖表示類型類似於鄰接列表，因為它可以輕鬆訪問每個頂點的鄰居。例如，在搜索諸如Rubik Cube之類的拼圖的解決方案時，可以定義一個隱式圖，其中每個頂點代表多維數據集的可能狀態之一，每個邊緣代表從一個狀態到另一個狀態的移動。通過嘗試拼圖中的所有可能移動並確定這些移動中的每一個所達到的狀態，從而產生任何頂點的鄰居是很簡單的；但是，必須有一個隱式表示，因為Rubik立方體的狀態空間太大，無法允許算法列出其所有狀態。

在計算複雜性理論中，已經定義了與隱式圖相關的幾個複雜性類別，該類別定義為以上由列出頂點鄰居的規則或算法定義。例如， PPA是一個問題類別的類別，其中將其作為輸入一個無方向的隱式圖（其中頂點是n-位二進製字符串，具有用於列出任何頂點鄰居的多項式時間算法）和一個奇數度的頂點在圖中，必須找到第二個奇數的頂點。通過握手，存在這樣的頂點。在NP中找到一個問題是一個問題，但是可以以這種方式定義的問題可能不一定是NP完成的，因為尚不清楚PPA = np是不知道的。 PPAD是一個類似的類別，該類別定義在隱式有向圖上，引起了算法遊戲理論的關注，因為它包含計算NASH平衡的問題。一個在隱式圖中一個頂點對另一個頂點的可達到性的問題的問題也可以用來表徵由空間結合的無確定的複雜性類別（包括NL） （包括NL的類別（可能由隱式有向圖中的可達到的問題表徵的問題類別），其頂點為o（log n是log n） ） - 位BITSRINGS）， SL （無向圖的類似類）和PSPACE （可能以多項式長度bitsrings的隱式圖為特徵的問題類別）。在這種複雜性理論上下文中，隱式圖的頂點可以代表非確定的圖靈機的狀態，邊緣可能代表可能的狀態過渡，但隱式圖也可以用來表示許多其他類型的組合結構。 PLS是另一個複雜性類別，它捕獲了在隱式圖中找到局部Optima的複雜性。

隱式圖模型也已被用作相對化的一種形式，以證明比不塑造模型的已知分離更強的複雜性類別之間的分離。例如，Childs等。使用的隱式圖的鄰域表示可以定義圖形遍歷問題，該問題可以在量子計算機上在多項式時間內解決，但這需要指數時間才能在任何古典計算機上求解。

鄰接標記方案

在圖形的有效表示的上下文中，JH Muller在給定的圖中定義了圖形G的局部結構或鄰接標記方案，以作為g ，g，g，g，g ， log n ） bit標識符的分配。與算法（可能取決於f，但獨立於單個圖G ）一起，該算法將其作為輸入兩個頂點標識符，並確定它們是否是G中邊緣的終點。也就是說，這種隱式表示類型類似於鄰接矩陣：檢查兩個頂點是否相鄰，但要找到任何頂點的鄰居都可能涉及遍歷所有頂點並測試哪些是鄰居。

具有鄰接標籤方案的圖形家族包括：

有界度圖
如果G中的每個頂點最多都有D鄰居，則可以將G的頂點從1到N編號，並讓一個頂點的標識符為（ d + 1） - 其自己的數字及其鄰居的數量。當標識符中的第一個數字出現在另一個頂點標識符中時，兩個頂點是相鄰的。更一般而言，可以使用相同的方法為具有有界的樹木性或有界變性的圖形提供隱式表示，包括平面圖和任何次要閉合圖家族中的圖形。
相交圖
間隔圖是實際線路中一組線段的相交圖。可以給出一個鄰接標記方案，其中線段的端點的點從1到2 N編號，並且圖的每個頂點由其相應間隔的兩個端點的數字表示。通過此表示，可以通過比較表示它們的數字並驗證這些數字定義重疊間隔來檢查兩個頂點是否相鄰。相同的方法適用於其他幾何相交圖，包括邊界框和圓形圖的圖，以及這些家族的亞家族，例如距離棲息地圖和cographs 。但是，幾何相交圖表示並不總是意味著鄰接標記方案的存在，因為它可能需要的是對數數量的比數來指定每個幾何對象。例如，將圖表示為單位磁盤圖可能需要指數級的磁盤中心坐標。
低維可比性圖
部分訂購的集合的可比性圖具有每個集合元素的頂點，並且在偏序相關的兩個集合元素之間的邊緣。部分順序的順序維度是與給定的部分訂單相交的線性訂單的最小數量。如果部分順序具有有限的順序維度，則可以通過在每個定義線性訂單中標記每個頂點的位置來定義其頂點的鄰接標記方案，並確定每個對應的兩個頂點在每個相應的配對中都相鄰其標籤中的數字與彼此的順序關係相同。特別是，這允許對弦的可比性圖制定相鄰標記方案，該方案最多來自尺寸的部分順序。

隱式圖猜想

數學未解決的問題:

每個長大的遺傳性圖表都有隱性代表嗎？

（數學中更多未解決的問題）

並非所有的圖形家庭都有本地結構。對於某些家庭而言，一個簡單的計數參數證明不存在鄰接標記方案：只能使用O （ n log n ）位來表示整個圖表，因此僅在n -vertex的數量時才能存在此類類型的表示形式給定家族F中的圖最多為2 O （ n log n ） 。圖形的圖形家族比這比這更大的圖表，例如兩部分圖或無三角形圖，沒有鄰接標記方案。但是，即使是家庭中圖的數量很小的圖形家族也可能沒有鄰接標記方案。例如，邊緣比頂點少的圖族具有2 o （ n log n ） n -vertex圖，但沒有鄰接標記方案，因為一個人可以通過添加一個將任何給定的圖形轉換為較大的圖表。每個邊緣的新隔離頂點，而無需更改其標記性。 Kannan等。當被問及具有禁止的子圖表徵和最多具有2 o （ n log n ） n -vertex圖的最多足以保證存在鄰接標記方案的情況；這個問題是Spinrad作為猜想的重述，仍然開放。在滿足猜想條件且沒有已知鄰接標記方案的圖形家族中，是磁盤圖和線段相交圖的家族。

標記方案和誘導通用圖

如果圖族F具有鄰接標記方案，則F中的n -vertex圖可以表示為通用誘導的多項式尺寸的通用通用圖的誘導子圖，該圖由所有可能的頂點標識符組成。相反，如果可以構建此類型的誘導通用圖，則其頂點的身份可以用作鄰接標籤方案中的標籤。對於隱式圖表示的這種應用，標籤必須使用盡可能少的位，因為標籤中的位數直接轉化為誘導的通用圖中的頂點數量。 Alstrup和Rauhe表明，任何樹都有一個鄰接標記方案，每個標籤具有log 2 n + O （ log * n ）位，從中，任何具有Arboricity K的圖形都具有k log 2 n + o的方案（ log * *） n ）每個標籤的位和帶有n k 2 o （ log * n ）頂點的通用圖。特別是，平面圖最多具有三種樹狀，因此它們具有帶有幾乎我們數量的頂點的通用圖。 Gavoille和Labourel改善了這種結合，他們表明平面圖和次要封閉圖家族具有標記方案，每個標籤具有2個log 2 N + O （log log n ）位，並且有界樹機翼的圖具有帶有標記方案的標籤方案log 2 n + o （log log n ）每個標籤位。 Bonamy，Gavoille和Piliczuk再次改善了平面圖的綁定，他們表明平面圖具有一個標記方案，每個標籤具有（4/3+O（1））log 2 n位。最後，Dujmović等人表明平面圖具有一個標記方案，每個標籤的（1+O（1））log 2 n位，提供具有N 1+O（1）頂點的通用圖。

迴避

Aanderaa – Karp – Rosenberg的猜想涉及一個隱式圖作為一組標記的頂點，該頂點具有黑框規則，用於確定任何兩個頂點是否相鄰。該定義與鄰接標記方案有所不同，因為該規則可能特定於特定圖形，而不是適用於家庭中所有圖的通用規則。由於這種差異，每個圖都具有隱式表示。例如，規則可能是在單獨的鄰接矩陣中查找一對頂點。但是，作為輸入的算法，這種類型的隱式圖只有通過隱式鄰接測試才能在其上進行操作，而無需參考如何實現測試。

圖形屬性是圖形是否屬於給定的圖族的問題；在頂點的任何重新標記下，答案必須保持不變。在這種情況下，要確定的問題是，在最壞的情況下，必須測試多少個頂點，以確定感興趣的屬性是對給定的隱式圖為真或錯誤的。 Rivest和Vuillemin證明了任何非平凡圖屬性的任何確定性算法都必須測試二次數量的頂點數。 Aanderaa – Karp – Rosenberg的完整猜想是，單調圖屬性的任何確定性算法（如果將更多的邊緣添加到具有該屬性的圖形中，則必須是真實的），在某些情況下，必須測試每對可能的頂點。猜想的幾種情況已被證明是正確的，例如，對於具有質量數量的頂點的圖是正確的，但完整的猜想保持開放。還研究了有關隨機算法和量子算法的問題的變體。

Bender和Ron表明，在用於逃避性猜想的相同模型中，只有在恆定的時間內才有可能將有向的無環形圖與遠離無循環的圖形區分開。相反，在基於鄰里的隱式圖模型中不可能使用如此快的時間

也可以看看