Разделы 
Дополнительно
Задача по математике - 1965
2019-01-22 
В стране 2001 город, некоторые пары городов соединены дорогами, причем из каждого города выходит хотя бы одна дорога и нет города, соединенного дорогами со всеми остальными. Назовем множество городов $D$ доминирующим, если любой не входящий в $D$ город соединен дорогой с одним из городов множества $D$. Известно, что в любом доминирующем множестве хотя бы $к$ городов. Докажите, что страну можно разбить на 2001 - $k$ республик так, что никакие два города из одной республики не будут соединены дорогой.
Решение:
Построим граф, вершины которого соответствуют городам, а ребра - дорогам. В задаче требуется покрасить вершины этого графа в 2001 - к цветов так, что никакие две вершины одного цвета не соединены ребром (такая раскраска называется правильной).
Рассмотрим вершину $А$ наибольшей степени, пусть из этой вершины выходит $s$ ребер ($s < 2000$). Обозначим через $V$ множество из $s$ вершин, соединенных с $А$, пусть $W$ - множество из 2000 - $s$ оставшихся вершин. Рассмотрим два случая.
1) Пусть в множестве $W$ есть две соединенные ребром вершины $В$ и $C$. Тогда рассмотрим множество $U$, состоящее из вершины $А$ и всех вершин множества $W$, кроме $C$. В этом множестве $2000 - s$ вершин и любая не входящая в $U$ вершина соединена ребром с одной из вершин множества $U$ (либо с вершиной $А$, либо с $В$). Следовательно, $2000 - s \geq k$.
Остается заметить, что из каждой вершины выходит не более $s$ ребер, следовательно, эти вершины можно по очереди покрасить в $s + 1$ цвет так, чтобы никакие две вершины одного цвета не были соединены ребром (вершину нельзя красить в цвета ее соседей, которых не более, чем $s$, а в нашем распоряжении $s + 1$ цвет). Неравенство $s + 1 = 2001 - (2000 - s) \leq 2001 - k$ завершает доказательство задачи в этом случае.
2) Пусть никакие две вершины множества $W$ не соединены ребром. Покрасим все эти вершины в цвет $1$, в этот же цвет можно покрасить вершину $A$ (она не соединена ребром ни с одной вершиной из $W$). Заметим, что в этом случае вершины из множества $W$ должны быть соединены с вершинами из множества $V$ (так как из каждой вершины выходит хотя бы одно ребро). Это означает, что среди вершин множества $V$ есть две не соединенные ребром (иначе в этом множестве есть вершина, из которой выходит более $s$ ребер - к $s - 1$ остальным вершинам множества $V$, к вершине $A$ и к вершинам множества $W$). Так как среди $s$ вершин множества $V$ есть две не соединенные ребром, вершины этого множества можно покрасить в $s - 1$ цвет. Таким образом, все вершины оказались раскрашены в $s$ цветов и никакие две вершины не соединены ребром. Так как все $s$ вершин из множества $V$ соединены ребром с вершиной $A$, то $2001 - s \geq k$, следовательно, $s = 2001 - (2001 - s) < 2001 - k$, что и требовалось доказать.
В стране 2001 город, некоторые пары городов соединены дорогами, причем из каждого города выходит хотя бы одна дорога и нет города, соединенного дорогами со всеми остальными. Назовем множество городов $D$ доминирующим, если любой не входящий в $D$ город соединен дорогой с одним из городов множества $D$. Известно, что в любом доминирующем множестве хотя бы $к$ городов. Докажите, что страну можно разбить на 2001 - $k$ республик так, что никакие два города из одной республики не будут соединены дорогой.
Решение:
Построим граф, вершины которого соответствуют городам, а ребра - дорогам. В задаче требуется покрасить вершины этого графа в 2001 - к цветов так, что никакие две вершины одного цвета не соединены ребром (такая раскраска называется правильной).
Рассмотрим вершину $А$ наибольшей степени, пусть из этой вершины выходит $s$ ребер ($s < 2000$). Обозначим через $V$ множество из $s$ вершин, соединенных с $А$, пусть $W$ - множество из 2000 - $s$ оставшихся вершин. Рассмотрим два случая.
1) Пусть в множестве $W$ есть две соединенные ребром вершины $В$ и $C$. Тогда рассмотрим множество $U$, состоящее из вершины $А$ и всех вершин множества $W$, кроме $C$. В этом множестве $2000 - s$ вершин и любая не входящая в $U$ вершина соединена ребром с одной из вершин множества $U$ (либо с вершиной $А$, либо с $В$). Следовательно, $2000 - s \geq k$.
Остается заметить, что из каждой вершины выходит не более $s$ ребер, следовательно, эти вершины можно по очереди покрасить в $s + 1$ цвет так, чтобы никакие две вершины одного цвета не были соединены ребром (вершину нельзя красить в цвета ее соседей, которых не более, чем $s$, а в нашем распоряжении $s + 1$ цвет). Неравенство $s + 1 = 2001 - (2000 - s) \leq 2001 - k$ завершает доказательство задачи в этом случае.
2) Пусть никакие две вершины множества $W$ не соединены ребром. Покрасим все эти вершины в цвет $1$, в этот же цвет можно покрасить вершину $A$ (она не соединена ребром ни с одной вершиной из $W$). Заметим, что в этом случае вершины из множества $W$ должны быть соединены с вершинами из множества $V$ (так как из каждой вершины выходит хотя бы одно ребро). Это означает, что среди вершин множества $V$ есть две не соединенные ребром (иначе в этом множестве есть вершина, из которой выходит более $s$ ребер - к $s - 1$ остальным вершинам множества $V$, к вершине $A$ и к вершинам множества $W$). Так как среди $s$ вершин множества $V$ есть две не соединенные ребром, вершины этого множества можно покрасить в $s - 1$ цвет. Таким образом, все вершины оказались раскрашены в $s$ цветов и никакие две вершины не соединены ребром. Так как все $s$ вершин из множества $V$ соединены ребром с вершиной $A$, то $2001 - s \geq k$, следовательно, $s = 2001 - (2001 - s) < 2001 - k$, что и требовалось доказать.
