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

Решение:

Данная задача описывает задачу о нахождении минимального остовного дерева в графе. В графе города — это вершины, а авиалинии — это рёбра. Условие, что из любого города можно долететь в любой другой, означает, что исходный граф является связным.

На рисунке изображен граф с 6 вершинами (городами): А, Б, В, Г, Д, Е, Ж. Количество вершин \( n = 6 \).

Исходное количество авиалиний (рёбер) равно 7:

• А-Б
• А-Г
• Б-В
• Б-Е
• В-Д
• Г-Ж
• Д-Ж

Чтобы из любого города можно было долететь в любой другой (чтобы граф оставался связным), необходимо, чтобы в графе отсутствовали циклы. Минимальное количество рёбер, необходимое для связности \( n \) вершин, равно \( n-1 \).

В данном случае, для 6 вершин минимальное количество рёбер для поддержания связности равно \( 6 - 1 = 5 \).

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

\[ \text{Максимальное число убираемых авиалиний} = \text{Исходное число авиалиний} - (n-1) \]

\[ 7 - (6 - 1) = 7 - 5 = 2 \]

Таким образом, можно убрать 2 авиалинии.

Ответ: 2