Самостоятельная работа по теме «Дерево». Вариант 1.

Задание 1.

На рисунке изображён граф. Ответь на вопросы.

1. Является ли граф, изображённый на рисунке, деревом?

   Да, граф является деревом, так как он связный и не содержит циклов.

2. Сколько рёбер у данного графа?

   По рисунку можно определить, что у графа 7 рёбер.

3. Сколько вершин у графа, изображённого на рисунке?

   По рисунку можно определить, что у графа 8 вершин.

4. Сколько концевых вершин у графа, изображённого на рисунке?

   По рисунку можно определить, что у графа 4 концевые вершины (вершины степени 1).

Задание 3.

В саду у Хагрида, который находится в школе волшебства Хогвартс, есть 154 грядки с тыквами. Каждые две грядки соединяет ровно одна дорожка. Определите количество дорожек в этом саду.

Это задача на комбинаторику. Нужно найти количество способов выбрать 2 грядки из 154, чтобы их соединить дорожкой. Используем формулу для сочетаний:

$$C_n^k = \frac{n!}{k!(n-k)!}$$

В нашем случае ( n = 154 ) (количество грядок), ( k = 2 ) (выбираем две грядки).

$$C_{154}^2 = \frac{154!}{2!(154-2)!} = \frac{154!}{2!152!} = \frac{154 \times 153}{2 \times 1} = 77 \times 153 = 11781$$

Ответ: 11781 дорожек.

Задание 4.

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

Чтобы сетка не развалилась, нужно оставить хотя бы одну леску между любыми двумя узлами сетки. Это значит, что можно перерезать все лески, кроме тех, которые образуют остов (связный граф без циклов). Количество лесок, которые нужно оставить, чтобы сетка не развалилась, равно количеству узлов минус 1.

Количество узлов в прямоугольной сети 17x58 равно ( 17 \times 58 = 986 ).

Значит, количество лесок, которые нужно оставить: ( 986 - 1 = 985 ).

Общее количество лесок в сети равно количеству горизонтальных и вертикальных лесок. Горизонтальных лесок 17 рядов по 57 лесок в каждом ряду (так как 58 клеток, между ними 57 лесок), итого ( 17 \times 57 = 969 ) горизонтальных лесок. Вертикальных лесок 58 столбцов по 16 лесок в каждом столбце (так как 17 клеток, между ними 16 лесок), итого ( 58 \times 16 = 928 ) вертикальных лесок.

Всего лесок: ( 969 + 928 = 1897 ).

Количество лесок, которые можно перерезать: ( 1897 - 985 = 912 ).

Ответ: 912 лесок.