查看“︁图子式”︁的源代码


{{translating|[[:en:Graph minor]]||tpercent=50|time=2020-12-22}}
在[[图论]]中，如果[[图 (数学)|无向图]]H可以通过图G删除边和顶点或[[边收缩|收缩]]边得到，则称H为G的'''子式'''（minor）或'''次图'''。

图子式的提出源自[[瓦格纳定理|瓦格纳定理]]，这个定理表明：当且仅当一个图不存在[[完全圖|完全图]]''K''<sub>5</sub>和[[完全二分图]]''K''<sub>3,3</sub>的子式时，这个图才是[[平面图 (图论)|平面图]]。<ref name="w">{{Harvard citation text|Lovász|2006}}, p.&nbsp;77; {{Harvard citation text|Wagner|1937a}}.</ref>
{{Translink|en|Robertson–Seymour theorem|罗伯逊-西摩定理}}表明，对于任何在图上删除点或边或收缩边保留的性质，类似的'''{{Translink|en|forbidden minor characterization|禁子式表征}}'''（forbidden minor characterization）也存在。<ref name="rst">{{Harvard citation text|Lovász|2006}}, theorem 4, p.&nbsp;78; {{Harvard citation text|Robertson|Seymour|2004}}.</ref>
给定图G和图H，可以在[[时间复杂度|多项式时间]]内判断H是否是G的子式。<ref name="rs95">{{Harvard citation text|Robertson|Seymour|1995}}.</ref>
连同上述禁子式表征，这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。<ref name="fl88">{{Harvard citation text|Fellows|Langston|1988}}.</ref>
其他涉及到图子式的定理和猜想包括{{link-en|图结构定理|graph structure theorem}}、{{link-en|Hadwiger猜想|Hadwiger conjecture (graph_theory)}}等。

==定义==
'''[[边收缩]]'''（contraction）是在图上移除一条边同时合并这条边的两个邻点。一个无向图''H''是另一个无向图''G''的子式，如果''G''通过一系列的收缩边、删除边、删除孤立点可以得到一个[[图同构|同构]]于''H''的图。这一系列收缩和删除操作的顺序不影响最后得到的图''H''。

== 例子 ==
H是G的子式：

H. [[File:GraphMinorExampleA.png|101x101像素|图H]]

G. [[File:GraphMinorExampleB.svg|200x200像素|图G]]

以下显示了如何构造子式。首先去除图G中虚线边，再去掉孤立的顶点，最后对灰色边进行边收缩即得到图H。

[[File:GraphMinorExampleC.svg|190x190像素|从图G变为图H]]

==主要结论和猜想==
可以很直接地验证，在同构意义上，图子式[[关系 (数学)|关系]]是一个[[偏序关系]]：它满足[[自反关系|自反性]]（自己是自己的子式）、[[反对称关系|反对称性]]（图''G''和''H''互为子式仅当它们同构）、[[传递关系|传递性]]（图''G''的子式的子式也是图''G''的子式）。{{Translink|en|Neil Robertson (mathematician)|尼尔·罗伯逊 (数学家)|尼尔·罗伯逊}}和{{Translink|en|Paul Seymour (mathematician)|保罗·西摩}}提出了一个更深刻的结论：图子式关系实际上是一种[[良擬序]]关系：给定一串无穷的图序列''G''<sub>1</sub>, ''G''<sub>2</sub>,...总是存在''i'' < ''j''，使得 ''G''<sub>''i''</sub>是''G''<sub>''j''</sub>的子式。一个等价的表述是，任意的一簇图的集合必然只有有限个子式意义下的[[极小元]]<ref>{{harvtxt|Diestel|2005}}, Chapter 12: Minors, Trees, and WQO; {{harvtxt|Robertson|Seymour|2004}}.</ref>。这个结论验证了先前的一个猜想：瓦格纳猜想。它很早就被{{Translink|en|Klaus Wagner|克拉斯·瓦格纳}}提出，直至1970年才发表。<ref>{{harvtxt|Lovász|2006}}, p.&nbsp;76.</ref>

在他们证明的过程中，西摩和罗伯逊也同时证明了{{link-en|图结构定理|graph structure theorem}}。对于一个给定的图''H''，这个定理刻画了不包含''H''-子式的图的结构。这个定理的严格表述又长又复杂，但是简而言之，它证明了这样一个图必须具有由嵌在有界[[亏格]]曲面上的图以小方式修改而成的图的{{link-en|团和|Clique-sum}}结构。因此，他们的理论建立了图子式和图的[[嵌入 (数学)|拓扑嵌入]]之间的基本联系。<ref>{{harvtxt|Lovász|2006}}, pp. 80–82; {{harvtxt|Robertson|Seymour|2003}}.</ref>

对于任意图''H''，无''H''-子式的简单图必须是稀疏的，即图的边数小于等于一个常数倍的图的阶数<ref>{{harvtxt|Mader|1967}}.</ref>。更精确地，如果图''H''有''h''个点，那么有''n''个顶点的不包含''H''-子式的简单图''G''有至多<math>\scriptstyle O(nh\sqrt{\log h})</math>条边。不包含''K<sub>h</sub>''-子式的图至少有这么多条边。<ref>{{harvtxt|Kostochka|1982}}; {{harvtxt|Kostochka|1984}}; {{harvtxt|Thomason|1984}}; {{harvtxt|Thomason|2001}}.</ref>因此，''G''的[[度|平均度]]是<math>\scriptstyle O(h \sqrt{\log h})</math>级别的。更进一步，不包含''H''-子式的图有一个和{{Translink|en|planar separator theorem|平面图分割定理}}类似的分割定理：给定''H''和任意不包含''H''-子式的n阶图''G''，可以找到<math>\scriptstyle O(\sqrt{n})</math>个''G''的顶点，使得删除这些点可以将''G''分成两个（可能不连通的）子图，使得每个子图有至多2''n''/3个顶点。<ref>{{harvtxt|Alon|Seymour|Thomas|1990}}; {{harvtxt|Plotkin|Rao|Smith|1994}}; {{harvtxt|Reed|Wood|2009}}.</ref>更强的结论是，对于任意的图''H''，不包含''H''-子式的n阶图''G''的[[树宽]]是<math>\scriptstyle O(\sqrt{n})</math>数量级的。<ref>{{harvtxt|Grohe|2003}}</ref>

{{link-en|Hadwiger猜想|Hadwiger conjecture (graph_theory)}}表明，如果图''G''不包含k阶[[完全图]]子式，那么''G''可以被[[图着色问题|(''k''&nbsp;&minus;&nbsp;1)-着色]]<ref>{{harvtxt|Hadwiger|1943}}</ref>。''k''&nbsp;=&nbsp;5的情况即为[[四色定理]]。Hadwiger猜想在''k''&nbsp;≤&nbsp;6的情况下已经被证实<ref>{{harvtxt|Robertson|Seymour|Thomas|1993}}.</ref>，但是更一般的情况下还没有定论。{{harvtxt|Bollobás|Catlin|Erdős|1980}} 称它为“图论中最深刻的尚未解决的问题之一”。另一个将四色定理和图子式联系起来的猜想是{{link-en|snark猜想|Snark (graph theory)}}，它表明任意无[[割边]]的3-[[正则图]]，如果它的[[图着色问题|边色数]]等于4，那么[[佩特森图]]一定是它的子式。<ref>{{harvtxt|Thomas|1999}}; {{harvtxt|Pegg|2002}}.</ref>

== 参见 ==
* [[瓦格纳定理]]
* [[细分 (图论)|细分]]
* [[边收缩]]
* [[串并图]]
* [[图论术语|子图]]
* [[图论术语]]

== 注释 ==
<references group="" responsive="0"></references>

== 参考文献 ==
{{refbegin|2}}
*{{citation|last1=Alon|first1=Noga|author1-link=Noga Alon|last2=Seymour|first2=Paul|author2-link=Paul Seymour (mathematician)|last3=Thomas|first3=Robin|author3-link=Robin Thomas (mathematician)|doi=10.2307/1990903|mr=1065053|journal=[[Journal of the American Mathematical Society]]|pages=801–808|title=A separator theorem for nonplanar graphs|issue=4|url=http://www.ams.org/journals/jams/1990-03-04/S0894-0347-1990-1065053-0/home.html|volume=3|year=1990|jstor=1990903|language=en|accessdate=2019-04-25|archive-date=2019-02-14|archive-url=https://web.archive.org/web/20190214142557/http://www.ams.org/journals/jams/1990-03-04/S0894-0347-1990-1065053-0/home.html|dead-url=no}}.
*{{citation|last1=Błasiok|first1=Jarosław|last2=Kamiński|first2=Marcin|last3=Raymond|first3=Jean-Florent|last4=Trunck|first4=Théophile|title=Induced minors and well-quasi-ordering|arxiv=1510.07135|bibcode=2015arXiv151007135B|language=en}}.
*{{citation|last1=Bollobás|first1=B.|author1-link=Béla Bollobás|last2=Catlin|first2=P. A.|last3=Erdős|first3=Paul|author3-link=Paul Erdős|journal=[[European Journal of Combinatorics]]|pages=195–199|title=Hadwiger's conjecture is true for almost every graph|url=http://www2.renyi.hu/~p_erdos/1980-10.pdf|volume=1|year=1980|doi=10.1016/s0195-6698(80)80001-1|deadurl=yes|archiveurl=https://web.archive.org/web/20090318165333/http://www2.renyi.hu/~p_erdos/1980-10.pdf|archivedate=2009-03-18|df=|language=en|accessdate=2019-04-25}}.
*{{citation|last1=Buchheim|first1=Christoph|last2=Chimani|first2=Markus|last3=Gutwenger|first3=Carsten|last4=Jünger|first4=Michael|last5=Mutzel|first5=Petra|author5-link=Petra Mutzel|editor-last=Tamassia|editor-first=Roberto|editor-link=Roberto Tamassia|contribution=Crossings and planarization|publisher=CRC Press, Boca Raton, FL|series=Discrete Mathematics and its Applications (Boca Raton)|title=Handbook of Graph Drawing and Visualization|year=2014|language=en}}.
*{{citation|last1=Demaine|first1=Erik D.|author1-link=Erik Demaine|last2=Hajiaghayi|first2=MohammadTaghi|doi=10.1007/s00453-004-1106-1|issue=3|journal=Algorithmica|pages=211–215|title=Diameter and treewidth in minor-closed graph families, revisited|url=http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/|volume=40|year=2004|language=en|accessdate=2019-04-25|archive-date=2019-09-20|archive-url=https://web.archive.org/web/20190920135226/http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/|dead-url=yes}}.
*{{citation|last1=Demaine|first1=Erik D.|author1-link=Erik Demaine|last2=Hajiaghayi|first2=MohammadTaghi|last3=Thilikos|first3=Dimitrios M.|contribution=1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor|doi=10.1007/3-540-45753-4_8|pages=67–80|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|title=Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002)|volume=2462|year=2002|language=en}}
*{{citation|last=Diestel|first=Reinhard|edition=3rd|isbn=978-3-540-26183-4|location=Berlin, New York|publisher=Springer-Verlag|title=Graph Theory|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|year=2005|language=en|accessdate=2019-04-25|archive-date=2011-07-28|archive-url=https://web.archive.org/web/20110728103939/http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|dead-url=no}}.
*{{citation|last=Ding|first=Guoli|doi=10.1006/jctb.1996.0002|issue=1|journal=[[Journal of Combinatorial Theory]]|mr=1368512|pages=11–23|series=Series B|title=Excluding a long double path minor|volume=66|year=1996|language=en}}.
*{{citation|last=Eppstein|first=David|authorlink=David Eppstein|doi=10.1007/s004530010020|arxiv=math.CO/9907126|mr=1759751|journal=Algorithmica|pages=275–291|title=Diameter and treewidth in minor-closed graph families|volume=27|year=2000|language=en}}.
*{{citation|last1=Fellows|first1=Michael R.|author1-link=Michael Fellows|last2=Langston|first2=Michael A.|author2-link=Michael Langston|doi=10.1145/44483.44491|issue=3|journal=[[Journal of the ACM]]|pages=727–739|title=Nonconstructive tools for proving polynomial-time decidability|volume=35|year=1988|language=en}}.
*{{citation|last=Grohe|first=Martin|authorlink=Martin Grohe|title=Local tree-width, excluded minors, and approximation algorithms|journal=[[Combinatorica]]|doi=10.1007/s00493-003-0037-9|volume=23|issue=4|pages=613–632|year=2003|arxiv=math/0001128|language=en}}.
*{{citation|last=Hadwiger|first=Hugo|author-link=Hugo Hadwiger|journal=Vierteljschr. Naturforsch. Ges. Zürich|pages=133–143|title=Über eine Klassifikation der Streckenkomplexe|volume=88|year=1943|language=en}}.
*{{citation|last=Hall|first=Dick Wick|doi=10.1090/S0002-9904-1943-08065-2|issue=12|journal=[[Bulletin of the American Mathematical Society]]|pages=935–936|title=A note on primitive skew curves|volume=49|year=1943|language=en}}.
*{{citation|last1=Kawarabayashi|first1=Ken-ichi|author1-link=Ken-ichi Kawarabayashi|last2=Kobayashi|first2=Yusuke|last3=Reed|first3=Bruce|author3-link=Bruce Reed (mathematician)|title=The disjoint paths problem in quadratic time|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|volume=102|issue=2|date=March 2012|pages=424–435|doi=10.1016/j.jctb.2011.07.004|language=en}}
*{{citation|last=Kostochka|first=Alexandr V.|journal=Metody Diskret. Analiz.|language=ru|pages=37–58|title=The minimum Hadwiger number for graphs with a given mean degree of vertices|volume=38|year=1982}}.
*{{citation|last=Kostochka|first=Alexandr V.|doi=10.1007/BF02579141|journal=Combinatorica|pages=307–316|title=Lower bound of the Hadwiger number of graphs by their average degree|volume=4|year=1984|language=en}}.
*{{citation|last=Lovász|first=László|author-link=László Lovász|doi=10.1090/S0273-0979-05-01088-8|issue=1|journal=[[Bulletin of the American Mathematical Society]]|pages=75–86|title=Graph minor theory|volume=43|year=2006|language=en}}.
*{{citation|last=Mader|first=Wolfgang|doi=10.1007/BF01364272|issue=4|journal=Mathematische Annalen|pages=265–268|title=Homomorphieeigenschaften und mittlere Kantendichte von Graphen|volume=174|year=1967|language=en}}.
*{{citation|last1=Nešetřil|first1=Jaroslav|author1-link=Jaroslav Nešetřil|last2=Ossona de Mendez|first2=Patrice|author2-link=Patrice Ossona de Mendez|doi=10.1007/978-3-642-27875-4|isbn=978-3-642-27874-7|mr=2920058|pages=62–65|publisher=Springer|series=Algorithms and Combinatorics|title=Sparsity: Graphs, Structures, and Algorithms|volume=28|year=2012|language=en}}.
*{{citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf|doi=10.1109/TED.2002.1003756|bibcode=2002ITED...49.1084A|language=en|accessdate=2019-04-25|archive-date=2019-04-02|archive-url=https://web.archive.org/web/20190402234011/http://www.ams.org/notices/200209/rev-pegg.pdf|dead-url=no}}.
*{{citation|last1=Plotkin|first1=Serge|last2=Rao|first2=Satish|last3=Smith|first3=Warren D.|contribution=Shallow excluded minors and improved graph decompositions|pages=462–470|title=Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994)|url=http://www.stanford.edu/~plotkin/lminors.ps|year=1994|language=en}}.
*{{citation|last1=Reed|first1=Bruce|authorlink=Bruce Reed (mathematician)|last2=Wood|first2=David R.|doi=10.1145/1597036.1597043|issue=4|journal=ACM Transactions on Algorithms|pages=Article 39|title=A linear-time algorithm to find a separator in a graph excluding a minor|volume=5|year=2009|language=en}}.
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul|author2-link=Paul Seymour (mathematician)|doi=10.1016/0095-8956(83)90079-5|issue=1|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=39–61|title=Graph minors. I. Excluding a forest|volume=35|year=1983|language=en}}.
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul D.|author2-link=Paul Seymour (mathematician)|doi=10.1016/0095-8956(86)90030-4|issue=1|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=92–114|title=Graph minors. V. Excluding a planar graph|volume=41|year=1986|language=en}}
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul D.|author2-link=Paul Seymour (mathematician)|contribution=Excluding a graph with one crossing|editor1-last=Robertson|editor1-first=Neil|editor2-last=Seymour|editor2-first=Paul|pages=669–675|publisher=[[American Mathematical Society]]|series=Contemporary Mathematics|title=Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors|volume=147|year=1993|language=en}}.
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul D.|author2-link=Paul Seymour (mathematician)|doi=10.1006/jctb.1995.1006|issue=1|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=65–110|title=Graph Minors. XIII. The disjoint paths problem|volume=63|year=1995|language=en}}.
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul D.|author2-link=Paul Seymour (mathematician)|doi=10.1016/S0095-8956(03)00042-X|issue=1|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=43–76|title=Graph Minors. XVI. Excluding a non-planar graph|volume=89|year=2003|language=en}}.
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul D.|author2-link=Paul Seymour (mathematician)|doi=10.1016/j.jctb.2004.08.001|issue=2|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=325–357|title=Graph Minors. XX. Wagner's conjecture|volume=92|year=2004|language=en}}.
*{{citation|last1=Robertson|first1=Neil|author1-link=Neil Robertson (mathematician)|last2=Seymour|first2=Paul|author2-link=Paul Seymour (mathematician)|last3=Thomas|first3=Robin|author3-link=Robin Thomas (mathematician)|doi=10.1007/BF01202354|journal=[[Combinatorica]]|pages=279–361|title=Hadwiger's conjecture for ''K''<sub>6</sub>-free graphs|url=http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf|volume=13|year=1993|language=en|accessdate=2019-04-25|archive-date=2009-04-10|archive-url=https://web.archive.org/web/20090410233641/http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf|dead-url=yes}}.
*{{citation|last=Thomas|first=Robin|authorlink=Robin Thomas (mathematician)|contribution=Recent excluded minor theorems for graphs|location=Cambridge|mr=1725004|pages=201–222|publisher=Cambridge Univ. Press|series=London Math. Soc. Lecture Note Ser.|title=Surveys in combinatorics, 1999 (Canterbury)|url=http://people.math.gatech.edu/~thomas/PAP/bcc.pdf|volume=267|year=1999|language=en|access-date=2019-04-25|archive-url=https://web.archive.org/web/20160803200552/http://people.math.gatech.edu/~thomas/PAP/bcc.pdf|archive-date=2016-08-03|dead-url=yes}}.
*{{citation|last=Thomason|first=Andrew|doi=10.1017/S0305004100061521|issue=2|journal=[[Mathematical Proceedings of the Cambridge Philosophical Society]]|pages=261–265|title=An extremal function for contractions of graphs|volume=95|year=1984|bibcode=1983MPCPS..95..261T|language=en}}.
*{{citation|last=Thomason|first=Andrew|doi=10.1006/jctb.2000.2013|issue=2|journal=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=318–338|title=The extremal function for complete minors|volume=81|year=2001|language=en}}.
*{{citation|last=Wagner|first=Klaus|author-link=Klaus Wagner|doi=10.1007/BF01594196|journal=Math. Ann.|pages=570–590|title=Über eine Eigenschaft der ebenen Komplexe|volume=114|year=1937a|language=en}}.
*{{citation|last=Wagner|first=Klaus|author-link=Klaus Wagner|journal=Deutsche Mathematik|pages=280–285|title=Über eine Erweiterung des Satzes von Kuratowski|volume=2|year=1937b|language=en}}.
{{refend}}

== 外部链接 ==
* {{MathWorld|urlname=GraphMinor|title=Graph Minor}}

[[Category:图论]]