И контрдостижимостей

 

Матрица достижимостей графа G=(X,V) , определяется следующим образом:

 

Множество вершин R(xi) графа G, достижимых из заданной вершины xi, состоит из таких элементов xj, для которых (i, j)-й элемент в матрице достижимостей равен 1. Считают, что каждая вершина достижима из себя самой с помощью пути длины 0, поэтому все диагональные элементы в матрице R равны 1.

Поскольку Г(xi) является множеством таких вершин xj, которые достижимы из xi c использованием путей длины 1 (т.е. Г(xi) – такое множество вершин, для которых в графе суще­ствуют дуги (xi, xj)) и поскольку Г(xj) является множеством вершин, достижимых из xj с помощью путей длины 1, то множество Г(Г(xi))=Г2(xi) состоит из вершин, достижимых из xi c использованием путей длины 2. Аналогично Гp(xi) является множеством вершин, которые достижимы из xi с помощью путей длины р.

Так как любая вершина графа G, которая достижима из xi, должна быть достижима с использованием пути (или путей) дли­ны 0, или 1, или 2, ..., или р (с некоторым конечным р≤n), то множество вершин, достижимых из xi , можно представить в виде

R(xi) = { xi }ÈГ(xi)È Г2 (xi )È…È Гp (xi ) (4.3)

Таким образом, множество R(xi) может быть получено последова­тельным выполнением (слева направо) операций объединения в соотношении (4.3), до тех пор, пока «текущее» множество не перестанет изменяться при очередной операции объединения. С этого момента последующие операции не будут давать новых элементов множеству и, таким образом, будет получено, достижимое множество R(xi). Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число р меньше числа вершин в графе.

Матрицу достижимостей можно построить так. Находим достижимые множества R(xi) для всех вершин xiÎХ способом, приведенным выше. Положим rij=1, если xjÎR(xi), и rij=0 в противном случае. Полученная таким образом матрица R является матрицей достижимостей.

Матрица контрдостижимостей (матрица обратных достижимостей) , определяется следующим образом:

 

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

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

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

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

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

 

Рис.4.24

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

 

 


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

R(x1)={x1} È {x2,x5} È {x2,x4,x5} È {x2,x4,x5} = {x1,x2,x4,x5},

R(x2)= {x2} È {x2,x4} È {x2,x4,x5} È {x2,x4,x5} = {x2,x4,x5},

R(х3)= {x3} È {x4} È {x5} È {x5} = {x3,x4,x5},

R(х4)= {x4} È {x5} È {x5} = {x4,x5},

R(х5)= {x5} È {x5} = {x5},

R(х6)= {x6} È {x3,x7} È {x4Èx6} È {x3,x5,x7} È {x4,x5,x6}=

= {x3,x4,x5,x6,x7},

R(х7)= {x7} È {x4,x6} È {x3,x5,x7} È {x4,x5,x6}=

= {x3,x4,x5,x6,x7}.

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

 
 

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

 

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

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

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

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

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

 

 








Дата добавления: 2015-04-10; просмотров: 1834;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.01 сек.