Выберите правильные утверждения. Каждая вершина дерева может быть связана только с нечётным количеством вершин

Краткий ответ: Правильные утверждения — это «Дерево – это связный граф без циклов» (оно уже отмечено на фото) и «В любом дереве количество вершин всегда на 1 больше, чем количество рёбер».

Разбор по шагам:

1. Определение дерева. По определению из дискретной математики и информатики, дерево — это именно связный граф, в котором нет циклов. Поэтому третье утверждение верно.
2. Связь числа вершин и рёбер. У любого дерева с \(n\) вершинами ровно \(n - 1\) ребро. Это легко понять: если взять одну вершину, рёбер будет 0 (\(1 = 0 + 1\)). Каждый раз, когда мы добавляем новую вершину, чтобы граф остался связным и не образовал цикл, мы проводим ровно одно новое ребро. Значит, каждая вершина добавляет одно ребро, и разница между ними всегда равна 1. Поэтому четвёртое утверждение верно.
3. Почему остальные неверны:
   • «Каждая вершина дерева может быть связана только с нечётным количеством вершин» — неверно. В цепочке из трёх вершин средняя соединена с двумя другими (чётное число).
   • «Только одна вершина в дереве может быть корнем» — неверно. В обычном дереве в качестве корня можно выбрать любую вершину, перестроив направление рёбер.
   • «Каждая вершина в дереве имеет только одного предка» — неверно. У корня дерева предков нет вообще, поэтому слово «каждая» делает утверждение ложным.

Проверка: Возьмём звезду из 5 вершин (один центр и 4 листа). Вершин — 5, рёбер — 4. Свойство \(V = E + 1\) выполняется (\(5 = 4 + 1\)), циклов нет — это действительно дерево.