羅伯遜-西摩定理,也稱為圖子式定理,是由羅伯遜和西摩提出的 庫拉托夫斯基歸約定理 的推廣,該定理指出有限 圖 的集合透過子式可嵌入性是良擬序的,由此得出庫拉托夫斯基的“停用子圖”嵌入障礙推廣到更高 虧格 曲面。
形式上,對於固定的 整數 ,存在一個有限的圖列表
,其屬性是一個 圖
嵌入到 虧格 為
的曲面上 當且僅當 它不包含列表
中的任何 圖 作為子式。
羅伯遜-西摩定理,也稱為圖子式定理,是由羅伯遜和西摩提出的 庫拉托夫斯基歸約定理 的推廣,該定理指出有限 圖 的集合透過子式可嵌入性是良擬序的,由此得出庫拉托夫斯基的“停用子圖”嵌入障礙推廣到更高 虧格 曲面。
形式上,對於固定的 整數 ,存在一個有限的圖列表
,其屬性是一個 圖
嵌入到 虧格 為
的曲面上 當且僅當 它不包含列表
中的任何 圖 作為子式。
Weisstein, Eric W. "羅伯遜-西摩定理。" 來自 Web 資源。 https://mathworld.tw/Robertson-SeymourTheorem.html