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>'''Coloring, colouring''' <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>'''Coloring, colouring''' <ins style="font-weight: bold; text-decoration: none;">— ''[[</ins>раскраска<ins style="font-weight: bold; text-decoration: none;">]]</ins>.<ins style="font-weight: bold; text-decoration: none;">'' </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>'''1.''' Let <math>G</math> be a graph and <math>S</math> be a set of colors. A '''coloring''' of <math>G</math> 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>'''1.''' Let <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G</math> 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 <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>S</math> be a set of colors. A '''coloring''' of <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G</math> 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 <math>f: V(G) \rightarrow S</math> from the vertex set <math>V(G)</math> into <math>S</math></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 <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>f: V(G) \rightarrow S</math> from the <ins style="font-weight: bold; text-decoration: none;">[[</ins>vertex<ins style="font-weight: bold; text-decoration: none;">]] </ins>set <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>V(G)</math> into <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>S</math></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., <math>f(x) \neq f(y)</math> whenever <math>x</math> and <math>y</math> are adjacent. This '''C.''' is called a '''proper''' ('''valid''',</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., <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>f(x) \neq f(y)</math> whenever <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>x</math> and <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>y</math> are adjacent. This '''C.''' is called a '''proper''' ('''valid''',</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>'''legitimate''', '''good''') 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>'''legitimate''', '''good''') 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><math>f</math> is called '''<math>k</math>-coloring''' of <math>G</math> if <math>f</math> is a coloring of <math>G</math> into <math>k</math> 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><math><ins style="font-weight: bold; text-decoration: none;">\,</ins>f</math> is called '''<ins style="font-weight: bold; text-decoration: none;">[[k-Coloring|</ins><math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k</math>-coloring<ins style="font-weight: bold; text-decoration: none;">]]</ins>''' of <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G</math> if <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>f</math> is a coloring of <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G</math> into <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k</math> 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. <math>k=|\{f(p): p\in V(G)\}|</math>.</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. <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k=|\{f(p): p\in V(G)\}|</math>.</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 <math>NP</math>-complete to decide if a given graph <math>G</math> 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 <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>NP</math>-complete to decide if a given graph <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G</math> 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 <math>k</math>-coloring for a given <math>k</math> except for the cases <math>k</math> = 1 and <math>k</math> = 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 <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k</math>-coloring for a given <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k</math> except for the cases <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k</math> = 1 and <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>k</math> = 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 <math>NP</math>-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 <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>NP</math>-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>'''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>'''2.'''</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>*''Large-block schema''.</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>* ''<ins style="font-weight: bold; text-decoration: none;">[[</ins>Large-block schema<ins style="font-weight: bold; text-decoration: none;">]]</ins>''<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>Новая страница: «'''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> …»</p>
<p><b>Новая страница</b></p><div>'''Coloring, colouring''' --- раскраска. <br />
<br />
'''1.''' Let <math>G</math> be a graph and <math>S</math> be a set of colors. A '''coloring''' of <math>G</math> is<br />
a mapping <math>f: V(G) \rightarrow S</math> from the vertex set <math>V(G)</math> into <math>S</math><br />
such that no two adjacent vertices have the same color,<br />
i.e., <math>f(x) \neq f(y)</math> whenever <math>x</math> and <math>y</math> are adjacent. This '''C.''' is called a '''proper''' ('''valid''',<br />
'''legitimate''', '''good''') coloring.<br />
<br />
<math>f</math> is called '''<math>k</math>-coloring''' of <math>G</math> if <math>f</math> is a coloring of <math>G</math> into <math>k</math> colors,<br />
i.e. <math>k=|\{f(p): p\in V(G)\}|</math>.<br />
<br />
It is <math>NP</math>-complete to decide if a given graph <math>G</math> admits<br />
a <math>k</math>-coloring for a given <math>k</math> except for the cases <math>k</math> = 1 and <math>k</math> = 2.<br />
Graph coloring remains <math>NP</math>-complete even on<br />
planar graphs of degree at most 4.<br />
<br />
'''2.''' <br />
==See==<br />
*''Large-block schema''.</div>
Glk