Вопрос проверяет базовое понимание свойств графов и того, что отличает дерево от других графов.
У любого дерева с M вершинами всегда ровно M - 1 рёбер. Это связано с тем, что дерево — связный граф без циклов. Если рёбер меньше, граф будет несвязным, если больше — появится цикл. Это свойство справедливо для любых деревьев, независимо от их формы.
Свойство количества рёбер — одно из фундаментальных для деревьев.
Определение: Дерево — связный неориентированный граф без циклов.
Можно рассуждать пошагово:
Одна вершина — 0 рёбер
Чтобы добавить новую вершину и сохранить связность, нужно добавить ровно одно ребро
Каждая новая вершина добавляет одно ребро
Если вершин стало M, рёбер будет M - 1.
Если добавить ещё одно ребро:
Появится альтернативный путь между вершинами
Значит, образуется цикл
Граф перестанет быть деревом
Если убрать одно ребро:
Граф станет несвязным
Некоторые вершины окажутся недостижимыми
Для дерева из 5 вершин:
Минимум рёбер для связности: 4
Любое добавочное ребро создаёт цикл
Формула M - 1 — прямое следствие связности и отсутствия циклов.
Это свойство часто используется при проверке, является ли граф деревом.
