2.3. Пример

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

На рис. 7.8 изображено соответствующее дерево решений (оно порождено в процессе работы алгоритма, приведенного в разд. 2.2.2). Если взять ребра, указанные в кружочках какой-либо цепи, выходящей из верхнего узла этого дерева и оканчивающейся в самом нижнем узле, то из них можно построить некоторый остов данного графа. Эти остовы перенумерованы числами от 1 до 21 и приведены на рис. 7.9.

Легко проверить, что у графа, изображенного на рис. 7.7, действительно 21 остов. Это можно установить с помощью теоремы 1 из разд. 2. Матрица инциденций В данного графа имеет следующий вид (считаем, что каждое ребро ориентировано от его

(кликните для просмотра скана)

концевой вершины с меньшим индексом к вершине с большим индексом):

Удаляя, например, строку получим матрицу Произведение матриц выглядит так:

Определитель равен 21. Следовательно, по теореме 1 число остовных деревьев данного графа равно 21.