Начинается пора вступительных экзаменов, а значит и решения интересных задач. Пару лет назад Computer Science Center предлагал поступающим разобраться с задачей про кактус-граф, и сегодня речь пойдёт именно о ней. Попробуйте подумать над задачей сами, а затем свериться с решением.
К слову, набор в CS центр уже идёт. В этом году поступить на очное обучение можно не только в Санкт-Петербурге, но и в Новосибирске. Приходите — на занятиях ещё больше интересного.
Computer Science Center – это совместная инициатива Computer Science клуба при ПОМИ, компании JetBrains и Школы анализа данных Яндекса. Центр предлагает двух- или трёхлетние курсы для студентов, аспирантов и выпускников технических вузов, а также молодых специалистов, желающих развиваться в области анализа данных, разработки ПО или теоретической информатики. Занятия проходят по вечерам в Санкт-Петербурге или в Новосибирске.
В 2017 году набор на очное обучение состоит из четырёх этапов:
- подача заявки до 16 апреля включительно,
- онлайн-тестирование,
- экзамен,
- очное собеседование.
Задача
Кактусом называется простой связный граф, в котором любые два цикла имеют не больше одной общей вершины. Доказать, что максимальное число ребер в кактусе с n вершинами равно 
.
*
— округление вниз.
Решение
Сначала нужно понять, как этот граф устроен. Поможет нам в этом пример графа, изображённого на рисунке. Рядом изображён настоящий кактус. Это позволяет понять, чем обусловлено такое название.
Любой цикл, в котором больше трёх вершин, можно «затянуть», заменив на цикл длины три и простой путь. При этом общее число вершин и рёбер в графе не изменится, а сам граф останется кактусом. Ниже пример «затягивания» графа.
Рассмотрим теперь кактус, в котором найдутся рёбра, не лежащие ни на одном цикле. Любые два таких ребра можно стянуть в вершину. В результате из графа исчезнут два ребра и две вершины. После чего добавить в граф цикл длины три, одна из вершин которого будет уже существующей вершиной графа. Количество вершин станет прежним, а число ребер увеличится на единицу.
На рисунке выше изображён пример описанной выше манипуляции. На левом рисунке изображён кактус, в котором выделены ребра вне циклов. На центральном рисунке тот же кактус, но уже со стянутыми ребрами. В нём не только исчезли два ребра, но и стало на две вершины меньше. И, наконец, на правом рисунке изображен кактус, к которому мы прибавили ещё один треугольник, — появились три новых ребра и две вершины. В результате количество вершин до и после операции не изменилось, а количество рёбер увеличилось.
Таким образом, максимальное количество рёбер в кактусе достигается тогда, когда он состоит целиком из треугольников и, может быть, одного ребра, не лежащего ни на одном цикле. Такой кактус можно построить последовательным добавлением крайних блоков-треугольников, начав либо с 
, либо с 
, в зависимости от чётности 
. (
— полный граф на 
вершинах.) При добавлении каждого блока добавляется две вершины и три ребра, откуда немедленно следует требуемое в задаче утверждение.
Автор: СПБАУ
