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

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

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

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

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

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

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

С другой стороны, перелёта всегда достаточно, чтобы добраться от любого города до любого.

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

Каждый город на уровне может быть соединён только с городами на уровнях и

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

Это означает, что у нас не может быть более

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

Индукцией по докажем утверждение задачи для любого ладейно связного множества состоящего из клеток. Клетками далее называем клетки множества База очевидна.

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

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

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

Если все три множества состоят из чётного числа клеток, применим предположение индукции к этим множествам, а потом добавим доминошку

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

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

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

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

Пронумеруем всех участников турнира числами от до Для любого для -го участника — количество его друзей друзей,

где — множество всех друзей -го участника. Предположим противное: каждое меньше, чем среднее количество друзей, тогда

(удвоенного количества пар друзей). Переставив слагаемые в сумме видим, что равно сумме

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Если первый успеет разбить вершины на компоненты связности размера не меньше — он победил.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 2. Каждое синее ребро упомянуто не больше раз.

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

_________________________________________________________________________________________________________________________________________________________________________________

Следствие. Суммарное количество упоминаний за игру не превосходит

______________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Оценим снизу количество упоминаний как

Это больше чем противоречие.

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

Значит, ход Максима на отдельный остров невозможен, и Оля выиграет.

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

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

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

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

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

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

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

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

Так, исходная задача может быть переформулировано в следующем виде:

Пусть — граф, такой, что и Тогда — гамильтонов.

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

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

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

Рассмотрим произвольную вершину и множество Поскольку то — тоже независимое множество, а, значит, — противоречие.

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

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

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

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

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

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