Пж

На фотографии видно задание на определение количества конечных вершин в дереве графа. Число вершин в дереве равно 56.

В дереве графа есть свойства, которые нам помогут решить задачу. Дерево – это связный граф без циклов, и для дерева справедливо следующее: если в дереве есть n вершин, то в нем будет n-1 ребро. Каждая вершина, не являющаяся конечной, соединяет минимум две другие вершины.

Теперь давай подумаем. Если предположить, что у нас получится "цепочка", где каждая вершина (кроме двух концевых) соединена только с двумя соседями, то количество конечных вершин будет минимальным и составит 2.

В случае, если у дерева будет только одна вершина, которая не является конечной (или "корень" дерева), и все оставшиеся 55 вершин будут соединены прямо с ней, то количество конечных вершин будет максимальным, то есть 55.

Итак, в ответе на задачу:

• Наименьшее число конечных вершин = 2
• Наибольшее число конечных вершин = 55