Одна задача про кактус-граф

Начинается пора вступительных экзаменов, а значит и решения интересных задач. Пару лет назад Computer Science Center ^[1] предлагал поступающим разобраться с задачей про кактус-граф, и сегодня речь пойдёт именно о ней. Попробуйте подумать над задачей сами, а затем свериться с решением.

К слову, набор в CS центр ^[2] уже идёт. В этом году поступить на очное обучение можно не только в Санкт-Петербурге, но и в Новосибирске. Приходите — на занятиях ещё больше интересного.

Чуть больше про CS центр и набор

Computer Science Center – это совместная инициатива Computer Science клуба при ПОМИ ^[3], компании JetBrains ^[4] и Школы анализа данных Яндекса ^[5]. Центр предлагает двух- или трёхлетние курсы для студентов, аспирантов и выпускников технических вузов, а также молодых специалистов, желающих развиваться в области анализа данных, разработки ПО или теоретической информатики. Занятия проходят по вечерам в Санкт-Петербурге или в Новосибирске.

В 2017 году набор на очное обучение состоит из четырёх этапов:

подача заявки ^[6] до 16 апреля включительно,
онлайн-тестирование,
экзамен,
очное собеседование.

Задача

Кактусом называется простой связный граф, в котором любые два цикла имеют не больше одной общей вершины. Доказать, что максимальное число ребер в кактусе с n вершинами равно $operatorname{floor}frac{3}{2}(n-1)$ .

* $operatorname{floor}$ — округление вниз.

Решение

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

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

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

Одна задача про кактус-граф - 5

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

Таким образом, максимальное количество рёбер в кактусе достигается тогда, когда он состоит целиком из треугольников и, может быть, одного ребра, не лежащего ни на одном цикле. Такой кактус можно построить последовательным добавлением крайних блоков-треугольников, начав либо с $K_3$ , либо с $K_2$ , в зависимости от чётности $n$ . ( $K_n$ — полный граф на $n$ вершинах.) При добавлении каждого блока добавляется две вершины и три ребра, откуда немедленно следует требуемое в задаче утверждение.