ПОМОГИТЕ ПОЖАЛУЙСТА РЕШИТЬ

Задача 1: Сколько в дереве рёбер, если количество вершин равно 50?
В теории графов известно, что любое дерево с n вершинами имеет ровно n−1 ребер. Это следует из определения дерева как связного ациклического графа.

Если количество вершин n=50, то количество рёбер:
m=n−1=50−1=49.
Ответ: 49
Задача 2: Количество вершин дерева равно 31. Какой наибольший диаметр может иметь это дерево?
Диаметр дерева — это максимальное расстояние между двумя его вершинами. Чтобы максимизировать диаметр, нужно "растянуть" дерево так, чтобы оно имело форму цепочки (так называемое "вырожденное дерево"). В этом случае все вершины располагаются на одной прямой, и длина цепочки будет равна количеству рёбер, которые можно провести между вершинами.
При n=31 вершинах дерево содержит n−1=30 рёбер. Если все эти рёбра образуют одну длинную цепочку, то диаметр дерева будет равен количеству рёбер в этой цепочке, то есть 30.

Ответ: 30
Задача 3: Рыболовная сеть имеет форму прямоугольника 48×28 клеток. Какое наибольшее число клеток можно перерезать так, чтобы сетка не распалась на куски?
Рассмотрим структуру сети. Она представляет собой решётку размером 48×28 клеток. Каждая клетка имеет границы, которые соединяют её с соседними клетками. Чтобы сетка не распалась на части, необходимо сохранить хотя бы один путь между любой парой клеток.
Шаг 1: Определение общего числа клеток
Общее количество клеток в сети:
48×28=1344.
Шаг 2: Минимальное количество связей для сохранения связности
Сетка является планарным графом, где каждая клетка соединена с соседями. Для того чтобы граф оставался связным, достаточно оставить структуру, которая представляет собой дерево. Дерево с n вершинами имеет n−1 рёбер. Здесь вершины соответствуют клеткам, а рёбра — границам между ними.
Таким образом, минимальное количество рёбер, необходимых для сохранения связности, равно:
1344−1=1343.
Шаг 3: Общее количество рёбер в начальной сетке
Каждая клетка имеет до 4 границ (сверху, снизу, слева, справа), но каждое ребро делится между двумя соседними клетками. Поэтому общее количество рёбер в сетке можно вычислить следующим образом:
Горизонтальные рёбра: 48×(28+1)=48×29=1392,
Вертикальные рёбра: (48+1)×28=49×28=1372.
Итого общее количество рёбер:
1392+1372=2764.
Шаг 4: Максимальное количество рёбер, которые можно удалить
Чтобы сохранить связность, необходимо оставить 1343 рёбер. Значит, можно удалить:
2764−1343=1421.
Ответ: 1421