Циклы в графах

Допустим, утверждение задачи неверно для какого-либо графа на 2008 вершинах. Будем говорить, что вершина портит вершину , если вершину можно перекрасить так, чтобы вершина , которая не была плохой, стала плохой. Заметим, что если степень вершины не равна 2 , её можно испортить не более чем одним способом.

Сформулируем задачу на языке графов и заменим разбиение на фракции раскраской вершин графа на три цвета, а депутата-единолюба на плохую вершину.

Допустим, утверждение задачи неверно для какого-либо графа на 2008 вершинах. Будем говорить, что вершина портит вершину , если вершину можно перекрасить так, чтобы вершина , которая не была плохой, стала плохой.

Заметим, что если степень вершины не равна 2 , её можно испортить не более чем одним способом. В самом деле, вершины степени 0 и 1 всегда плохие, поэтому испортить их вообще нельзя. Пусть степень вершины больше 2. Если её можно испортить, то все соседние вершины, кроме одной, покрашены в один цвет, а одна — в другой, и этот цвет, как и вершина, которую надо в него перекрашивать, определены однозначно. Вершину же степени 2 можно, очевидно, испортить не более чем двумя способами.

Каждую вершину можно перекрасить двумя способами. Поэтому количество способов, которыми можно испортить вершины нашего графа, равно . С другой стороны, столько же должно получиться, если просуммировать по всем вершинам количество способов, которыми они могут быть испорчены. Поскольку в этой сумме все слагаемые не больше 2 , все они должны равняться 2. Это возможно только если в нашем графе степень каждой вершины равна 2 . Стало быть, он распадается на непересекающиеся циклы, причём каждую вершину каждого цикла можно испортить двумя способами. Такое возможно только если каждая вершина и те вершины, что идут в цикле через одну от неё, покрашены в три разных цвета. Нетрудно показать, что длина цикла в этом случае должна делиться на 3 . Но 2008 на 3 не делится.

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Пусть — наш граф, — множество всех остовных деревьев графа , а М( ) — множество всех остовных подграфов графа , имеющих ровно один цикл. Рассмотрим произвольное дерево . В нем нечетное число ребер, следовательно, количество не вошедших в ребер графа также нечетно. Если к дереву добавить любое не вошедшее в него ребро графа , то получится граф из . Всего таким образом из дерева получается нечетное число графов из . Наоборот, рассмотрим любой граф и его единственный цикл . Граф может быть получен добавлением ребра к тем деревьям, которые получаются из удалением одного из ребер цикла . Так как граф двудольный, то в цикле — четное число ребер, следовательно, у графа — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве четное число остовных деревьев.

Пусть — наши пары. Каждую девочку соединим с другой девочкой, знакомой с . В результате получится граф на вершинах , с 2015 рёбрами.

Пусть — наши пары. Каждую девочку соединим с другой девочкой, знакомой с . В результате получится граф на вершинах , с 2015 рёбрами. Нам нужно покрасить этот граф правильным образом в три цвета, это и будет искомая покраска девочек. Рассмотрим компоненту связности построенного графа, пусть в ней вершин, тогда и рёбер в ней тоже (Мы провели по одному ребру из каждой вершины этой компоненты связности, из вершин вне компоненты рёбра в нее не входят). Если есть вершина степени 1 , удалим ее, эту вершину можно будет легко докрасить после покраски остальных вершин компоненты. После серии таких операций наша компонента связности будет иметь минимальную степень вершины 2 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.

Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл.

Ответ. Вася.

Решение. Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл. Значит, концы цепи длины 2 соединять с другими точками нельзя. Стратегия Васи: после каждого хода Пети соединять ту же красную точку с какой-то синей, которая ещё не соединена ни с какой другой. Тогда после каждой пары ходов Пети и Васи число не соединённых с другими синих точек будет уменьшаться на 2 , и после 50 -го хода Васи каждая синяя точка будет концом цепи длины 2. Своим 51-м ходом Петя создаст цепь длины 3 и проиграет.

Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если , то в одном из пауков выбраны все 4 города, что противоречит условию.

Ответ. . Решение. Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если , то в одном из пауков выбраны все 4 города, что противоречит условию.

Оценка. Рассмотрим граф: вершины — города, рёбра — дороги. Если граф не связный, будем проводить по ребру между компонентами связности, пока он не станет связным. Ясно, что такая процедура не увеличит искомое число и не добавит в граф циклы.

Итак, мы можем считать, что рассматриваемый граф — дерево. Индукцией по докажем, что в дереве на вершинах можно выбрать вершин так, чтобы выполнялось условие задачи. Такое множество вершин будем называть хорошим.

База: очевидна.
Переход: от всех меньших к . Подвесим дерево за вершину и рассмотрим вершину самого нижнего уровня. Если у ее предка не менее трёх потомков, то выкинем и всех ее потомков.

В оставшемся дереве выберем хорошее множество и добавим всех потомков . Полученное множество будет хорошим для исходного дерева, и в нём не менее вершины.

Если у вершины ровно 2 потомка и , то рассмотрим её предка . Выкинем вершины и и, если понадобится, добавим рёбра для того, чтобы получилось дерево. В получившемся дереве выберем хорошее множество из не менее вершин, после чего добавим к нему вершины и .

Итак, мы можем считать, что у любой вершины с нижнего уровня предок имеет степень ровно 2. Пусть — вершина нижнего уровня, — её предок, — предок . У всех потомков (не обязательно прямых) степень 1 или 2 . Если у всего потомков (не обязательно прямых). Выкинем и всех её (не обязательно прямых) потомков. В оставшемся графе хорошее множество содержит не менее вершин. Добавим к ним всех потомков . Получим хорошее множество из не менее вершин в исходном дереве.

Наконец, если , то единственные потомки — это и . Пусть — предок . Выкинем вершины и . В получившемся графе выберем хорошее множество из не менее вершин, после чего добавим к нему вершины и .

Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1. Предположим, что в графе нашелся нечетный цикл. Пройдем по этому циклу и будем следить за изменением расстояния при переходе по каждому ребру.

Рассмотрим граф, в котором вершины — города, ребра — наличие сообщения. Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1. Предположим, что в графе нашелся нечетный цикл. Пройдем по этому циклу и будем следить за изменением расстояния при переходе по каждому ребру. Так как цикл нечетный, то если каждый раз расстояние менялось ровно на 1 , то придя в исходную вершину мы бы получили расстояние другой четности, чего быть не может. Следовательно, хотя бы один раз при проходе по ребру цикла расстояние не изменилось. То есть существует ребро , что оба конца этого ребра находятся на одинаковом расстоянии от столицы.

Назовем набор ребер хорошим, если при удалении из графа всех ребер, кроме ребер этого набора, расстояние до столицы не изменятся. Докажем, что хорошие наборы можно разбить на пары следующим образом: если в наборе есть , то уберем из набора, а если нет , то добавим. То есть надо доказать, что если мы удалили несколько рёбер и расстояния не изменились, то при удалении/добавлении ребра расстояния также не изменятся. Про добавление ребра утверждение очевидно, так как от добавления ребра расстояния не могут уменьшиться, а увеличиться не могут, так как они равны расстояниям в графе, в котором никакие ребра не удалены. Предположим, что при удалении расстояние от какого-то города до столицы увеличилось. Тогда кратчайший путь от до проходил через . Но такого не может быть, ведь расстояния от концов до одинаковы, и мы могли, не проходя по ребру , добраться от до за меньшее число шагов.

Таким образом, все наборы разбились на пары, то есть их четное число. Противоречие.

Подвесим граф за вершину-столицу С. Вспомним, что вершины -го яруса определяются в точности как те вершины, расстояние от которых до C равно .

Введём граф, в котором вершины — города, рёбра — наличие авиасообщения. Подвесим граф за вершину-столицу С. Вспомним, что вершины -го яруса определяются в точности как те вершины, расстояние от которых до C равно . В таком графе рёбра могут быть либо внутри одного яруса, либо между ярусами с номерами, отличающимися на 1. Мы рассматриваем множества ребер, при удалении которых сохраняется ярус каждой вершины в нашем графе, будем называть их интересными. Если некоторое ребро соединяет две вершины одного яруса, то при включении или исключении интересность множества ребер не меняется. Таким образом, все интересные множества разбиваются на пары, что противоречит условию. Следовательно, в графе нет ребер, соединяющих вершины одного яруса. Тогда в любом цикле ярусы соседних вершин отличаются на 1 , тем самым они имеют разную четность. Значит, любой цикл в данном графе имеет четную длину, что и требовалось.

Можно оставить только остовное дерево.

Ответ: . Решение. Рассмотрим граф, вершинами которого являются города, ребрами — дороги. Понятно, что , в противном случае граф на оставшихся ребрах не будет связным. Докажем, что в этом графе всегда можно выделить остовное дерево, удовлетворяющее условиям. Будем последовательно удалять ребра из графа. Пусть в графе к текущему моменту есть цикл, проходящий по вершинам . Предположим, что мы не можем удалить ребро (считаем, что ) с сохранением всех условий. Тогда один из городов и должен быть важным, а другой — не важным. Поэтому если мы не можем удалить ни одно из ребер цикла, то в нем чередуются важные и не важные города. В этом случае удалим любое ребро из нашего цикла. Каждый не важный город будет по-прежнему соединен с важным. В какой-то момент в графе не останется циклов, а все условия будут выполнены. Поэтому оставшийся граф дерево, и ребер в нем ровно .

Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1.

Рассмотрим граф, в котором вершины — города, ребра — наличие сообщения. Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1. Предположим, что в графе нашелся нечетный цикл. Пройдем по этому циклу и будем следить за изменением расстояния при переходе по каждому ребру. Так как цикл нечетный, то если каждый раз расстояние менялось ровно на 1 , то придя в исходную вершину мы бы получили расстояние другой четности, чего быть не может. Следовательно, хотя бы один раз при проходе по ребру цикла расстояние не изменилось. То есть существует ребро , что оба конца этого ребра находятся на одинаковом расстоянии от столицы.

Назовем набор ребер хорошим, если при удалении из графа всех ребер, кроме ребер этого набора, расстояние до столицы не изменятся. Докажем, что хорошие наборы можно разбить на пары следующим образом: если в наборе есть , то уберем из набора, а если нет , то добавим. То есть надо доказать, что если мы удалили несколько рёбер и расстояния не изменились, то при удалении/добавлении ребра расстояния также не изменятся. Про добавление ребра утверждение очевидно, так как от добавления ребра расстояния не могут уменьшиться, а увеличиться не могут, так как они равны расстояниям в графе, в котором никакие ребра не удалены. Предположим, что при удалении расстояние от какого-то города до столицы увеличилось. Тогда кратчайший путь от до проходил через . Но такого не может быть, ведь расстояния от концов до одинаковы, и мы могли, не проходя по ребру , добраться от до за меньшее число шагов.

Таким образом, все наборы разбились на пары, то есть их четное число. Противоречие.

Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина , и она соединена ребрами цвета 1 с вершинами . Поскольку , то остались еще вершины , каждая из которых соединена с вершиной ребром какого-то другого цвета.

Решение 1. Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина , и она соединена ребрами цвета 1 с вершинами . Поскольку , то остались еще вершины , каждая из которых соединена с вершиной ребром какого-то другого цвета. Рассмотрим вершину , пусть она соединена с ребром цвета . Тогда должна быть соединена с каждой из вершин либо ребром цвета 1 , либо ребром цвета (иначе будет треугольник с разноцветными сторонами). Если все эти ребер окрашены в цвет , то всего из вершины выходит ребро цвета , что противоречит выбору вершины и цвета 1 . Следовательно, хотя бы одно из этих ребер окрашено в цвет 1. Таким образом, из каждой вершины выходит хотя бы одно ребро цвета 1 , и всего мы имеем ребро цвета 1 , что противоречит условию. Следовательно, обязательно найдутся три вершины, все три ребра между которыми покрашены в разные цвета.

Решение 2. Пусть в любом треугольнике есть два одноцветных ребра. Так как ребер любого цвета не более , то они образуют несвязный граф на данных нам вершинах. Для каждого цвета такой граф распадается хотя бы на две компоненты связности. Среди всех таких компонент связности (для всех цветов) найдем наибольшую по количеству вершин компоненты связности (пусть ее ребра окрашены в цвет 1). Очевидно, существует вершина , не вошедшая в . Рассмотрим любую вершину из , она соединена с ребром не цвета 1 , пусть это ребро цвета 2 . Если вершина из соединена с ребром цвета 1 , то также соединена с ребром цвета 2 (иначе будет треугольник будет иметь разноцветными ребрами). Такими же рассуждениями мы получим, что соединена со всеми вершинами компоненты связности ребрами цвета 2 , но тогда существует компонента связности цвета 2 , содержащая все вершины из и вершину . Противоречие с максимальностью компоненты связности .