ВсОШ 2021, 10 класс, задача 3

Ответ.

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

Первое решение.

Рассмотрим граф, в котором вершины - это города, ребра - авиалинии, причем ребра, соответствующие авиалиниям -ой компании, покрашены в -й цвет.

Пример.

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

Оценка.

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

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

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

Второе решение.

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

Сначала докажем, что для каждой пары компаний найдутся две вершины , любой путь между которыми содержит ребра обеих компаний и . Пусть при удалении компании вершины распадаются на два непустых множества и , между которыми нет ребер, а при удалении компании - на множества и . Если множества и оба непустые, то можно взять и . Иначе, множества и оба непустые, и можно взять и . Ясно, что и подходят и что между ними нет ребра.

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

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

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