图子式

This article "图子式" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:图子式. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one. 在图论中，如果无向图 H 可以通过删除边和顶点以及收缩边而由图G 形成，那么就被称为G 的子式（minor）或次图。

在英文中，我们说 "H is a minor of G." 图子式也被称为是 "graph minor."

图子式理论始于瓦格纳定理，即当且仅当图的子式不包括完全图K₅ 或完全二分图K_3,3时，这一图就是平面的。

Robertson-Seymour定理也是关于图子式的重要禁子式表征（forbidden minor characterization）。

可以在多项式时间内测试如何H是否G的子式。 连通以上的定理，这意味着通过删除和收缩保留的每个图形属性可以在多项式时间内被识别。

其他结果包括图结构定理（graph structure theorem）、Hadwiger猜想、等。

例子

H是G的子式：

H.

G.

下图显示了如何构造子式：

参见

• 瓦格纳定理
• 细分
• 边收缩
• 串并图
• 子图
• 图论术语

参考资料

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

外部连接

• Template:MathWorld
• https://baike.baidu.com/item/%E5%AD%90%E5%9B%BE（但这是子图的文章）

This article "图子式" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:图子式. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• 边收缩
• 彼得森定理
• 惠特尼定理
• 度 (图论)
• 串并图

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

<addthis />