Графы и турниры → .14 Связность и связные подграфы (клики)

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

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

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

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

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

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

База индукции: Для утверждение очевидно — вершине присваивается номер

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

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

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

Таким образом, нумерация корректна для вершин.

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

Рассмотрим полный ориентированный граф. В таком графе для любой пары вершин и существует ровно одно направленное ребро: либо либо

Если граф уже сильно связен, тогда утверждение тривиально выполняется.

Пусть граф не является сильно связным. Разобьём его на компоненты сильной связности (КСС) где Компоненты сильной связности образуют линейный порядок: для любых и либо все рёбра между ними направлены из в либо из в

Пусть — порядок КСС. Рассмотрим компоненты и В исходном графе все рёбра направлены от к Изменим направление одного ребра где Теперь появится путь из в что объединяет компоненты в одну КСС.

Для остальных компонент

— Из можно достичь их через исходные рёбра.

— Из них можно достичь через изменённое ребро.

Таким образом, после изменения направления одного ребра граф становится сильно связным.

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

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

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

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

Первый вопрос задается про две крайние карты, а второй — про -ю и -ю. Далее задаем вопросы о таких парах карт: -я и -я; -я и -я; -я и -я, -я и -я и т. д. При этом за вопроса удается определить положение трех карт.

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

Сначала покажем, что последовательностей не хватит.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример на последовательностей опишем пример в терминах графа.

Разделим чисел на две равные группы: например, и .

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

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

Теперь поясним, почему после "склейки"полученные последовательностей будут удовлетворять условию. Какие бы числа , мы ни взяли, либо два из них будут среди чисел от до , либо среди чисел от до . Тогда два числа из одно группы соединены ребром, то есть являются соседями в одной из последовательностей. Этого мы и добивались.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

Предположим, что из города A нельзя попасть в город B. Пусть C – какой-то из оставшихся 18 городов. Тогда по крайней мере одна их двух авиалиний A–C, B–C отсутствует. Итого из возможных авиалиний отсутствуют не менее 19 (считая линию A–B), то есть линий не больше 171. Противоречие.

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

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

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

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

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

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

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