text: 在圖論中，如果無向圖H可以透過圖G刪除邊和頂點或收縮邊得到，則稱H為G的子式或次圖。圖子式的提出源自瓦格納定理，這個定理表明：當且僅當一個圖不存在完全圖"K"5和完全二分圖"K"3,3的子式時，這個圖才是平面圖。表明，對於任何在圖上刪除點或邊或收縮邊保留的性質，類似的也存在。給定圖G和圖H，可以在多項式時間內判斷H是否是G的子式。連同上述禁子式表徵，這意味著任何刪除點或邊和收縮邊保留的圖的屬性可以在多項式時間內被識別。其他涉及到圖子式的定理和猜想包括、等。定義.邊收縮是在圖上移除一條邊同時合併這條邊的兩個鄰點。一個無向圖"H"是另一個無向圖"G"的子式，如果"G"透過一系列的收縮邊、刪除邊、刪除孤立點可以得到一個同構於"H"的圖。這一系列收縮和刪除操作的順序不影響最後得到的圖"H"。例子.H是G的子式：H.G.以下顯示瞭如何構造子式。首先去除圖G中虛線邊，再去掉孤立的頂點，最後對灰色邊進行邊收縮即得到圖H。主要結論和猜想.可以很直接地驗證，在同構意義上，圖子式關係是一個偏序關係：它滿足自反性。和提出了一個更深刻的結論：圖子式關係實際上是一種良擬序關係：給定一串無窮的圖序列"G"1, "G"2...總是存在"i" &lt; "j"，使得 "G""i"是"G""j"的子式。一個等價的表述是，任意的一簇圖的集合必然只有有限個子式意義下的極小元。這個結論驗證了先前的一個猜想：瓦格納猜想。它很早就被提出，直至1970年才發表。在他們證明的過程中，西摩和羅伯遜也同時證明了。對於一個給定的圖"H"，這個定理刻畫了不包含"H"-子式的圖的結構。這個定理的嚴格表述又長又複雜，但是簡而言之，它證明了這樣一個圖必須具有由嵌在有界虧格曲面上的圖以小方式修改而成的圖的結構。因此，他們的理論建立了圖子式和圖的拓撲嵌入之間的基本聯絡。對於任意圖"H"，無"H"-子式的簡單圖必須是稀疏的，即圖的邊數小於等於一個常數倍的圖的階數。更精確地，如果圖"H"有"h"個點，那麼有"n"個頂點的不包含"H"-子式的簡單圖"G"有至多formula_1條邊。不包含"Kh"-子式的圖至少有這麼多條邊。因此，"G"的平均度是formula_2級別的。更進一步，不包含"H"-子式的圖有一個和類似的分割定理：給定"H"和任意不包含"H"-子式的n階圖"G"，可以找到formula_3個"G"的頂點，使得刪除這些點可以將"G"分成兩個子圖，使得每個子圖有至多2"n"/3個頂點。更強的結論是，對於任意的圖"H"，不包含"H"-子式的n階圖"G"的是formula_3數量級的。表明，如果圖"G"不包含k階完全圖子式，那麼"G"可以被("k" − 1)-著色。"k" = 5的情況即為四色定理。Hadwiger猜想在"k" ≤ 6的情況下已經被證實，但是更一般的情況下還沒有定論。#重定向 稱它為“圖論中最深刻的尚未解決的問題之一”。另一個將四色定理和圖子式聯絡起來的猜想是，它表明任意無割邊的3-正則圖，如果它的邊色數等於4，那麼佩特森圖一定是它的子式。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 圖子式
metadata: https://zh.wikipedia.org/wiki?curid=6563442