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. Множество вершин S V называется:

• 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) !