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

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

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

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

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