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

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

Оценка: Докажем по индукции, что число ничьих не превосходит

База индукции: При это очевидно. При все три игры не могли закончиться вничью, иначе у всех команд было бы одинаковое число очков.

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

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

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

Подставим и получим ответ.

Оценка: До пересчёта у команды «Бельчата» было хотя бы на 2 очка больше, чем у команды «Метеор», а после пересчёта - хотя бы на 2 очка меньше. Кроме того, чтобы после пересчёта оказаться первой, команда «Метеор» должна иметь хотя бы одну победу. Действительно, в каждом матче разыгрывается 2 очка, поэтому если бы у команды «Метеор» не было побед, то она набрала бы не более половины возможного числа очков и не могла бы стать первой. Аналогично, для того чтобы команда «Бельчата» стала последней, у неё должно быть поражений больше, чем побед. Таким образом, после пересчёта команда «Метеор» потеряет как минимум 1 очко. Следовательно, команда «Бельчата» должна потерять не менее 5 очков, т. е. у неё должно быть не меньше пяти побед и не меньше шести поражений. Поэтому она сыграла как минимум 11 матчей, значит, в турнире участвовало не менее 12 команд.

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

Команда													Сумма 1	Сумма 2
		B	B	B	B	B	0	0	0	0	0	0	15	10
	0		1	1	1	1				0	0	1	14	11
	0	1		1	1	1	0				0	1	14	11
	0	1	1		1	1	0	0				1	14	11
	0	1	1	1		1		0	0			1	14	11
	0	1	1	1	1				0	0		1	14	11
		0			0	0		1	1	1	1	1	14	11
		0	0			0	1		1	1	1	1	14	11
		0	0	0			1	1		1	1	1	14	11
			0	0	0		1	1	1		1	1	14	11
				0	0	0	1	1	1	1		1	14	11
		1	1	1	1	1	1	1	1	1	1		13	12

Рассмотрим граф, в котором вершины — ребра, города — дороги. Выделим в нем максимальную антиклику . Если она размера 7 или более, то нам повезло. Иначе отделим эти вершины, а в оставшемся графе снова выберем максимальную антиклику . Наберем таким образом 8 непересекающихся антиклик. Теперь в одну часть отнесем все вершины этих восьми антиклик (их будет не более ), а во вторую часть — все оставшиеся вершины. Заметим, что любая оставшаяся вершина имеет хотя бы по одной смежной в каждой антиклике, иначе на очередном шаге эту вершину можно было бы присоединить к этой антиклике. Следовательно, из каждой вершины второй части, которых хотя бы 52, выходит не менее 8 ребер в первую часть. Итого, не менее 416 ребер между частями. Противоречие.

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

Выделим в нашем графе остовное дерево. В нём рёбер.

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

Для дерева из двух вершин это очевидно.

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

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

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

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

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

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

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

Выделим в нашем графе из вершин остовное дерево.

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

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

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

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

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

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

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

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

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

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

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

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

Докажем индукцией по числу вершин.

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

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

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

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

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

Ясно, что степень каждой вершины хотя бы иначе мы можем рассмотреть четв̈eрку, состоящую из вершины и три вершин, с которыми она не смежна. Очевидно, она не удовлетворит условию.

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

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

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

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

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

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

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

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

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

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

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

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

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

Докажем, что не существует графа, состоящего из треугольников, степень каждой неизолированной вершины в котором Это завершит решение задачи по индукции. Отметим, что в любом таком графе есть хотя бы неизолированные вершины. Посчитаем двумя способами количество ребер в нем. С одной стороны, оно равно так как ребра можно разбить по цветам; цветов ровно а ребер фиксированного цвета – ровно 3. С другой, так как степень каждой неизолированной вершины то число ребер Значит, натуральное число должно удовлетворять неравенству

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