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

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

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

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

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

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

Будем доказывать это утверждение индукцией по числу участников.

База для и очевидна.

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

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

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

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

Рассмотрим команду Г. Она не могла играть с командами А, Б и В из первого утверждения, не могла играть с командами Д, В и Е из второго утверждения и не могла играть с командами Ж, Д и Б из третьего утверждения. Значит, команда Г играла с командой З. Рассмотрим команду В. Она не могла играть с командами А, Б и Г из первого утверждения, не могла играть с командами Г, Д и Е из второго утверждения и не могла играть с командами Г и З, так как они играют между собой. Значит, команда В играла с командой Ж. Рассмотрим команду Д. Она не могла играть с командами Г, В и Е из второго утверждения, не могла играть с командами Ж, Б и Г из третьего утверждения и не могла играть с командами Г, З, В и Ж, так как они играют между собой. Значит, Д играла с командой А. Тогда оставшиеся две команды — Б и Е играют между собой.

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

Если Вова сыграл 11 игр, то общее число игр в турнире равно — а это не целое число, столько игр быть не могло.

Сыграть 14 игр Вова тоже не мог, потому что это больше, чем Андрей и Боря вместе взятые. Не играл же Вова сам с собой!

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

Решаем это уравнение и получаем Так как есть еще внешняя грань, то треугольников

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

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

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

А, значит,

Замечание. На самом деле верно более общее утверждение. Если каждый цикл графа имеет длину хотя бы То верны следующие неравенства:

Пусть существуют два хороших хороших множества которые содержат различное количество элементов. Без ограничений общности считаем, что

Покажем, что не является максимальным по включению.

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

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

Пусть — число всех ребер в путях из на шаге данного алгоритма, — число общих ребер в путях из и на шаге данного алгоритма. Рассмотрим величину

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

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

1.

имеют общий конец с каким-то путем из

2.

не имеют общих вершин с любым путем из

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

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

И теперь

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

Итак, всего вариантов: тетраэдр ( октаэдр икосаэдр куб додекаэдр

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

База: — очевидно.

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

_________________________________________________________________________________________________________________________________________________________________________________

Следствие. Внутри любого пятиугольника есть точка, из которой "видно"все точки этого пятиугольника.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

База: представляется треугольником.

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

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

Пусть мы убрали ребро, которое соединяло вершины и Пойдем от противного. Пусть граф остался связным. Заметим, что тогда вершины и точно попали в разные компоненты связности. Рассмотрим компоненту связности, которая содержит вершину В этой компоненте все вершины, кроме вершины имеют степень Следовательно, там только одна вершина нечётной степени. А этого быть не может в силу того, что сумма степеней вершин любого графа равна удвоенному числу ребер, а значит, чётна.

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

Давайте начнем “гулять” по графу, пока можем попадать в новую вершину. В силу конечного количества вершин в какой-то момент мы остановимся. Пусть мы остановились в вершине Тогда все ребра из точно ведут в этот путь. Этих ребер хотя бы два. Пусть эти ребра ведут в вершины и Заметим, что образовалось хотя бы три цикла. Путь из в и ребро путь из в и ребро путь из в и ребра и Тогда путь из в и путь из в имеют четную длину, но тогда путь из в тоже четной длины. Следовательно, цикл содержащий ребра и путь из в — четный.

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

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

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