Вопрос 25 Выберите верное утверждение: Выберите один ответ: Число вершин на единицу меньше числа ребер Число ребер в дереве совпадает с числом вершин Число вершин в дереве в 2 раза больше числа ребер Число ребер в дереве на единицу меньше числа вершин Очистить мой выбор ← Назад Далее →

Ответ: Число рёбер в дереве на единицу меньше числа вершин

В теории графов, дерево - это связный граф без циклов. В дереве с n вершинами всегда n-1 ребро.

• Рассмотрим дерево с 1 вершиной. У него 0 ребер.
• Если добавим еще одну вершину, нам понадобится 1 ребро, чтобы связать её с первой.
• Если добавим третью вершину, понадобится ещё одно ребро, чтобы связать её с одной из первых двух.
• И так далее: каждая новая вершина требует одного нового ребра.

Таким образом, количество ребер всегда на единицу меньше количества вершин.

Ответ: Число рёбер в дереве на единицу меньше числа вершин