http://pco.iis.nsk.su/grapp/index.php?title=Coloring,_colouring&feed=atom&action=history Coloring, colouring - История изменений 2024-03-29T09:39:35Z История изменений этой страницы в вики MediaWiki 1.39.3 http://pco.iis.nsk.su/grapp/index.php?title=Coloring,_colouring&diff=10474&oldid=prev KEV в 05:55, 23 сентября 2014 2014-09-23T05:55:19Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 12:55, 23 сентября 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Coloring, colouring&#039;&#039;&#039; <del style="font-weight: bold; text-decoration: none;">--- </del>раскраска.  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Coloring, colouring&#039;&#039;&#039; <ins style="font-weight: bold; text-decoration: none;">— &#039;&#039;[[</ins>раскраска<ins style="font-weight: bold; text-decoration: none;">]]</ins>.<ins style="font-weight: bold; text-decoration: none;">&#039;&#039; </ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;1.&#039;&#039;&#039; Let &lt;math&gt;G&lt;/math&gt; be a graph and &lt;math&gt;S&lt;/math&gt; be a set of colors. A &#039;&#039;&#039;coloring&#039;&#039;&#039; of &lt;math&gt;G&lt;/math&gt; is</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;1.&#039;&#039;&#039; Let &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G&lt;/math&gt; be a <ins style="font-weight: bold; text-decoration: none;">[[</ins>graph<ins style="font-weight: bold; text-decoration: none;">, undirected graph, nonoriented graph|graph]] </ins>and &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>S&lt;/math&gt; be a set of colors. A &#039;&#039;&#039;coloring&#039;&#039;&#039; of &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G&lt;/math&gt; is</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>a mapping &lt;math&gt;f: V(G) \rightarrow S&lt;/math&gt; from the vertex set &lt;math&gt;V(G)&lt;/math&gt; into &lt;math&gt;S&lt;/math&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>a mapping &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>f: V(G) \rightarrow S&lt;/math&gt; from the <ins style="font-weight: bold; text-decoration: none;">[[</ins>vertex<ins style="font-weight: bold; text-decoration: none;">]] </ins>set &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>V(G)&lt;/math&gt; into &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>S&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>such that no two adjacent vertices have the same color,</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>such that no two adjacent vertices have the same color,</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>i.e., &lt;math&gt;f(x) \neq f(y)&lt;/math&gt; whenever &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; are adjacent. This &#039;&#039;&#039;C.&#039;&#039;&#039; is called a &#039;&#039;&#039;proper&#039;&#039;&#039; (&#039;&#039;&#039;valid&#039;&#039;&#039;,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>i.e., &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>f(x) \neq f(y)&lt;/math&gt; whenever &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>x&lt;/math&gt; and &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>y&lt;/math&gt; are adjacent. This &#039;&#039;&#039;C.&#039;&#039;&#039; is called a &#039;&#039;&#039;proper&#039;&#039;&#039; (&#039;&#039;&#039;valid&#039;&#039;&#039;,</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;legitimate&#039;&#039;&#039;, &#039;&#039;&#039;good&#039;&#039;&#039;) coloring.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;legitimate&#039;&#039;&#039;, &#039;&#039;&#039;good&#039;&#039;&#039;) coloring.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;f&lt;/math&gt; is called &#039;&#039;&#039;&lt;math&gt;k&lt;/math&gt;-coloring&#039;&#039;&#039; of &lt;math&gt;G&lt;/math&gt; if &lt;math&gt;f&lt;/math&gt; is a coloring of &lt;math&gt;G&lt;/math&gt; into &lt;math&gt;k&lt;/math&gt; colors,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>f&lt;/math&gt; is called &#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[k-Coloring|</ins>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k&lt;/math&gt;-coloring<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;&#039; of &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G&lt;/math&gt; if &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>f&lt;/math&gt; is a coloring of &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G&lt;/math&gt; into &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k&lt;/math&gt; colors,</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>i.e. &lt;math&gt;k=|\{f(p): p\in V(G)\}|&lt;/math&gt;.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>i.e. &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k=|\{f(p): p\in V(G)\}|&lt;/math&gt;.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>It is &lt;math&gt;NP&lt;/math&gt;-complete to decide if a given graph &lt;math&gt;G&lt;/math&gt; admits</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>It is &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>NP&lt;/math&gt;-complete to decide if a given graph &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G&lt;/math&gt; admits</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>a &lt;math&gt;k&lt;/math&gt;-coloring for a given &lt;math&gt;k&lt;/math&gt; except for the cases &lt;math&gt;k&lt;/math&gt; = 1 and &lt;math&gt;k&lt;/math&gt; = 2.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>a &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k&lt;/math&gt;-coloring for a given &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k&lt;/math&gt; except for the cases &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k&lt;/math&gt; = 1 and &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>k&lt;/math&gt; = 2.</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Graph coloring remains &lt;math&gt;NP&lt;/math&gt;-complete even on</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Graph coloring remains &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>NP&lt;/math&gt;-complete even on</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>planar graphs of degree at most 4.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[planar graph|</ins>planar graphs<ins style="font-weight: bold; text-decoration: none;">]] </ins>of degree at most 4.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;2.&#039;&#039;&#039;  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;2.&#039;&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==See==</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>*&#039;&#039;Large-block schema&#039;&#039;.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>Large-block schema<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Литература==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009</ins>.</div></td></tr> </table> KEV http://pco.iis.nsk.su/grapp/index.php?title=Coloring,_colouring&diff=6582&oldid=prev Glk: Новая страница: «'''Coloring, colouring''' --- раскраска. '''1.''' Let <math>G</math> be a graph and <math>S</math> be a set of colors. A '''coloring''' of <math>G</math> …» 2011-03-03T08:09:52Z <p>Новая страница: «&#039;&#039;&#039;Coloring, colouring&#039;&#039;&#039; --- раскраска. &#039;&#039;&#039;1.&#039;&#039;&#039; Let &lt;math&gt;G&lt;/math&gt; be a graph and &lt;math&gt;S&lt;/math&gt; be a set of colors. A &#039;&#039;&#039;coloring&#039;&#039;&#039; of &lt;math&gt;G&lt;/math&gt; …»</p> <p><b>Новая страница</b></p><div>&#039;&#039;&#039;Coloring, colouring&#039;&#039;&#039; --- раскраска. <br /> <br /> &#039;&#039;&#039;1.&#039;&#039;&#039; Let &lt;math&gt;G&lt;/math&gt; be a graph and &lt;math&gt;S&lt;/math&gt; be a set of colors. A &#039;&#039;&#039;coloring&#039;&#039;&#039; of &lt;math&gt;G&lt;/math&gt; is<br /> a mapping &lt;math&gt;f: V(G) \rightarrow S&lt;/math&gt; from the vertex set &lt;math&gt;V(G)&lt;/math&gt; into &lt;math&gt;S&lt;/math&gt;<br /> such that no two adjacent vertices have the same color,<br /> i.e., &lt;math&gt;f(x) \neq f(y)&lt;/math&gt; whenever &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; are adjacent. This &#039;&#039;&#039;C.&#039;&#039;&#039; is called a &#039;&#039;&#039;proper&#039;&#039;&#039; (&#039;&#039;&#039;valid&#039;&#039;&#039;,<br /> &#039;&#039;&#039;legitimate&#039;&#039;&#039;, &#039;&#039;&#039;good&#039;&#039;&#039;) coloring.<br /> <br /> &lt;math&gt;f&lt;/math&gt; is called &#039;&#039;&#039;&lt;math&gt;k&lt;/math&gt;-coloring&#039;&#039;&#039; of &lt;math&gt;G&lt;/math&gt; if &lt;math&gt;f&lt;/math&gt; is a coloring of &lt;math&gt;G&lt;/math&gt; into &lt;math&gt;k&lt;/math&gt; colors,<br /> i.e. &lt;math&gt;k=|\{f(p): p\in V(G)\}|&lt;/math&gt;.<br /> <br /> It is &lt;math&gt;NP&lt;/math&gt;-complete to decide if a given graph &lt;math&gt;G&lt;/math&gt; admits<br /> a &lt;math&gt;k&lt;/math&gt;-coloring for a given &lt;math&gt;k&lt;/math&gt; except for the cases &lt;math&gt;k&lt;/math&gt; = 1 and &lt;math&gt;k&lt;/math&gt; = 2.<br /> Graph coloring remains &lt;math&gt;NP&lt;/math&gt;-complete even on<br /> planar graphs of degree at most 4.<br /> <br /> &#039;&#039;&#039;2.&#039;&#039;&#039; <br /> ==See==<br /> *&#039;&#039;Large-block schema&#039;&#039;.</div> Glk