Apex graph
在圖理論中，數學的分支， Apex圖是可以通過去除單個頂點來製成平面的圖。刪除的頂點稱為圖形的頂點。它是頂點，而不是頂點，因為Apex Graph可能具有多個頂點。例如，在最小的非平面圖k 5或k 3,3中，每個頂點都是頂點。 Apex圖包括本身就是平面的圖，在這種情況下，每個頂點都是頂點。即使沒有頂點要刪除，零圖也被視為頂點圖。
Apex圖是在帶領未成年人的操作下封閉的，並在圖形理論的其他幾個方面發揮作用：無連鎖嵌入， Hadwiger的猜想，YΔY-可還原圖以及TreeWidth和圖直徑之間的關係。
表徵和識別
Apex圖是在帶領未成年人的操作下關閉的：收縮任何邊緣或刪除任何邊緣或頂點，都會導致另一個Apex圖。因為，如果g是帶有頂點V的頂端圖，則不涉及V的任何收縮或去除均可以保留其餘圖的平面度，以及對V到V的邊緣刪除的任何邊緣去除。如果收縮了對V的邊緣事件，則對剩餘圖的影響等於去除邊緣的另一個端點。如果刪除了V本身，則可以選擇任何其他頂點作為頂點。
由羅伯遜 - 西蒙定理（Robertson-Seymour Therorem） ，因為它們形成了次要的圖形家族，因此頂部圖具有禁止的圖表。只有有限的圖形既不是頂點圖，也沒有另一個非apex圖作為輔修圖。這些圖是禁止作為頂點圖的屬性的未成年人。當且僅當沒有禁止的未成年人是G的少數G時，任何其他圖G是Apex圖。這些禁止的未成年人包括彼得森家族的七個圖，三張由k 5和k 3,3的兩個分離工會形成的脫節圖，以及許多其他圖。但是，對它們的完整描述仍然未知。
儘管一組完整的禁止未成年人仍然未知，但仍可以測試給定圖是頂點圖，如果是的，則在線性時間內找到該圖的頂點。更一般而言，對於任何固定常數k ，可以在線性時間識別k -apex圖，在大多數k頂點處刪除一些精心選擇的一組的圖會導致平面圖。但是，如果k是可變的，則問題是NP完成。
色數
每個頂點圖最多都有五個色數：基礎平面圖最多需要四種顏色，而四種顏色定理最多需要四種顏色，其餘頂點最多需要一種附加的顏色。羅伯遜（ Robertson ） ，西摩（Seymour）和托馬斯（Thomas）（1993a）在他們證明了哈德威格（Hadwiger ）猜想的情況下使用了這一事實。猜想必須是一個頂點圖，但是由於沒有6個色調圖形，因此不存在反例。
Jørgensen（1994）猜想，每個沒有K 6作為小調的6個vertex連接圖必須是頂點圖。如果證明了這一點，羅伯遜 - 西摩 - 托馬斯（Hadwiger）的猜想將是直接的後果。喬根森的猜想仍然未經證實。但是，如果是錯誤的，則只有許多反例。
本地樹寬
如果f遵守直徑和樹寬之間的功能關係，則圖族f具有局限性的局部樹寬：存在一個函數f ，使得f中的直徑圖的樹寬度最多為f （ d ） 。頂點圖沒有界限的本地樹寬：通過將Apex頂點連接到N × N網格圖的每個頂點形成的頂點圖，而直徑為n和直徑2，因此該圖不受這些圖的函數的界限。 。但是，Apex圖密切連接到有界的本地樹寬：限製本地樹寬的次要閉合圖家族F恰好是具有頂點圖作為其禁止的未成年人之一的家族。具有頂點圖的次要圖形家族是其禁止的未成年人之一，被稱為Apex-Minor-Fime 。使用此術語，可以重述Apex圖與本地樹寬之間的連接，因為無頂點的圖形家族與具有有限的本地樹寬的次要閉合圖家族相同。
有界的本地樹寬的概念構成了雙段性理論的基礎，並允許在無頂點的無限製圖上通過多項式時間算法或固定參數拖拉算法或使用近似於近似的算法無限圖上的許多算法問題。多項式時間近似方案。 Apex-Minor-frage Graph家族遵守圖形結構定理的增強版本，從而導致圖形著色和旅行推銷員問題的其他近似算法。但是，其中一些結果也可以通過結構定理將其與Apex-Minor圖形相關聯的結構定理擴展到任意的次要圖形家族。
嵌入
如果g是帶有頂點V的頂點圖，並且τ是覆蓋v的所有鄰居所需的面孔數量的最小數量τ - 1 ：只需將數量的橋樑添加到平面嵌入中，將所有必須連接到V的面連接在一起。例如，將單個頂點添加到外平面圖（具有τ= 1的圖）會產生平面圖。當g \ { v }是3連接時，他的界限在最佳的恆定因素之內： g的每個表面嵌入至少需要屬 τ / 160 。但是，確定頂端圖的表面嵌入的最佳屬是NP硬的。
通過使用SPQR樹來編碼Apex圖的平面部分的可能嵌入，可以在平面中計算唯一雜交涉及Apex Vertex的平面圖的圖形，從而最小化雜交總數時間。但是，如果允許任意穿越，即使在通過將單個邊緣添加到平面圖中形成的特殊情況下，也可以最大程度地減少交叉數的數量。
Apex圖還可以在三維空間中無連鎖嵌入：它們可以以某種方式嵌入，使圖中的每個循環都是磁盤的邊界，該磁盤的邊界未由圖形的任何其他功能跨過。可以通過將圖形的平面部分繪製在平面上，將頂點放在平面上方，然後通過直線邊緣連接到其每個鄰居，從而獲得這種類型的圖。無連鎖的可嵌入圖形構成了一個次要的家庭，彼得森家族的七個圖表是其最小的禁忌少年。因此，這些圖也被禁止作為頂點圖的未成年人。但是，存在不是頂點圖的無連鎖嵌入圖。
yΔy-還原性
如果可以通過一系列步驟將其還原為單個頂點，則連接的圖是可重新還原的，每個頂點是δ-y或y-δ變換，去除自循環或多個鄰接，去除一個帶有一個鄰居的頂點，並用單個邊緣替換了第二個鄰居的頂點及其兩個相鄰的邊緣。
像Apex圖和無連鎖嵌入圖一樣，在圖形未成年人中封閉了YΔY-還原圖。而且，像無連鎖的可包含圖一樣，YδY可還原圖在Petersen家族中具有七個圖形作為禁止的未成年人，促使問題是，這些問題是否是唯一的禁止的未成年人，以及YδY可還原圖是否與可連接的無連接嵌入的圖形相同圖。但是，尼爾·羅伯遜（Neil Robertson）提供了不可還原的頂點圖的示例。由於每個頂點圖都是無連鎖的嵌入式，因此這表明存在無連鎖的嵌入式圖形，但不可嵌入的圖形，因此YΔY-可還原圖還有其他禁止的未成年人。
Robertson的Apex圖顯示在圖中。可以通過將Apex頂點連接到菱形十二面體的每個度三個頂點，或通過合併兩個四維超級立方體圖的兩個直徑相對的頂點來獲得。由於菱形十二面體的圖是平面，因此羅伯遜的圖是頂點圖。它是一個至少四個的無三角形圖，因此無法通過任何還原YΔY-Recuction更改。
幾乎平面圖
如果圖形是頂點圖，則不一定是具有唯一的頂點的情況。例如，在次要最小非平面圖k 5和k 3,3中，可以選擇任何頂點作為頂點。瓦格納（ Wagner，1967，1970 ）將幾乎平面圖定義為具有屬性的非平面最高圖，所有頂點都可以是圖形的頂點。因此， k 5和k 3,3幾乎是平面。他將這些圖的分類分為四個子集，其中一個由圖形（如Möbius梯子）組成，可以將其嵌入Möbius條上，以使得條的單個邊緣與漢密爾頓的單個邊緣相吻合。圖形。在獲得四種顏色定理的證明之前，他證明了每個幾乎平面圖最多都可以用四種顏色進行顏色，除了通過用兩個相鄰的頂點代替帶有奇怪外部循環的輪子圖形的圖形，該圖是奇怪的外循環。需要五種顏色。此外，他證明，除了單個例外（立方體的八個vertex補體圖）外，每個幾乎平面圖都嵌入了射影平面上。
但是，短語“近平面圖”是高度模棱兩可的：它也用於參考Apex圖，通過將一個邊緣添加到平面圖中形成的圖形以及由平面嵌入式圖形成的圖形來替換有界數的面孔通過有限路徑的“渦旋”以及其他不太確定的圖表集。
相關的圖形類
如果可以通過刪除n或更少的頂點將其製成平面，則稱為n -apex。 1-apex圖也據說是頂點。
根據Lipton等人的說法。 （2018年） ，如果圖中有一些邊緣可以刪除以使圖平面的圖形，則圖形為edge-apex 。圖形是收縮 -如果圖表中有一些邊緣可以收縮以製成圖形平面。
通常，如果x是一類圖形，則“ apex- x ”圖是可以通過刪除一些頂點將X帶入X類的圖。例如，頂點是一個具有頂點V的圖G ，使得g-v是cograph。