Упр.96 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Волейбольная сетка имеет вид прямоугольника $$50 \times 600$$ клеток. Какое наибольшее количество верёвочек можно перерезать так, чтобы сетка не распалась на куски?

Рассмотрим сетку как граф: клеткам соответствуют вершины, а верёвочкам — рёбра. Чтобы сетка не распалась на куски, граф должен остаться связным.

В прямоугольнике $$50 \times 600$$ клеток число вершин равно

$$(50+1)(600+1)=51\cdot 601=30651.$$

Число рёбер:

вертикальных верёвочек $$51\cdot 600$$, горизонтальных верёвочек $$601\cdot 50$$.

Итого

$$51\cdot 600+601\cdot 50=30600+30050=60650.$$

Для связного графа с $$30651$$ вершиной достаточно оставить $$30651-1=30650$$ рёбер.

Значит, можно перерезать

$$60650-30650=30000$$

верёвочек.

Ответ

$$30000$$