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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример графа показан на рисунке. Множество содержит вершину, множество — вершину.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

следовательно, .

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

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

Введём граф следующим образом: камни будут вершинами, вершины соединены ребром, если соответствующие камни сравнивались. Ясно, что для выявления самого тяжёлого камня граф должен быть связным. То есть количество рёбер должно быть не меньше

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