图子式
维基百科,自由的 encyclopedia
在图论中,如果无向图H可以通过图G删除边和顶点或收缩边得到,则称H为G的子式(minor)或次图。
此条目目前正依照en:Graph minor上的内容进行翻译。 (2020年12月22日) |
图子式的提出源自瓦格纳定理,这个定理表明:当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时,这个图才是平面图。[1] 罗伯逊-西摩定理(英语:Robertson–Seymour theorem)表明,对于任何在图上删除点或边或收缩边保留的性质,类似的禁子式表征(英语:forbidden minor characterization)(forbidden minor characterization)也存在。[2] 给定图G和图H,可以在多项式时间内判断H是否是G的子式。[3] 连同上述禁子式表征,这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。[4] 其他涉及到图子式的定理和猜想包括图结构定理(英语:graph structure theorem)、Hadwiger猜想(英语:Hadwiger conjecture (graph_theory))等。