https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Smallest_Last 2026-05-06T22:04:52Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=Smallest_Last&diff=6489&oldid=prev 2017-12-09T12:04:39Z

<p>Новая страница: «Алгоритм для задачи [https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 р…»</p> <p><b>Новая страница</b></p><div>Алгоритм для задачи [https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 раскраски графа].<br /> <br /> Пусть у нас есть граф ''G=(V,E)''.<br /> Сначала определим нумерацию вершин, построим ее с конца в начало:<br /> * Последняя вершина &lt;m&gt;v_n&lt;/m&gt; — вершина с минимальной степенью.<br /> * Предпоследняя вершина &lt;m&gt;v_{n-1}&lt;/m&gt; — вершина с минимальной степенью в графе G без вершины &lt;m&gt;v_n&lt;/m&gt;<br /> …<br /> * Вершина &lt;m&gt;v_i&lt;/m&gt; — вершина с минимальной степенью в графе G без вершин &lt;m&gt;v_{i+1} \ldots v_n&lt;/m&gt;<br /> * Вершина &lt;m&gt;v_1&lt;/m&gt; — та, что осталась.<br /> <br /> Затем берем и последовательно красим вершины.<br /> * Если к ''i''-й вершине мы использовали только ''k'' красок, пробуем<br /> ** покрасить вершину в краску с минимальным номером из этих<br /> ** это невозможно (вершина степени k, и все предыдущие раскрашены в разные цвета) — вводим новый цвет, k+1</div>

StasFomin