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

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

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

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

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

Так как суммарно во всех -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). Добавление остальных ребер из уже не уменьшит количество компонент связности. Аналогично к графу можно добавить такие ребер из множества , что в итоге получаются все компонент связности графа . Но если к графу добавить и те, и другие ребра (в общей сложности ребер), то граф станет связным. Следовательно, и, значит, .

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

(a) 

Оценка. Занесём 2 в числитель и оценим каждое слагаемое следующим образом

Получим

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

Пример. Поставим во все вершины получим

(b) Будем доказывать от противного.

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

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

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

Пример. Найдём в графе максимальную клику, в его вершины поставим а в остальные

Оценка.

Рассмотрим расстановку, на которой достигается Если там есть вершина с 0, удалим её. По предположение

если максимальная антиклика не уменьшилась, и

если максимальная антиклика уменьшилась. Таким образом сделаем все числа ненулевыми.

Обозначим — сумму чисел в смежных с вершинах. Заметим, что если и — несмежные вершины и то можно заметить на Общая сумма не измениться, а увеличиться, противоречие. Следовательно, если и — несмежные вершины, то

Рассмотрим антиграф, проверим два случая:

1) Если он связен. Значит, для любых вершин и обозначим это число за Следовательно по предположению

Рассмотрим вершину максимальной антиклики.

Следовательно, число в плюс в вершинах, не смешных с меньше Просуммируем по врем вершинам максимальной антиклики. Мы посчитали каждое число неменее 1 раза, значит сумма всех меньше, чем . Противоречие, следовательно, такое невозможно.

2) Антиграф не связен.