Кратчайший остов графа

Понятие дерева

Одним из наиболее важных понятий теории графов является дерево. Его упрощенное определение можно дать так. Дерево — граф, имеющий начало, от которого дуги (ребра) расходятся, как ветви дерева [2]. Дерево, как и граф, может быть ориентированным и неориентированным.

Неориентированное дерево — это сильно связный граф, не имеющий циклов. (Понятие сильно связного графа дано в п. 2.3.2).

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

Определение числа остовных деревьев графа

В некоторых ситуациях возникает необходимость в построении полного списка остовных деревьев графа. Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным, так что непосредственное решение задачи оптимизации, не использующее перечисление всех остальных деревьев, оказывается невыполнимым.

Определим число всех остовных деревьев для неориентированного графа. Пусть матрица M={m_ij} для неориентированного графа определена следующим образом: диагональный элемент m_ii есть число ребер, имеющих вершину x_i в качестве одной из концевых вершин, а элемент m_ij — число параллельных ребер между вершинами x_i и x_j со знаком минус. Число всех остовных деревьев равно определителю подматрицы, получающейся вычеркиванием одной строки и одного столбца из матрицы М.

Для ориентированного графа без петель (петлей называется дуга, начальная и конечная вершины которой совпадают) матрицу определим следующим образом: m_ii — число дуг, которые имеют своей конечной вершиной, вершину x_i т. е. заходят в x_i; m_ij = -k, где k есть число параллельных дуг из x_i в x_j. Тогда число ориентированных остовов с корнем x_r равно определителю подматрицы, полученной вычеркиванием r-й строки и r-го столбца из матрицы М.