Одним из наиболее важных понятий теории графов является дерево. Его упрощенное определение можно дать так. Дерево – граф, имеющий начало, от которого дуги (ребра) расходятся, как ветви дерева [2]. Дерево, как и граф, может быть ориентированным и неориентированным.
Неориентированное дерево – это сильно связный граф, не имеющий циклов. (Понятие сильно связного графа дано в п.2.3.2).
Ориентированное дерево представляет собой ориентированный граф без циклов, в котором в каждую вершину должна быть направлена только одна дуга, кроме корневой вершины, куда не заходит ни одна дуга. Остовное дерево графа, или остов графа, имеет то же самое множество вершин, что и исходный граф, но множество дуг (ребер) остовного дерева является подмножеством множества дуг (ребер) исходного графа.
Определение числа остовных деревьев графа
В некоторых ситуациях возникает необходимость в построении полного списка остовных деревьев графа. Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным, так что непосредственное решение задачи оптимизации, не использующее перечисление всех остальных деревьев, оказывается невыполнимым.
|
|
Определим число всех остовных деревьев для неориентированного графа. Пусть матрица M={mij} для неориентированного графа определена следующим образом: диагональный элемент mii есть число ребер, имеющих вершину xi в качестве одной из концевых вершин, а элемент mij – число параллельных ребер между вершинами xi и xj со знаком минус. Число всех остовных деревьев равно определителю подматрицы, получающейся вычеркиванием одной строки и одного столбца из матрицы М.
Для ориентированного графа без петель (петлей называется дуга, начальная и конечная вершины которой совпадают) матрицу определим следующим образом: mii – число дуг, которые имеют своей конечной вершиной, вершину xi т.е. заходят в xi; mij = -k, где k есть число параллельных дуг из xi в xj. Тогда число ориентированных остовов с корнем xr равно определителю подматрицы, полученной вычеркиванием r-й строки и r-го столбца из матрицы М.
Алгоритм построения всех остовных деревьев графа
На основе полного перебора последовательностей