21.2.2 Вершинная база

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

Для нахождения вершинной базы необходимо сформировать матрицу

A” = E v A v…v A^n-1,

где Е – единичная матрица размера nn, А,…,A^n–1 – степени матрицы смежности графа, от 1 доn–1.

Затем надо найти в матрице A” множество строк, единицы в которых покрывают все столбцы, – множество вершин, соответствующее этому множеству строк, и есть вершинная база.

В качестве примера найдем вершинную базу графа, показанного на рис. 21.1

Составим матрицу смежности графа

A= .

Определим необходимые степени матрицы смежности

A²= * = ,

A³= *=.

Определим матрицу A”

A”= E v A v A² v A³ = .

Для определения вершинной базы необходимо найти вершины, строки которых покрывают все столбцы матрицы A”.

Анализируя матрицу A”, замечаем, что

• для покрытия столбца 1 нужна строка 1 (v₁),

• для покрытия столбца 2 нужна строка 1 (v₁), или строка 2 (v₂), или строка 3 (v₃), что можно записать так (v₁v₂v₃),

• для покрытия столбца 3 нужна строка 3 (v₃),

• для покрытия столбца 4 нужна или строка 1 (v₁), или строка 2 (v₂), или строка 3 (v₃), или строка 4 (v₄), что можно записать так

(v₁v₂v₃v₄).

Поскольку надо покрыть единицами и первый столбец, и второй столбец, и третий столбец, и четвертый столбец, то, заменив союз И символом конъюнкции, запишем

v₁(v₁v₂v₃)v₃(v₁v₂v₃v₄).

Раскрыв скобки и проведя преобразования, получаем

v₁v₃.

Множество вершин {v₁,v₃} и есть вершинная база графа.