Антибаза

Антибаза орграфа G - наименьшее (относительно включения) подмножество вершин B¢, удовлетворяющее условию: любая вершина vÎ V, достижима из какой-либо вершины vÎ V/ B¢.

Алгоритм построения антибазы

1. Построить конденсацию G ^*.

2. Выделить в конденсации вершины с нулевыми полустепенями исхода.

3. Из каждой компоненты, соответствующей такой вершине, выбирается по одной вершине.

Например:

Задан граф G. Найти базу и антибазу.

Решение:

Построим конденсацию G ^*:

Матрица достижимости R_G :

Матрица контрдостижимости Q_G :

Матрица взаимной достижимости S_G :

Для базы:

1. Выделим в конденсации вершины с нулевыми полустепенями захода.

Базовые компоненты: S₁ и S₃.

2. Базы орграфа G: {1, 4}; {1, 5}; {2, 4}; {2, 5}; {3, 4}; {3, 5}.

Для антибазы:

1. Выделить в конденсации вершины с нулевыми полустепенями исхода.

Антибазовые компоненты: S₄.

2. Антибаза орграфа G: {7}; {8}.