禁止圖表

“禁止的未成年人”在這裡重定向。該術語也可以指年齡限制。

在數學的圖理論中，可以通過一組有限的單個圖表來描述許多重要的圖形家庭，這些圖形不屬於家族，並進一步將包含這些禁止圖中的任何一個的家族排除在家族中（誘導）子圖或次要。

該現象的一個典型示例是庫拉托夫斯基的定理，該定理指出圖是平面（可以在平面上沒有穿越而無需穿越的情況），並且僅當它不包含兩個禁止圖中的任何一個，完整的圖k 5和完整的bipittite圖k 3,3 。對於Kuratowski的定理，遏制的概念是圖同構的概念，其中一個圖的細分顯示為另一個圖的一個子圖。因此，每個圖都有一個平面圖（在這種情況下，它屬於平面圖的家族），或者它具有至少這兩個圖中的至少一個作為子圖的細分（在這種情況下，它不屬於平面圖）。

定義

更一般而言，禁止的圖表是通過指定家庭中任何圖表中禁止存在的子結構來指定圖形或超圖，結構的一種方法。不同的家庭在禁止的本質上有所不同。通常，結構G是家庭的成員且僅當G中沒有禁止的子結構時。禁止的子結構可能是：

禁止屬於給定圖的一組結構也可以稱為該家族的障礙物集。

禁止圖表可以在算法中用於測試圖形是否屬於給定家族。在許多情況下，可以在多項式時間內測試給定圖是否包含障礙物集的任何成員，因此它是否屬於該阻塞組定義的家族。

為了使家庭具有禁止的圖表表徵，具有特定類型的子結構，必須在子結構下關閉家庭。也就是說，家庭中圖中的每一個（給定類型）的每個子結構都必須是家庭中的另一個圖。同等地，如果圖形不屬於家族的一部分，則所有包含它作為子結構的較大圖也必須從家族中排除。如果這是真的，總是會有一個障礙物集（不在家庭中，而較小的子結構都屬於家族的圖集）。但是，對於某些子結構是什麼概念，這種障礙物可能是無限的。羅伯遜 - 西蒙定理證明，對於未成年人的特殊情況，在未成年人封閉的家庭中總是有有限的阻塞組。

圖形和超圖的禁止表徵列表

家庭 障礙物 關係 參考
森林 循環，一對平行邊緣和各個長度的週期 子圖 定義
循環（用於多編碼）或三角形k 3 （用於簡單的圖） 圖形小調 定義
線性森林 [循環 /三角形k 3 （見上文）]和恆星K 1,3 圖形小調 定義
無爪圖 Star K 1,3 誘導子圖 定義
可比性圖 誘導子圖
無三角形圖 三角k 3 誘導子圖 定義
平面圖 K 5和K 3,3 同型子圖 Kuratowski的定理
K 5和K 3,3 圖形小調 瓦格納的定理
外平面圖 K 4和K 2,3 圖形小調 Diestel（2000） ， 第1頁。 107
外1平面圖 六個禁止的未成年人 圖形小調 Auer等。 （2013）
固定屬的圖 有限障礙物 圖形小調 Diestel（2000） ， 第1頁。 275
Apex圖 有限障礙物 圖形小調
無連鎖的可嵌入圖 彼得森家族 圖形小調
兩部分圖 奇數 子圖
和弦圖 長度4或更多的循環 誘導子圖
完美的圖 奇數長5或更多的循環 誘導子圖
圖形圖 9禁止子圖 誘導子圖
仙人掌圖的圖圖 通過從完整的圖k 4中刪除邊緣而形成的四個vertex鑽石圖 圖形小調
梯子圖 k 2,3及其雙圖 同型子圖
拆分圖 誘導子圖
2連接系列 - 平行（樹寬≤2，分支寬度  ≤2） K 4 圖形小調 Diestel（2000） ， 第1頁。 327
樹寬 ≤ 3 K 5 ，八面體，五角大樓棱鏡，瓦格納圖 圖形小調
分支環 ≤ 3 K 5 ，八面體，立方體，瓦格納圖 圖形小調
補體 - 可還原圖（Cographs） 4-vertex路徑p 4 誘導子圖
瑣碎的完美圖 4 vertex路徑p 4和4 vertex循環C 4 誘導子圖
閾值圖 4 vertex路徑p 4，4 vertex循環C 4 ， c 4的補充 誘導子圖
3-均勻線性超圖的線圖 至少19歲的禁忌誘導子圖的有限列表 誘導子圖
k-均勻線性超圖的線圖， k > 3 最低邊緣度的禁止誘導子圖的有限列表至少2 K 2 - 3 K + 1 誘導子圖
圖形ΔY-可重新可重新為單個頂點 至少有680億個不同（1,2,3）的有限列表 圖形小調
光譜半徑的圖最多 存在有限的障礙物時，只有和任何 ， 在哪裡是最大的根 。 子圖 /誘導子圖
集群圖 三個vertex路徑圖 誘導子圖
一般定理
由誘導性財產定義的家庭 A，可能是非限限的阻塞組 誘導子圖
由次要財產定義的家庭 有限障礙物 圖形小調 羅伯遜 - 西摩定理

也可以看看