Графы и турниры

(a) Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в цвета правильным образом (то есть так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.

Выберем по одному ребру в каждом нечётном цикле графа и удалим их графа. Обозначим полученный граф В нем нет циклов нечётной длины. Любой такой граф можно окрасить в два цвета правильным образом. Зафиксируем одну такую раскраску, и присвоим одному цвету номер а другому номер

Рассмотрим граф, состоящий из удаленных ребер, который мы будем обозначать В нем степень каждой вершины не превосходит так как по условию задачи через каждую вершину в исходном графе проходит не более нечетных циклов. Ясно, что вершины такого графа можно окрасить в цвет. Действительно, вершины можно красить по очереди, и поскольку на каждом этапе окрашиваемая вершина соединена не более чем с уже окрашенными, для нее существует хотя бы один свободный цвет. Зафиксируем одну такую раскраску, и пронумеруем в ней цвета числами от до

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

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

База для графа из одной вершины очевидна.

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

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

Если для некоторого в графе через вершину не проходит ни один цикл нечётной длины, то циклов нечётной длины в этом графе нет. В этом случае мы можем так перекрасить вершины графа (используя лишь цвета и ), чтобы все рёбра в этом графе соединяли пары вершин разных цветов. Так как все остальные вершины графа покрашены в цвета, отличные от и , то и во всём графе никакие две вершины одинакового цвета не соединены ребром.

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

Будем решать чуть более общую задачу – пусть число ребер в графе не превосходит Рассмотрим отдельно случай Пусть в графе вершин и ребер. Пусть в нем также ровно изолированных вершин. Если то задача уже решена. Выделим все изолированные вершины в отдельное независимое множество. Будем обозначать граф, из которого удалили все изолированные вершины, как Если то поскольку в вершин и ребер, в нем существует висячая вершина. Добавим ее в независимое множество, и удалим из графа ее соседа со всеми исходящими из него ребрами. Ясно, что после этого преобразования множество осталось независимым. После этого действия число вершин в графе сократилось на а ребер – хотя бы на поэтому разница между числом вершин и ребер сократилась не более чем на 1. Будем повторять эту операцию пока в графе вершин больше чем ребер. Ясно, что мы гарантированно сможем ее провести раз. В результате мы сформировали независимое множество размера хотя бы что и требовалось.

Теперь перейдем к случаю произвольного Оценим среднее количество ребер в подграфе на вершин. Достаточно найти сумму количества ребер во всех таких подграфах и поделить на их количество: А первое можно вычислить альтернативным способом: как сумму по всем ребрам числа подграфов размера его содержащих. Это число не превосходит Если ребро фиксировано, то чтобы дополнить его до подграфа размера необходимо выбрать ровно среди оставшихся Итак,

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

Просуммируем по всем раскраскам графа количество одноцветных копий графа Эту сумму можно вычислить вторым способом, как сумму по всем подграфам входящим в раскрасок, в которых данный подграф является одноцветным. А такое число, разумеется, равно

 – количество способов выбрать подграф  – количество способов выбрать цвет  – количество способов раскрасить оставшиеся ребра.

По принципу Дирихле, существует раскраска графа, в которой число одноцветных подграфов составляет хотя бы

что и требовалось доказать.

Найдем в графе наименьший цикл нечетной длины. Удалим все вершины, принадлежащие этому циклу, и все ребра, исходящие из этих вершин. В оставшемся (не обязательно связном) графе не будет нечетных циклов, т.к. по условию любые два пересекались по вершине. Тогда наш граф двудольный, а значит, мы можем покрасить его в цвета.

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

Докажем индукцией по количеству вершин. База для треугольника очевидна, так вершин три и все три цвета присутствуют.

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

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

Итак, предположим, что такой тройки точек нет. Пусть точка окрашена в цвет а точка — в цвет тогда точка — снова в цвет иначе мы получим нужную тройку либо две соседние вершины одного цвета. Далее по аналогичным рассуждениям покрашена в цвет , — в цвет и так далее. В конечном итоге мы получим, что все вершины раскрашены в цвета и а вершины третьего цвета нет, противоречие.

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

Пусть у нас есть дерево на вершинах. Удалим висячую вершину и выходящее из неё ребро Оставшееся дерево по предположению можно обойти по рёбрам. Вернём вершину и вставим в маршрут кусок Количество пройденных рёбер станет что и требовалось.

Докажем индукцией по количеству игроков. База для двух игроков очевидна.

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

Докажем индукцией по количеству вершин. Если в графе одна вершина, то утверждение задачи очевидно.

Пусть в графе вершин. В графе есть такая вершина при выкидывании которой граф не теряет связность. Выкинем её. В оставшемся графе по предположению индукции проведём нужную раскраску. Вернём вершину

Какая проблема могла возникнуть при возврате Чтобы не была одного цвета с одним из соседей, просто покрасим её в один из цветов, в который не покрашены соседи (такие цвета есть, потому что соседей не больше а цветов ).

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

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

Итак, для графа на вершине утверждение очевидно. Рассмотрим граф на вершинах. Выкинем из него вершину так, чтобы оставшийся граф был связным. Полученный граф по предположению можно разбить на две части так как нужно. Теперь вернем вершину Она обязательно соединена с какой-то вершиной Добавим в часть, в которой нет

Докажем задачу индукцией по

Прежде чем доказывать базу, давайте поймём, какое минимальное значение может быть. Ясно, что оно ограничено, потому что, например, при описанная в задаче конструкция вообще невозможна.

Итак, в графе не более рёбер. Значит откуда . При описанная в условии конструкция реализуется, притом только если граф полный (это следует из рассмотренного неравенства).

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

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

Если же её степень хотя бы то и степень всех остальных хотя бы Значит, если её выкинуть, то степень соседних с ней вершин будет хотя бы а у несоседних — хотя бы Что и требовалось.

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

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

туров уже может быть, составим пример. Пусть в первые туров команда набирает очков, другие если играли с или если играли между собой. Тогда в оставшиеся тура команда набирает очков, а команда , у которой самое большее количество очков после туров, набирает очков. Остальные команды разыгрывают очки между собой.

Первое решение. Докажем сначала следующую лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер.

Доказательство. Рассмотрим вершину наибольшей степени (пусть Пусть вершина cоединена с Ясно, что никакие и не могут быть соединены, потому что иначе в графе будет треугольник Степень оставшихся вершин не превосходит Таким образом, всего в графе не более Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем по индукции.

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

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

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

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

Тогда возьмём вершину наибольшей степени (её степень не менее ), назовём её и рассмотрим всех знакомных этого человека. Если бы они все рассорились, из графа удалилось бы не менее ребер. Таким образом, у найдутся знакомых, которые по прежнему дружат, и вместе с они образуют компанию из трёх друзей.

Второе решение. Cначала докажем лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер. Докажем это.

Рассмотрим вершину наибольшей степени (пусть ). Пусть вершина cоединена с Ясно, что никакие и не могут быть соединены, потому что иначе в графе будет треугольник Степень оставшихся вершин не превосходит Таким образом, всего в графе не более Лемма доказана.

Давайте предположим, что в полученном графе нет треугольников. Тогда по лемме в графе не более рёбер, но их Пришли к противоречию.

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

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

Всего в графе есть потенциальных циклических треугольников. Что может сделать треугольник не циклическим? Либо в нём нет какого-то ребра, либо в нём две стрелки идут в одну вершину. Каждое отсутсвующее ребро портит треугольников. Все такие рёбра портят не более треугольников (потому что их ). По условию в каждую вершину входит стрелочки, то есть каждая вершина портит треугольников, а значит всего таким образом испорчено не более треугольников. К сожалению, Однако по условию из каждой вершины выходит два отсутствующих ребра. То есть если игрок сыграл с и вничью, то рёбра и портят треугольник значит мы его посчитали дважды. Таким образом, всего испорчено не более треугольников. Следовательно, хотя бы один будет циклическим, что и требовалось.

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

Пусть из вершины ведёт два ребра Так как нет треугольников, то (здесь смотрим по модулю ). Также так как — наименьший получаем, что Из этих рассуждений следует, что из в идёт максимум два ребра, так как пусть есть рёбра Тогда можно расположить индексы так, что по модулю а значит Противоречие.

Осталось посчитать рёбра. Тогда из в вершины цикла ведёт не более рёбер. Тогда найдется вершина цикла степени не более, чем Значит есть вершина степени что и требовалось.

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

Сумма степеней вершин четная, есть то она равна как минимум а тогда ребер хотя бы из чего следует, что найдется цикл, а значит при заведомо найдётся несколько детей, которых можно посадить за круглый стол так, чтобы каждый знал обоих своих соседей (очевидно, что друзья знают друг друга). Если же то можно построить пример, когда цикла не будет и, следовательно, указанная рассадка не возможна. Например, возьмем вершин, соединим их путем ( ребер) и затем ко всем вершинам, кроме концов добавим “висячую” вершину.

Рассмотрим граф, в котором вершины — числа, ребро проводится, если модуль разности этих чисел — простое число. Будем красить каждую компоненту связности этого графа в два цвета: сначала покрасим любую вершину в красный. Затем покрасим всех её соседей в синий. Затем всех соседей синих, которые ещё не покрашены, в красный. Затем соседей красных в синий. И так далее. Легко видеть, что у каждой красной вершины будет хотя бы один синий сосед, а у каждой синей — хотя бы один красный. В каждой компоненте связности выберем цвет, вершин которого не более половины, и подчеркнем вершины этого цвета. Каждая неподчеркнутая вершина будет соединена хотя бы с одной подчеркнутой.

Пример графа показан на рисунке. Множество содержит вершину, множество — вершину.

_________________________________________________________________________________________________________________________________________________________________________________

Оценка. Для графа и некоторого множества его ребер через обозначим граф, получающийся из графа удалением всех его ребер, входящих в , т.е. граф .

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть — связный граф, и пусть и — два непересекающихся множества его ребер. Обозначим через () количество компонент связности графа . Тогда количество компонент связности графа не меньше, чем .

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

следовательно, .

Предположим, что существует. Тогда количество рёбер в нём не превосходит Однако сумма степеней всех вершин хотя бы то есть рёбер не меньше, чем Пришли к противоречию.