Остовные деревья

Определение 2.3. Дерево называется остовным деревом графа , если – подграф графа и каждая вершина графа является вершиной в .

Теорема 2.5*. У каждого связного графа существует подграф, который является остовным деревом.

Для построения остовных деревьев существуют разные методы. Самыми распространенными являются два метода: метод поиска в ширину и метод поиска в глубину.

Согласно методу поиска остовного дерева в ширину произвольную вершину графа выбираем в качестве корня дерева . Для каждой вершины графа , смежной с вершиной , в дерево добавляется вершина и ребро . Это вершины первого уровня. Затем берем каждую вершину первого уровня и для каждой вершины графа , смежной с вершиной из тех, что еще не выбраны, добавляем в дерево вершину и ребро . Вершины, добавленные на этом этапе, − это вершины второго уровня. Продолжаем процесс, пока в графе не останется вершин, которые можно было бы добавить в дерево. По построению граф является деревом. Если расстояние от до вершины графа равно , то эта вершина будет добавлена в дерево на уровне . Следовательно, является остовным деревом.

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

При поиске в глубину усилия направлены на построение для дерева как можно более длинного пути.

Метод поиска в глубину начинается с задания вершины графа, которую будем считать корнем. Выбираем вершину , смежную с корнем, и формируем ребро дерева. Затем выбираем вершину , смежную с ранее выбранной вершиной , и формируем новое ребро. По ходу необходимо помечать использованные вершины с той целью, чтобы каждая вершина использовалась один раз. Если, находясь в вершине , мы выбираем другую вершину и обнаруживаем, что вершина уже была добавлена в дерево, то ребро между этими вершинами не может быть добавлено в дерево.