Страница 68 номер 96, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Волейбольная сетка имеет вид прямоугольника \(50 \times 600\) клеток. Какое наибольшее количество верёвочек можно перерезать так, чтобы сетка не распалась на куски?
Узлы — вершины, верёвочки — рёбра; сетка не распадётся ровно тогда, когда граф связен.
Узлы стоят в 51 ряду по 601 узлу: их \(51 \cdot 601 = 30\,651\).
Горизонтальных верёвочек \(51 \cdot 600 = 30\,600\), вертикальных \(601 \cdot 50 = 30\,050\), всего \(30\,600 + 30\,050 = 60\,650\).
Связный граф с \(30\,651\) вершиной содержит не меньше \(30\,651 - 1 = 30\,650\) рёбер — столько их в дереве на тех же вершинах. Значит, перерезать можно не больше \(60\,650 - 30\,650 = 30\,000\) верёвочек.
Ровно столько и перерезается: оставим все вертикальные линии (\(601 \cdot 50 = 30\,050\) верёвочек) и верхнюю горизонтальную (600 верёвочек) — каждый узел связан по своей вертикали с верхним рядом, а верхний ряд связан весь. Оставлено \(600 + 30\,050 = 30\,650\) верёвочек — ровно столько, сколько нужно дереву.
Ответ: можно перерезать 30 000 верёвочек.
Волейбольная сетка имеет вид прямоугольника \(50 \times 600\) клеток. Какое наибольшее количество верёвочек можно перерезать так, чтобы сетка не распалась на куски?
Сетка — это граф: вершины — узлы, в которых связаны верёвочки, рёбра — сами верёвочки между соседними узлами. Сетка не распадётся на куски ровно тогда, когда этот граф остаётся связным.
В сетке \(50 \times 600\) клеток узлы стоят в 51 горизонтальном ряду по 601 узлу в каждом, поэтому узлов \(51 \cdot 601 = 30\,651\).
Верёвочки посчитаем по направлениям: в каждом из 51 ряда 600 горизонтальных верёвочек, то есть \(51 \cdot 600 = 30\,600\); в каждом из 601 столбца 50 вертикальных верёвочек, то есть \(601 \cdot 50 = 30\,050\). Всего \(30\,600 + 30\,050 = 60\,650\) верёвочек.
Связный граф с \(30\,651\) вершиной содержит не меньше \(30\,651 - 1 = 30\,650\) рёбер: выбрасывая рёбра, лежащие на циклах, из него получают дерево на тех же вершинах, а в дереве рёбер ровно \(30\,650\). Значит, перерезать можно не больше \(60\,650 - 30\,650 = 30\,000\) верёвочек.
Ровно столько перерезать удаётся. Оставим целиком все вертикальные линии (\(601 \cdot 50 = 30\,050\) верёвочек) и верхнюю горизонтальную линию (600 верёвочек): каждый узел связан по своей вертикали с верхним рядом, а верхний ряд связан весь, поэтому сетка не распадается. Оставлено \(600 + 30\,050 = 30\,650\) верёвочек — ровно столько, сколько нужно дереву.
Ответ: можно перерезать 30 000 верёвочек.
