Определение оптимальной базы графа

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

1. Каждая вершина графа достижима хотя бы из одной вершины множества В.

2. Среди вершин базы В нет вершины, которая достижима из другой вершины множества В.

3. Множество вершин В должно быть наименьшим.

Рассмотрим алгоритм нахождения базы графа.

1. Для графа строится его конденсация (п.2.3.2).

2. Среди вершин Y_i графа конденсации находим такие, в которые не заходит ни одна дуга (Y_i являются сильными компонентами исходного графа). Пусть такими вершинами будут Y_l, Y_m.

3. Для построения базы нужно из каждой выбранной на 2-м шаге сильной компоненты (Y_l = {X₁^l, X₂^l,…, X_N^l}, Y_m = {X₁^m, X₂^m,…, X_N^m}) взять по одной вершине (x_i^l, x_j^m). Эти вершины и будут определять базу графа. Чтобы определить оптимальную базу, нужно знать длину дуг. Оптимальная база имеет минимальное суммарное расстояние до всех вершин графа. Алгоритм определения длин кратчайших путей между всеми вершинами графа одновременно будет дан в п.3.4.2.

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

Определение оптимальной антибазы графа

Антибазой графа В^-1 является такое множество вершин графа, которое удовлетворяет следующим условиям.

1. Из каждой вершины графа можно достичь хотя бы одной вершины множества В^-1.

2. Среди множества вершин В^-1 нет вершины, которая достижима из другой вершины этого множества В^-1.

3. Множество вершин В^-1 должно быть минимальным.

Рассмотрим алгоритм нахождения антибазы графа.

1. Для графа строится его конденсация (п.2.3.2).

2. Среди вершин Y_i графа конденсации находим такие, из которых не выходит ни одна дуга. Пусть такими вершинами будут Y_k, Y_f.

3. Для построения антибазы нужно из каждой выбранной на 2-м шаге сильной компоненты (Y_k = {x₁^k, x₂^k,…, x_N^k}, Y_f = {x₁^k, x₂^k,…, x_N^k}) взять по одной вершине (x_i^k, x_j^k). Эти вершины будут определять антибазу графа. Оптимальная антибаза имеет минимальное суммарное расстояние от всех вершин графа (см. п.3.4.2).