Индукция в графах и теорема Турана

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

Введем граф, вершинами которого будут города, а ребрами — дороги.

Пример. Если то треугольников с общей вершиной, если , то треугольников с общей вершиной и висячее ребро из той же вершины.

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

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

Рассмотрим граф состояний диаграмм Юнга с переходами в виде удаления доминошек, так как клеток конечное число, то все пути конечны, а по доказанному выше он удовлетворяет Diamond-лемме, значит, конечное состояние — единственно.

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

Для применения Diamond-леммы необходимо показать, что для пары состояний полученных операциями над вершинами из состояния найдется общее состояние

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

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

Обозначим — вершины смежные и с и с — смежные только с — только с Вес в вершине — в —

Тогда после описанных выше операций получим веса:

• в
• в
• в вес изменится на
• в вес изменится на

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

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

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

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

Будем говорить, что вершина влияет на вершину если данные вершины являются соседями и идол сильнее идола при этом не имеет соседа с более сильным идолом, отличным от

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При хватит нашей оценки. Так как неравенство

равносильно неравенству что верно при

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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