Определение остовного дерева

Question

Я хочу проверить правильность моего понимания связующего дерева (для неориентированных и связанных графов).

Из того, что я прочитал онлайн.Покрывающее дерево является подмножеством графа, оно содержит такое же количество вершин графа, однако имеет минимальное количество ребер.Для графа также может быть много разных связующих деревьев.

Я видел несколько иллюстраций остовных деревьев и их графа, поэтому я попытался привести свой собственный пример.

график дома

Итак, это изображение показывает график в форме дома.Если бы мне пришлось избавиться от одного ребра в этом домашнем графе, это было бы остовное дерево, поскольку существует альтернативный путь для перехода от одного узла к другому.

Я также мог бы потенциально избавиться от двух ребер, если быЯ проверяю, что между двумя узлами все еще существует путь.

Я прав в этом предположении?

Answer 1

Нет, вы не правы в этом предположении, потому что вам придется удалить 2 ребра, чтобы построить остовное дерево.Удаление одного ребра не сработает.
На вашем домашнем графике 5 вершин и 6 ребер.
Дерево с n вершинами имеет n-1 ребер, поэтому у дерева с 5 вершинами должно быть 4кромки.

Покрывающее дерево - не хитрый объект, оно действительно стоит под своим именем.spanning потому что он охватывает все вершины, и tree, потому что это дерево.

Если вы удалите одно ребро, в вашем графе все равно будет цикл, поэтому он не может быть деревом (которое по определению является связным ациклическим графом).

Это одна вещь, которую очень легко выяснить, когда вы хотите построить остовное дерево графа, это количество удаляемых ребер (или сохранение, что эквивалентно).Формула #vertices = #edges + 1 всегда выполняется в дереве.
Я советую вам взглянуть на все определения и характеристики дерева, всегда полезно иметь в виду более одного, особеннокогда дело доходит до деревьев.