2.11. Подструктуры диграфа

2.11.1. Конденсация

Конденсация диграфа D=(V,E) – диграфD^*(S,F),FE, вершины которогоs₁,s₂,…,s_kсоответствуют сильным компонентам диграфаD, а дуга {s_i,s_j}Fпринадлежит диграфуD^*тогда и только тогда, когда вDсуществует дуга, источник которой находится в сильной компонентеs_i, а цель – в компонентеs_j.

Конденсация D^*любого диграфа не имеет циклов.

Класс сложности

1. Построить матрицу достижимости диграфа R(D).

2. Найти матрицу S(D) =R(D)*R^T(D), где * - оператор поэлементного умножения матриц, Т – операция транспонирования матриц.

3. Перестановкой строк и столбцов привести матрицу S(D) к блочно-диагональному виду, где каждый блок будет соответствовать некоторой сильной компоненте.

2.11.2. База и антибаза диграфа

База диграфа D=(V,E) – наименьшее (относительно включения) подмножество В вершин, удовлетворяющее условию:

любая вершина vV-Bдостижима из какой-либо вершиныvB.

Базовая компонента –сильная компонента диграфаD=(V,E), в которую не входит ни одна дуга из других сильных компонент. В конденсацииD^*=(S,F) таким компонентам соответствуют вершины с нулевыми полустепенями захода.

База и базовые компоненты связаны между собой:

Подмножество В вершин в диграфе D=(V,E) – база, если В состоит из вершин, принадлежащих базовым компонентам, причем в каждую базовую компоненту входит ровно одна вершина из множества В.

1. Построить конденсацию D^*=(S,F) диграфаD=(V,E).

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

3. Из каждой базовой компоненты выбирается по одной вершине (таким образом, база диграфа может быть определена не единственным образом).

Антибаза диграфа D=(V,E) – наименьшее (относительно включения) подмножество В^’вершин, удовлетворяющее условию:

любая вершина vVдостижима из какой-либо вершиныuV-B^’.

1. Построить конденсацию D^*=(S,F) диграфаD=(V,E).

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

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

2.11.3. Доминирующее множество вершин

Доминирующее множество вершинSдиграфаD=(V,E) – такое подмножество вершин, что для любой вершиныwV-Sсуществует такая вершинаvS, что {v,w}E.

4. Независимое множество вершин

Независимое множество вершин диграфа D=(V,E) – подмножество его вершин, в котором никакие две вершины не смежны между собой.

Доминирующее множество диграфа

Вершина vдиграфадоминируетнад вершинойu, если имеется дуга из вершиныvв вершинуu. Множество вершинSV называется:

• in доминирующим, если любая не находящаяся вSвершина доминируема любой вершиной изS;

• out доминирующим, если любая вершина множестваSдоминируема некоторой вершиной, не входящей во множествоS.

Пример

Ядро диграфа

Ядро диграфаD=(V,E) – множество вершин, которое одновременно являетсяoutдоминирующим и независимым.

Проблема нахождение ядра диграфа является NP-полной.

.12. Эйлеровы диграфы

Эйлеровым диграфом называется связный диграф, содержащий замкнутую прогулку со всеми дугами диграфа, взятыми точно по одному разу. Эта прогулка называетсяэйлеровым туром.

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

Существует формула определения числа эйлеровых туров в диграфе, названная по начальным буквам фамилий авторов BEST-формулой. Приведем некоторые предварительные определения:

• [A] – матрица связности диграфа;

• [M] =diag(d₁,d₂,d₃,…,d_|V|) – матрица, где диагоналями являются степени исхода (или захода) всех аершин диграфа, а остальные элементы – нули;

• [D] = [M] – [A] – Лапласиан или матрица Кирхгофа диграфа;

•  - детерминант (i,j) алгебраического дополнения матрицы [D] (все (i,j) алгебраические дополнения [D] равны между собой);

Тогда число эйлеровых туров в слабо связанном графе Rравно (BEST-формула):

R = (d₁-1)! (d₂-1) !…(d_n-1) !