Задание 4. Какое максимальное количество лесок можно перерезать в рыболовной сети, имеющей форму прямоугольника и размеры 17×58 клеток, так чтобы сетка не развалилась?

Решение:

Рыболовная сеть, состоящая из \( m \times n \) клеток, представляет собой прямоугольный граф. Чтобы сетка не развалилась, мы можем перерезать все рёбра, кроме тех, которые образуют "остов" сетки. "Остов" — это минимальный набор рёбер, который сохраняет связность всех вершин.

Количество вершин в сети \( (m+1) \times (n+1) \) (учитывая пересечения лесок).

В данном случае, \( m = 17 \) и \( n = 58 \).

Количество вершин = \( (17+1) \times (58+1) = 18 \times 59 \).

\( 18 \times 59 = 18 \times (60 - 1) = 1080 - 18 = 1062 \) вершины.

Минимальное количество рёбер (лесок), необходимое для того, чтобы сетка не развалилась (т.е. чтобы граф остался связным), равно \( V - 1 \), где \( V \) — количество вершин. Это количество образует остов графа.

Количество лесок в остове = \( 1062 - 1 = 1061 \).

Общее количество лесок в сети равно сумме горизонтальных и вертикальных лесок.

Горизонтальных лесок: \( m \times (n+1) = 17 \times (58+1) = 17 \times 59 = 1003 \).

Вертикальных лесок: \( n \times (m+1) = 58 \times (17+1) = 58 \times 18 = 1044 \).

Всего лесок = \( 1003 + 1044 = 2047 \).

Максимальное количество лесок, которое можно перерезать = Общее количество лесок - Количество лесок в остове.

Максимальное количество перерезаемых лесок = \( 2047 - 1061 = 986 \).

Ответ: 986.