2.4. Понятие дерева. Выберите правильные утверждения.

Ответ: верны четвёртое и пятое утверждения:

• «Дерево – это связный граф без циклов»;
• «В любом дереве количество вершин всегда на 1 больше, чем количество рёбер».

Разбор по пунктам

1. «Каждая вершина связана только с нечётным количеством вершин» — неверно. Степень вершины (число соседей) может быть любой. Пример: цепочка \(a - b - c\). У средней вершины \(b\) ровно два соседа — степень 2, чётная. Значит, «только нечётное» — неправда.

2. «Только одна вершина может быть корнем» — неверно. В обычном (неориентированном) дереве нет «главной» вершины: корнем можно назначить любую вершину, от этого граф не перестанет быть деревом — изменится лишь способ рисовать его иерархией.

3. «Каждая вершина имеет только одного предка» — неверно. Если рассматривать дерево с корнем, то у самого корня предка нет вообще, поэтому слово «каждая» делает утверждение ложным. Верной была бы формулировка: «у каждой вершины, кроме корня, ровно один непосредственный родитель».

4. Верно — это и есть определение дерева. Из связности и отсутствия циклов следует, что между любыми двумя вершинами есть ровно один простой путь.

5. Верно: для дерева с \(n\) вершинами и \(m\) рёбрами всегда \(m = n - 1\), то есть вершин на одну больше.

Почему \(m = n - 1\)

Дерево можно «вырастить» из одной вершины: каждый раз добавляем новую вершину и присоединяем её ровно одним ребром к уже построенной части. Тогда:

• 1 вершина — 0 рёбер;
• 2 вершины — 1 ребро;
• 3 вершины (цепочка) — 2 ребра;
• «звезда» из 5 вершин — 4 ребра.

Если добавить лишнее ребро — появится цикл, а если не добавить ребро — новая вершина окажется не связана с остальными.

Проверка: \(n = m + 1\) выполняется на всех маленьких примерах, а вывод «каждая новая вершина требует ровно одного ребра» объясняет, почему это верно для любого дерева.