Сколько общих пересадочных станций необходимо, чтобы соединить 100 линий метро в городе, так что каждые две линии

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

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

Итак, для 100 линий метро, которые должны пересекаться только в одной общей станции, и не больше трех линий в одной станции, нам понадобится 99 + 98 + 97 + ... + 2 + 1 = 4950 общих пересадочных станций.

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

Совет: Для лучшего понимания задачи и решения по шагам, можно нарисовать диаграмму графа метро и поэтапно добавлять новые линии и пересечения.

Задание для закрепления: Имеется 5 линий метро. Сколько общих пересадочных станций потребуется в этом случае?