Графы и турниры → .01 Индукция в графах и теорема Турана

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

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

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

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

Индукция по База при справедлива, искомое дерево — две вершины, соединённые ребром.

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

Индукция по База при и

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

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

Индукция по База при тривиальна.

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Сначала докажем, что для каждой пары компаний найдутся две вершины любой путь между которыми содержит ребра обеих компаний и Пусть при удалении компании вершины распадаются на два непустых множества и между которыми нет ребер, а при удалении компании — на множества и Если множества и оба непустые, то можно взять и Иначе, множества и оба непустые, и можно взять и Ясно, что и подходят и что между ними нет ребра.

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

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

Пронумеруем олигархов и их города числами от до соответственно.

Пример.

Пусть дорога между городами и принадлежит олигарху под номером тогда и только тогда, когда Тогда количество дорог равно

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

Оценка 1.

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Оценка 2.

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

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

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

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

ребер.

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

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

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

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

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

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

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

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

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

Первое решение. Сведём задачу на язык графов. Вершины — команды. Ребро проводим между вершинами, если соответствующие команды сыграли между собой. Рассмотрим произвольные две вершины которые не соединены ребром (если таких нет, то рёбер в графе Рассмотрим произвольную вершину из оставшихся. Если в графе отстутствуют рёбра и то тройка не удовлетворяет условиям задачи. То есть хотя бы одно ребро из проведено. Итого, от каждой из оставшихся вершин к паре ведёт хотя бы одно ребро. То есть всего хотя бы рёбер. Теперь рассмотрим граф на оставшихся вершинах. В нём также выделим несмежные вершины (если такой не нашлось, то рёбер хотя бы ). Аналогичными рассуждениями получаем, что от каждой из оставшихся вершин (не ) к паре ведёт хотя бы рёбер. Будем делать такие «спуски», пока не закончатся вершины или пока не встретим полный подграф. Разберём оба случая.

1.

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

Теперь учтём остальные посчитанные рёбра. Их хотя бы

по формуле арифметической прогрессии. Итого, хотя бы

рёбер в графе. Так как — парабола с ветвями вверх и где — абсцисса вершины параболы, то при рёбер в графе хотя бы

2.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

База индукции: Оценка очевидна.

Шаг индукции: Пусть доказано для , докажем для .

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

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

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

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

База. Для полного графа с тремя вершинами утверждение очевидно.

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

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

2) Не все рёбра цикла окрашены в один цвет. Пусть в цикле есть две одноцветные части: (красная) и (синяя). Посмотрим на цвет ребра Если это ребро красное, то цикл — искомый, если же оно синее, то искомым будет цикл

Индукция по числу городов.

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

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

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