Материал: Дискретная математика. учебное пособие. Собенина О.В

Контрдостижимым множеством Q(x_i) графа G является множество таких вершин, что из любой вершины этого множества можно достигнуть вершину x_i. Аналогично построению достижимого множества R(x_i) на основе соотношения (4.3) можно «сформиро­вать» множество Q(x_i), используя следующее выражение:

Q(x_i) = {x_i} È Г^-1 (x_i) È Г^-2 (x_i) È … È Г^-р (x_i), (4.4) где Г^-2 (x_i) = Г^-1 (Г^-1 (x_i)) и т. д.

Операции, выполняются слева направо до тех пор, пока очередная операция объединения не перестанет изменять «текущее» множе­ство Q(x_i).

Из определений очевидно, что столбец x_i матрицы Q (в котором q_ij=1, если x_iÎQ(x_i), и q_ij=0 в противном случае) совпадает со строкой x_i матрицы R, т. е. Q=R^T, где R^T – матрица, транспонированная к матрице достижимостей R.

Пример. Найти матрицы достижимостей и обратных достижимостей для графа G, приведенного на рис. 4.24.

Рис.4.24

Матрица смежности графа G имеет вид

Множества достижимостей находятся с помощью соотношений

R(x₁)={x₁} È {x₂,x₅} È {x₂,x₄,x₅} È {x₂,x₄,x₅} = {x₁,x₂,x₄,x₅},

R(x₂)= {x₂} È {x₂,x₄} È {x₂,x₄,x₅} È {x₂,x₄,x₅} = {x₂,x₄,x₅},

R(х₃)= {x₃} È {x₄} È {x₅} È {x₅} = {x₃,x₄,x₅},

R(х₄)= {x₄} È {x₅} È {x₅} = {x₄,x₅},

R(х₅)= {x₅} È {x₅} = {x₅},

R(х₆)= {x₆} È {x₃,x₇} È {x₄Èx₆} È {x₃,x₅,x₇} È {x₄,x₅,x₆}=

= {x₃,x₄,x₅,x₆,x₇},

R(х₇)= {x₇} È {x₄,x₆} È {x₃,x₅,x₇} È {x₄,x₅,x₆}=

= {x₃,x₄,x₅,x₆,x₇}.

Следовательно, матрица достижимостей имеет вид

м атрица обратных достижимостей такова:

Так как R(x_i) является множеством вершин, достижимых из x_i, а Q(x_j) – множеством вершин, из которых можно достиг­нуть x_j, то – множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от x_i к x_j. Эти вершины называются существенными или неотъем­лемыми относительно двух концевых вершин x_i и x_j. Все остальные вершины называются несуществен­ными или избыточными, поскольку их удаление не влияет на пути от x_i к x_{j .}

Матрицы достижимостей и обратных достижимостей являются полными в том смысле, что на длины путей от x_i к x_j не накладывались никакие ограничения. С другой стороны, можно определить матрицы ограниченных достижимостей и контрдостижимостей – надо потребовать, чтобы длины путей не превышали некоторого заданного числа. Эти ограниченные матрицы тоже могут быть построены с помощью соотношений (4.3) и (4.4) – надо действовать точно так, как раньше, при нахожде­нии «неограниченных» матриц, но только теперь р будет верхней границей длины допустимых путей.

Для неориентированного графа множество достижимости позволяет проверить граф на связность. Опишем алгоритм проверки связности неорграфа.

Шаг 1. G =(X,V) – данный неорграф. Для произвольной вершины х_iХ найти множество R(x_i). Перейти к шагу 2.

Шаг 2. Если R(x_i)=X, то граф является связным, иначе граф не является связным. Выдать соответствующее сообщение. Останов.

4.8.3. Нахождение сильных компонент

Сильная компонента (СК) графа G определяется как максимальный сильно связный подграф графа G. Поскольку в сильно связном графе произвольная вершина x_j достижима из любой другой вершины x_i, то в ориентированном графе существует одна и только одна СК, содержащая данную вершину x_i. В самом деле, если бы вершина x_i, принадлежала двум или большему числу сильных компонент, то существовал бы путь из любой вершины одной СК в произвольную вершину другой СК и, следовательно, объединение этих сильных компо­нент было бы сильно связным графом, что противоречит опре­делению СК.

Если вершина x_i, одновременно является начальной и конечной вершиной пути, то множество вершин, существенных относительно этих двух идентичных концов (т.е. множество вершин некоторого цикла, содержащего x_i), совпадает с пересечением . Поскольку все эти существенные вершины достижимы из x_i и, кроме того, из каждой такой вершины достижима вершина x_i, то все они взаимно достижимы. Более того, если нет другой вершины, существенной относительно концов x_i и x_i, то множество , которое может быть построено с использованием соотношений (4.3) и (4.4), однозначно определяет СК графа G, содержащую вершину x_i.

Если эти вершины удалить из графа G=(X,V), то в оставшемся порожденном подграфе можно таким же способом выделить новую СК, содержащую x_jÎ . Эту процедуру можно повторять до тех пор, пока все вершины графа G не будут сгруппированы в соответствующие СК. После завершения этой процедуры граф G будет разбит на свои сильные компоненты.

Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов

Шаг 1. G = (X, V) – данный граф. Определение сильных компонент графа (СК) начать с произвольной вершины х_iХ. Найти R(x_i) и Q(x_i). Положить СК(х_i) = - сильная компонента графа, содержащая вершину х_i.

Шаг 2. Определить множество . Если , то и перейти к шагу 1, иначе останов, так как все сильные компоненты определены.

Граф G*=(X*,V*) определяется так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (x_i*, x_j*) существует в G* тогда и только тогда, когда в G существует дуга (x_i, x_j), такая, что x_i принадлежит ком­поненте, соответствующей вершине x_i*, а x_j – компоненте, соответствующей вершине x_j*. Граф G* называют конденсацией графа G.

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

Пример. Для графа G, приведенного на рис. 4.25, найти сильные ком­поненты и построить конденсацию G*.

Найдем СК в G, содержащую вершину x₁.

Из соотношений (4.3) и (4.4) получаем

R(x₁) = { x₁ , x₂ , x₄ , x₅ , x₆ , x₇ , x₈ , x₉ , x₁₀ }

Q(x₁) = { x₁ , x₂ , x₃ , x₅ , x₆ }

Следовательно, СК, содержащая вершину x₁, является порожденным подграфом

R(x₁) Q(x₁) = ({ x₁ , x₂ , x₅ , x₆ })

Аналогично, СК, содержащая вершину x₈, есть порожденный подграф ({x₈, x₁₀}), СК содержащая x₇ – подграф ({x₄, x₇, x₉}), СК, содержащая x₁₁, – подграф ({x₁₁, x₁₂, x₁₃ }) и СК, содержащая x₃, – подграф ({x₃}). Следует отметить, что последняя СК со­стоит из единственной вершины графа G. Конденсация G* приведена на рис. 4.26.

Рис. 4.26. G* - конденсация графа G

Процедуру, описанную выше и связанную с нахождением СК графа, можно сделать более удобной, если непосредственно исполь­зовать матрицы R и Q. Пусть запись RÄQ означает поэлементное умножение этих матриц. Тогда сразу видно, что строка x_i, матрицы RÄQ содержит единицы только в тех столбцах x_j, для которых выполняется усло­вие: вершины x_i и x_j взаимно достижимы; в других местах строки x_i стоят нули. Таким образом, две вершины находятся в одной и той же СК тогда и только тогда, когда соответствующие им стро­ки (или столбцы) в матрице RÄQ идентичны. Вершины, кото­рым соответствуют строки, содержащие 1 в столбце x_j, образуют множество вершин СК, содержащей x_j. Отсюда мгновенно сле­дует, что матрицу RÄQ можно преобразовать путем транспони­рования строк и столбцов в блочно-диагональную. Каждая из диа­гональных подматриц этой матрицы соответствует СК графа G и содержит только единичные элементы, все остальные элементы блочно-диагональной матрицы равны нулю. Для приведенного ранее примера матрица RÄQ, преобразованная соответствую­щим образом, имеет вид

Таким образом, сильные компоненты графа можно находить по следующему алгоритму.

Шаг 1. G – данный граф. Для G построить матрицу достижимости R и найти матрицу контрдостижимости, транспонировав матрицу R, Q=R^T.

Шаг 2. Получить матрицу C, осуществив поэлементное умножение матриц R и Q, т.е. С=RQ, где  – поэлементное умножение матриц.

Шаг 3. Преобразовать матрицу С к блочно-диагональ-ному виду путем перестановки строк и столбцов. Каждая из диагональных подматриц соответствует сильной компоненте графа G. Останов.

4.8.4. Базы и антибазы

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

Базой является такое множество вершин графа G, которое удовлетворяет следующим двум условиям:

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

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

Из этих условий получаются следующие утверждения.

1. В множестве В нет двух вершин, которые принадлежат одной и той же СК графа G.

2. В любом графе без контуров существует единственная база. Она состоит из всех таких вершин, полустепени захода которых равны 0.

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

Шаг 1. G – данный граф. Для G найти все сильные компоненты.

Шаг 2. Построить конденсацию G* графа G.

Шаг 3. Определить базу В* конденсации G*, включив в В* те вершины G*, полустепени захода которых равны 0.

Шаг 4. Построить базу В графа G из В*, взяв по одной вершине из сильных компонент, входящих в В*. Останов.

Пример. Для графа G, приведенного на рис. 4.25, конденсация показана на рис. 4.26. Базой графа G* является множества , поскольку и  единственные вершины в графе G* с полустепенями захода, равными 0. Базами графа G являются , и .

Понятие, двойственное понятию базы есть антибаза. Антибаза графа G есть такое минимально возможное множестве вершин, что какова бы ни была вершина графа G, из нее достижима некоторая вершина в . Свойства антибаз аналогичны свойствам баз, надо только «прямые» понятия заменить на двойственные. Опишем алгоритм нахождения антибаз графа.