Как найти матрицу контрдостижимости графа

Достижимость и контрдостижимость

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х_i быть передана другому лицу х_j, т. е. существует ли путь, идущий от вершины х_i к вершине х_j. Если такой путь существует, то говорят, что вершина х_j достижима из вершины х_i. Можно интересоваться достижимостью вершины х_j из вершины х_i только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т. п. задачи.

Достижимость в графе описывается матрицей достижимости R=[r_ij], i, j=1, 2, … n, где n – число вершин графа, а каждый элемент определяется следующим образом:

r_ij=1, если вершина х_j достижима из х_i,

r_ij=0, в противном случае.

Множество вершин R(x_i) графа G, достижимых из заданной вершины x_i, состоит из таких элементов x_j, для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г⁺¹(x_i) является множеством таких вершин x_j, которые достижимы из x_i с использованием путей длины 1, то множество Г⁺(Г⁺¹(x_i)) = Г⁺²(x_i) состоит из вершин, достижимых из x_i с использованием путей длины 2. Аналогично Г^+p(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длины p.

Так как любая вершина графа, которая достижима из x_i, должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, …, или p, то множество вершин, достижимых для вершины x_i, можно представить в виде

.

Как видим, множество достижимых вершин R(x_i) представляет собой прямое транзитивное замыкание вершины x_i, т. е. R (x_i) = T⁺(x_i). Следовательно, для построения матрицы достижимости находим достижимые множества R (x_i) для всех вершин . Полагая, r_ij=1, если и r_ij=0 в противном случае.

Для графа, приведенного на
рис.
4.1,а, множества достижимостей находятся следующим образом:

,

,

,

,

,

,

.

Матрица достижимости имеет вид, как показано на
рис.
4.1,в. Матрицу достижимости можно построить по матрице смежности (
рис.
4.1,б), формируя множества T⁺(x_i) для каждой вершины x_i
.

Матрица контрдостижимости Q = [ q_ij], i, j =1, 2, … n, где n – число вершин графа, определяется следующим образом:

q_ij=1, если из вершины x_j
можно достичь вершину x_i
,

q_ij=0, в противном случае.

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

.

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

Матрица контрдостижимости показана на
рис.
4.1,г.

Следует отметить, что поскольку все элементы матриц R и Q равны 1 или 0, то каждую строку можно хранить в двоичной форме, экономя затраты памяти ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как с вычислительной точки зрения основными операциями являются быстродействующие логические операции.

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

Достижимость и
контрдостижимость

Задач, в которых используется понятие
достижимости, довольно много.

Вот одна из них. Графможет быть
моделью какой-то организации, в которой
люди представлены вершинами, а дуги
интерпретируют каналы связи. При
рассмотрении такой модели можно поставить
вопрос, может ли информация от одного
лицах_iбыть передана другому лицух_j, т. е. существует ли путь, идущий от
вершиных_iк вершинех_j. Если такой путь существует, то говорят,
что вершинах_jдостижимаиз вершиных_i.
Можно интересоваться достижимостью
вершиных_jиз вершиных_iтолько на таких путях, длины которых не
превосходят заданной величины или длина
которых меньше наибольшего числа вершин
в графе и т. п. задачи.

Достижимость в графе описывается
матрицей достижимости R=[r_ij],
i, j=1, 2, … n, гдеn–
число вершин графа, а каждый элемент
определяется следующим образом:

r_ij=1,
если вершинах_jдостижима изх_i,

r_ij=0,
в противном случае.

Множество вершин R(x_i)графаG, достижимых из
заданной вершиныx_i, состоит из таких элементовx_i, для которых(i, j)-й
элемент в матрице достижимостей равен
1. Очевидно, что все диагональные элементы
в матрицеRравны 1,
поскольку каждая вершина достижима из
себя самой путeм длины 0. Поскольку прямое
отображение 1-го порядкаГ⁺¹(x_i)является множеством таких вершинx_j, которые достижимы изx_iс использованием путей длины 1, то
множествоГ⁺(Г⁺¹(x_i))
= Г⁺²(x_i)состоит из вершин, достижимых изx_iс использованием путей длины 2. АналогичноГ^+p(x_i)является множеством вершин, которые
достижимы из x_i с помощью путей
длиныp.

Так как любая вершина графа, которая
достижима из x_i, должна быть достижима с использованием
пути (или путей) длины 0 или 1, или 2, …,
илиp, то множество
вершин, достижимых для вершиныx_i, можно представить в виде

R (x_i)
= { x_i }
Г⁺¹(x_i)

Г⁺²(x_i)
…Г^+p(x_i).

Как видим, множество достижимых вершин
R(x_i)представляет собой прямое транзитивное
замыкание вершиныx_i, т. е.R(x_i)
= T⁺(x_i).
Следовательно, для построения матрицы
достижимости находим достижимые
множестваR(x_i)для всех вершинx_iX.
Полагая,r_ij=1,
еслиx_j
R(x_i)иr_ij=0в противном случае.

Рис. 4.1. Достижимость в графе: а –граф;
б – матрица смежности; в – матрица
достижимости; г- матрица контрдостижимости.

Для графа, приведенного на рис. 4.1,а,
множества достижимостейнаходятся
следующим образом:

R (х₁) = { х₁}{ х₂, х₅}{ х₂, х₄, х₅ }{ х₂, х₄, х₅} = { х₁,
х₂, х₄, х₅},

R (х₂) = { х₂}{ х₂, х₄}{ х₂, х₄, х₅}{
х₂, х₄, х₅} = { х₂,
х₄, х₅},

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

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

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

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

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

Матрица достижимостиимеет вид,
как показано на рис. 4.1,в.Матрицу
достижимости можно построить поматрице смежности(рис. 4.1,б), формируя
множестваT⁺(x_i)для каждой вершиныx_i.

Матрица контрдостижимостиQ
= [ q_ij],i, j =1, 2, … n, гдеn– число вершин графа, определяется
следующим образом:

q_ij=1,
если из вершиныx_jможно достичь вершинуx_i,

q_ij=0,
в противном случае.

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

Q (x_i)
= { x_i }
Г^-1(x_i)
Г^—2(x_i)
…Г^-p(x_i).

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

Матрица контрдостижимостипоказана
на рис. 4.1,г.

Следует отметить, что поскольку все
элементы матриц RиQравны 1 или 0, то каждую строку можно
хранить в двоичной форме, экономя затраты
памяти ЭВМ. МатрицыRиQудобны для обработки
на ЭВМ, так как с вычислительной точки
зрения основными операциями являются
быстродействующие логические операции.

Нахождение
множества вершин, входящих в путь

Если необходимо узнать о вершинах графа,
входящих в эти пути, то следует вспомнить
определения прямого и обратного
транзитивных замыканий. Так как T⁺(x_i)– это множество вершин, в которые есть
пути из вершиныx_i,
аT^–(х_j)– множество вершин, из которых есть
пути вx_j, тоT⁺(x_i)
T^–(x_j)– множество вершин, каждая из которых
принадлежит, по крайней мере, одному
пути, идущему отx_iкx_j
. Эти вершины называются существенными
или неотъемлемыми относительно двух
концевых вершинx_iиx_j. Все остальные вершины графа называются
несущественными или избыточными,
поскольку их удаление не влияет на пути
отx_iкx_j.

Рис. 4.2. Орграф

Так для графа на рис. 4.2 нахождение
вершин, входящих в путь, например из
вершины х₂в вершинух₄, сводится к нахождениюТ⁺(
х₂)
={ х₂,
х₃,
х₄,
х₅,
х₆},

Т^—(
х₄)
={ х₁,
х₂,
х₃,
х₄,
х₅},
и их пересеченияT⁺(х₂)
T^–(х₄)
={ х₂,
х₃,
х₄,
х₅}.

Матричный метод нахождения путей в
графах

Матрица смежности полностью определяет
структуру графа. Возведем матрицу
смежности в квадрат по правилам
математики. Каждый элемент матрицы А²
определяется по формуле

a⁽²⁾_ik=ⁿ_j=1^a_ij^a_jk

Слагаемое в формуле равно 1 тогда и
только тогда, когда оба числа a_ijиa_jk
равны 1, в противном случае оно равно
0. Поскольку из равенстваa_ij
= a_jk
= 1следует существование пути длины
2 из вершиныx_iв вершинух_k, проходящего через вершинуx_j, то (i -й,k-й) элемент матрицыА²равен числу путей длины 2, идущих изx_iвх_k.

В таблице 4.1a представлена матрица
смежности графа, изображенного на рис.
4.2. Результат возведения матрицы смежности
в квадрат А²показан в таблице 4.1б.

Так «1», стоящая на пересечении
второй строки и четвертого столбца,
говорит о существовании одного пути
длиной 2 из вершины х₂к вершинех₄. Действительно, как видим вграфена рис. 4.2, существует такой путь:a₆,
a₅. «2» в
матрицеA²говорит о существовании двух путей
длиной 2 от вершиных₃к вершинех₆:a₈,
a₄иa₁₀,
a₃.

Аналогично для матрицы смежности,
возведенной в третью степень A³
(таблица 4.1в),a ⁽³⁾
_ikравно числу
путей длиной 3, идущих отx_iкх_k. Из четвертой строки матрицыA³видно, что пути длиной 3 существуют: один
изх₄вх₄(a₉,
a₈,
a₅),
один изх₄в

х₅(a₉,
a₁₀,
a₆)и два пути изх₄вх₆(a₉,
a₁₀,
a₃
и a₉,
a₈,
a₄).
МатрицаA⁴показывает существование путей длиной
4 (таблица 4.1г).

Таким образом, если a ^р
_ikявляется
элементом матрицыA^р,тоa ^р
_ikравно числу
путей (не обязательно орцепей или простых
орцепей) длиныр, идущих
отx_iкх_k.

Соседние файлы в папке МОТС

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Матрица достижимости простого ориентированного графа [math]displaystyle{ G=(V, A) }[/math] — бинарная матрица замыкания по транзитивности отношения [math]displaystyle{ A }[/math] (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Способы построения матрицы достижимости

Перемножение матриц

Пусть дан простой граф [math]displaystyle{ G=(V, A) }[/math], матрица смежности которого есть [math]displaystyle{ mathbf A = (a_{ij})_{n times n} }[/math], где [math]displaystyle{ a_{ij} = 1 Leftrightarrow (i, j) in A }[/math]. Матрица смежности даёт информацию о всех путях длины 1 (то есть дугах) в орграфе. Для поиска путей длины 2 можно найти композицию отношения [math]displaystyle{ A }[/math] с самим собой:

[math]displaystyle{ Acirc A = bigl { (a, c): exists b in V: (a, b), (b, c) in A bigr } }[/math].

По определению, матрица композиции отношений [math]displaystyle{ A circ A }[/math] есть [math]displaystyle{ mathbf{A^2} = ({a^2}_{ij})_{n times n}=Bigl (sum_k a_{ik} a_{kj} Bigr )=Bigl ( (a_{i1} land a_{1j}) lor (a_{i2} land a_{2j} ) lor ldots lor (a_{in} land a_{nj}) Bigr ) }[/math], где [math]displaystyle{ land }[/math] — конъюнкция, а [math]displaystyle{ lor }[/math] — дизъюнкция.

После нахождения матриц [math]displaystyle{ mathbf A^k }[/math] композиций [math]displaystyle{ underbrace {A circ ldots circ A}_k }[/math] для всех [math]displaystyle{ k }[/math], [math]displaystyle{ 1 leq k leq n-1 }[/math] будет получена информация о всех путях длины от [math]displaystyle{ 1 }[/math] до [math]displaystyle{ n-1 }[/math]. Таким образом, матрица [math]displaystyle{ mathbf {R(G)} = mathbf E lor mathbf{A} lor mathbf{A^2} lor ldots lor mathbf{A^{n-1}} = ({a^*}_{ij})_{n times n} = ({a}_{ij} lor {a^2}_{ij} lor ldots lor {a^{n-1}}_{ij}) }[/math] есть искомая матрица достижимости, где [math]displaystyle{ mathbf E }[/math] — единичная матрица.

[math]displaystyle{
mathbf E =
begin{pmatrix}
1&0&0&0 \
0&1&0&0 \
0&0&1&0 \
0&0&0&1
end{pmatrix}
}[/math]

Случай нескольких путей

Если булевы операции [math]displaystyle{ lor, land }[/math] дизъюнкции и конъюнкции заменить обычными алгебраическими операциями [math]displaystyle{ +, times }[/math] сложения и умножения соответственно, нахождение матрицы достижимости [math]displaystyle{ mathbf{R(G)} }[/math] сведётся к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица [math]displaystyle{ mathbf{R(G)} }[/math] будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных рёбер в графе.

Пример

Рассмотрим простой связный ориентированный граф [math]displaystyle{ G=(V={1, 2, 3, 4}, A
={(1, 2), (1, 3), (3, 2), (3, 4), (4, 3)}) }[/math].
Он имеет матрицу смежности [math]displaystyle{ mathbf A }[/math] вида:

[math]displaystyle{
mathbf A =
begin{pmatrix}
0&1&1&0 \
0&0&0&0 \
0&1&0&1 \
0&0&1&0
end{pmatrix}
}[/math]

Найдём булевы степени этой матрицы [math]displaystyle{ mathbf{A^2} }[/math], [math]displaystyle{ mathbf{A^3} }[/math]:

[math]displaystyle{
mathbf{A^2} =
begin{pmatrix}
0&1&0&1 \
0&0&0&0 \
0&0&1&0 \
0&1&0&1
end{pmatrix}
}[/math],
[math]displaystyle{
mathbf{A^3} =
begin{pmatrix}
0&0&1&0 \
0&0&0&0 \
0&1&0&1 \
0&0&1&0
end{pmatrix}
}[/math],

Получим матрицу достижимости

[math]displaystyle{ mathbf{R(G)} = mathbf{E lor A lor A^2 lor A^3} = begin{pmatrix} 1&1&1&1 \ 0&1&0&0 \ 0&1&1&1 \ 0&1&1&1 end{pmatrix} }[/math]

Таким образом, из вершины [math]displaystyle{ 1 }[/math] можно добраться в любую другую.

При использовании же алгебраических операций получится матрица

[math]displaystyle{ mathbf{R(G)} = mathbf{E + A + A^2 + A^3} = begin{pmatrix} 1&2&2&1 \ 0&1&0&0 \ 0&2&2&2 \ 0&1&2&2 end{pmatrix} }[/math]

Она показывает количество путей длины от 0 до 3 между вершинами орграфа.

Алгоритм Уоршелла

Существует другой алгоритм, позволяющий найти матрицу достижимости в точности за [math]displaystyle{ 2n^3 }[/math] шагов — алгоритм Уоршелла.

Связанные понятия

Матрица сильной связности

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

Построение матрицы сильной связности

Матрица сильной связности может быть построена из матрицы достижимости. Пусть [math]displaystyle{ mathbf E^* }[/math] — матрица достижимости орграфа [math]displaystyle{ G=(V, E) }[/math]. Тогда матрица сильной связности [math]displaystyle{ mathbf C }[/math] состоит из элементов [math]displaystyle{ (c_{ij}) = left ( (e_{ij}) land (e_{ji}) right ) }[/math].

Пример

Рассмотрим тот же граф, что и ранее.

Его матрица достижимости:

[math]displaystyle{ mathbf{E^*} = begin{pmatrix} 1&1&1&1 \ 0&1&0&0 \ 0&1&1&1 \ 0&1&1&1 end{pmatrix} }[/math]

Из неё получаем матрицу сильной связности:

[math]displaystyle{ mathbf{C} = begin{pmatrix} 1&0&0&0 \ 0&1&0&0 \ 0&0&1&1 \ 0&0&1&1 end{pmatrix} }[/math]

Вершины 3 и 4 сильно связаны друг с другом и сами с собой.

Матрица связности графа

Для обычного (не ориентированного) связного графа существует понятие матрицы связности, сходное с матрицей достижимости.

Матрица контрдостижимости

Матрица контрдостижимости Q графа G может быть найдена из матрицы достижимости путем ее транспонирования.

Примечания