Задача 78596

Темы:    [ Примеры и контрпримеры. Конструкции ] [ Классическая комбинаторика (прочее) ] [ Теория графов (прочее) ]

Сложность: 4 Классы: 8,9

Условие

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

Решение

Зафиксируем какую-нибудь линию. На ней есть неперсадочная станция. С нее, сделав одну пересадку, можно попасть не более, чем на 3 линии, а с каждой из них, сделав еще одну пересадку, – ещё не более, чем на две линии. Следовательно, всего линий не более чем  1 + 3 + 2·3 = 10.  На рисунке показана схема пересадок для десяти линий, удовлетворяющая условию (для удобства беспересадочные станции не отмечены; "пересечения", не отмеченные кружочками, станциями не являются).

Ответ

10 линий.

Замечания

В условии не требуется, чтобы линии были прямымм. Поэтому, вообще говоря, достаточно привести список из 15 пересадочных станций и 10 линий. Вот пример такого списка: станции A, B, ..., O; линии {A, B, C},  {A, D, E},  {B, F, G},  {C, H, I},  {D, J, K},  {E, L, M},  {F, L, N},  {G, J, O},  {H, K, N},  {I, M, O}. Также можно привести граф с 10 вершинами степени 3, вершины которого соответствуют линиям, а рёбра – пересадочным станциям. Но при отсутствии явной симметрии проверка соответствия примера условиям становится трудоемкой.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	29
Год	1966
вариант
	1
Класс	8
Тур	2
задача
Номер	4