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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если же её степень хотя бы то и степень всех остальных хотя бы Значит, если её выкинуть, то степень соседних с ней вершин будет хотя бы а у несоседних — хотя бы Что и требовалось.

Первое решение. Докажем сначала следующую лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер.

Доказательство. Рассмотрим вершину наибольшей степени (пусть Пусть вершина cоединена с Ясно, что никакие и не могут быть соединены, потому что иначе в графе будет треугольник Степень оставшихся вершин не превосходит Таким образом, всего в графе не более Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем по индукции.

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

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

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

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

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

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

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

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

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

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

Пронумеруем людей числами от до . Заметим, что при могут созвониться сначала и , потом и , потом и , и в конце и . Тогда все будут знать все новости. Пусть мы умеем организовывать созвон для человека. Научимся организовывать для . Сначала пусть созвонятся и . Теперь знает две новости. Далее организуем созвон для человека. А потом могут созвониться опять и . Легко видеть, что все будут знать все новости, а количество звонков стало равно .

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

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

Лемма: в ориентированном графе без циклов есть вершина, из которой не выходит ни одного ребра(только входят).

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство.

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

_________________________________________________________________________________________________________________________________________________________________________________

Теперь индукцией по количеству вершин докажем исходную задачу.

База при одной вершине очевидна.

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

Докажем индукцией по . Для такой граф существует: две вершины, соединённые ребром.

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

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

База для одного города: сделаем лжеца мэром города, тогда он ответит удовлетворительно, потому что у него вообще нет соседей.

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

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

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

Таким образом, при имеем не более диагоналей.

Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим пауков (всего 1000 городов). Если то в одном из пауков выбраны все 4 города, что противоречит условию.

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

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

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

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

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

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

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

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

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

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

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

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

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

База для проверяется непосредственно. Пусть оценка верна для всех Докажем ее для

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

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

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

(неравенство при следует при непосредственной проверке найденных значений, и при из предположения индукции), количество ребер в не превосходит

При для доказательства достаточно показать, что

что после раскрытия скобок и приведения подобных дает т.е. верно при

При для доказательства достаточно показать, что

что после раскрытия скобок и приведения подобных дает т.е. верно при

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

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

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

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