На рисунке жирными точками обозначены города некоторой страны. Между некоторыми парами городов установлены прямые авиалинии, показанные на рисунке в виде отрезков. Как можно видеть, из любого города есть возможность долететь в любой другой (иногда с пересадками). Руководство страны для экономии средств решило убрать часть авиалиний. При этом необходимо, чтобы из любого города по-прежнему можно было долететь в любой другой. Какое наибольшее число авиалиний можно убрать?

Решение:

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

На рисунке изображён граф, где вершины — это города, а рёбра — авиалинии. Посчитаем количество вершин (городов) на рисунке: A, Б, В, Г, Д, Е, Ж, К. Всего 8 вершин.

Минимальное количество авиалиний, необходимое для обеспечения связанности всех 8 городов, составляет N-1 = 8-1 = 7 авиалиний.

На рисунке видно, что изначальное количество авиалиний (рёбер) равно 9 (А-Б, А-Ж, А-Е, А-К, Б-В, В-Г, Г-Д, Д-Е, Ж-Е).

Чтобы определить, какое наибольшее число авиалиний можно убрать, нужно из общего числа авиалиний вычесть минимально необходимое количество:

\( 9 - 7 = 2 \) авиалинии.

Таким образом, можно убрать 2 авиалинии, и все города останутся связанными.

Ответ: 2