http://pco.iis.nsk.su/grapp/index.php?title=Minor_of_a_graph&feed=atom&action=history Minor of a graph - История изменений 2022-08-09T14:09:33Z История изменений этой страницы в вики MediaWiki 1.31.0 http://pco.iis.nsk.su/grapp/index.php?title=Minor_of_a_graph&diff=8096&oldid=prev Glk: Новая страница: «'''Minor of a graph''' --- минор графа. A graph $H$ obtained from $G$ by a series of vertex deletions, edge deletions and '' contra…» 2011-06-02T07:44:37Z <p>Новая страница: «&#039;&#039;&#039;Minor of a graph&#039;&#039;&#039; --- минор графа. A graph &lt;math&gt;H&lt;/math&gt; obtained from &lt;math&gt;G&lt;/math&gt; by a series of vertex deletions, edge deletions and &#039;&#039; contra…»</p> <p><b>Новая страница</b></p><div>'''Minor of a graph''' --- минор графа. <br /> <br /> A graph &lt;math&gt;H&lt;/math&gt; obtained from &lt;math&gt;G&lt;/math&gt; by a series of vertex deletions, edge<br /> deletions and '' contractions of an edge''. A class of graphs &lt;math&gt;{\mathcal<br /> F}&lt;/math&gt; is called ''' minor-closed''' if for every graph &lt;math&gt;G&lt;/math&gt; in &lt;math&gt;{\mathcal F}&lt;/math&gt;,<br /> every ''' minor''' of &lt;math&gt;G&lt;/math&gt; is also a member of &lt;math&gt;{\mathcal F}&lt;/math&gt;. For a class of graphs<br /> &lt;math&gt;{\mathcal F}&lt;/math&gt;, a finite ''' obstruction set''' &lt;math&gt;S&lt;/math&gt; is a finite set of<br /> minors such that a graph is a member of &lt;math&gt;{\mathcal F}&lt;/math&gt;<br /> if and only if it does<br /> not contain an element of &lt;math&gt;S&lt;/math&gt; as a minor.<br /> <br /> The graphs in every minor-closed class of graphs are recognizable in<br /> &lt;math&gt;{\mathcal O}(n^{3})&lt;/math&gt; time.</div> Glk