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

4. Лекция: Достижимость в графах

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

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

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

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

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

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

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

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

R (x_i) = < x_i > Г +1 (x_i) Г +2 (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 нахождение вершин, входящих в путь, например из вершины х₂в вершинух₄, сводится к нахождениюТ + ( х₂) =< х₂, х₃, х₄, х₅, х₆>,

Т — ( х₄) =< х₁, х₂, х₃, х₄, х₅>, и их пересеченияT + (х₂) T – (х₄) =< х₂, х₃, х₄, х₅>.

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

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

a (2) _ik= n _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 равен числу путей длины 2, идущих изx_iвх_k.

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

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

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

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

dm_learning

Тема: Уравнения в идемпотентных полукольцах. Гомоморфизм графов. Алгоритмы обхода вершин графа.. Читаем, комментируем, решаем ДЗ.

Идемпотентные полукольца

Идемпотентным называется полукольцо, , в котором операция сложения идемпотентна: .

Примером таких полуколец являются:

• булево полукольцо ;
• .

В указанных полукольцах для каждого элемента можно ввести операцию итерации: — бесконечная сумма степеней элементов. Под степенью элемента понимается умножение его на себя раз, а нулевая степень равна единице полукольца по определению: .

Для приведённых выше полуколец итерация для любых элементов находится очень просто:

Идемпотентные полукольца интересны тем, что в них можно решать уравнения вида:

Интересно, что такие необычные для арифметики уравнения как или имеют здесь единственные решения:

Нахождение матрицы достижимости

Важной задачей в теории графов является нахождение матрицы достижимости по матрице смежности. Можно доказать, что матрица достижимости может быть получена как итерация матрицы смежности:

где элементами матриц являются нули и единицы, о операции соответствуют операциям идемпотентного полукольца . В этом случае матрица может быть получена при решении уравнения , так как оно эквивалентно уравнению , где — единичная матрица.

Таким образом, для получения матрицы необходимо решить систем уравнений следующего вида для :

где — элементы матрицы смежности, а — элементы единичной матрицы. Решением каждой из систем будет -й столбец матрицы .

Рассмотрим пример. На рисунке 1 показан ориентированный граф из шести вершин, матрица смежности которого равна:

1-й столбец

2-й столбец

3-6 столбцы

Полученная матрица достижимости примет вид:

Нахождение кратчайших путей

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

, где — весовая функция над некоторым полукольцом . Т.е. каждому ребру (или дуге) сопоставляется число, символизирующее длину пути, сложнсть задачи или любую другую стоимость перемещения между вершинами.

Рассмотрим граф, размеченный над полукольцом (см. рисунок 2).

Для такого графа можно записать матрицу метог дуг (эта матрица аналогична матрице смежностей), где

В нашем случае матрица меток дуг равна:

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

Матрица стоимостей находится аналогично, с помощью решения систем уравнений. Важно отметить, что в данном случае вся работа ведётся в полукольце , в котором нулём полукольца является , а единицей — 0!

1-й столбец

2-й столбец

3-6 столбцы

Полученная матрица стоимостей будет иметь вид:

Гомоморфизм и автоморфизм графов

Пусть заданы два графа и , отображение множества вершин первого графа во второе — гомоморфизм графа в , если . Если отображение биективно, то графы называются изоморфными.

Примеры гомоморфизма и не гомоморфизма представлены на рисунке 3.

Аналогичным образом гомоморфизм определяется для ориентированных графов. Рассмотрим соответвтующий пример: для заданного графа (см. рисунок 4) необходимо найти все друхвершинные гомоморфные образы.

Изоморфизм графа на себя (перестановка вершин) называется автоморфизмом.

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

Можно увидеть, что любая перестановка из множества дополнении к графу оставит граф неизменным:

Такие циклические перестановки можно записать в сокращённом виде:

Алгоритмы обхода графов. Поиск в глубину, поиск в ширину

Часто возникает задача обхода вершин и рёбер графа, т.е. посещение всех вершин или рёбер, причём только по одному разу. Такой обход может использоваться, например, в поиске информациии на графе. Существуют два широко известных алгоритма обхода вершин графа: поиск в глубину и поиск в ширину. В обоих из них поиск ведётся от какой-то вершины, избранной в качестве начальной.

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

С помощью рекурсии алгоритм поиска в глубину можно представить следующим образом:

Если стэк использовать явным образом, можно избавиться от рекурсивного вызова:

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

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

Порядок следования вершин и состояние стэка на каждом шаге:

Аналогично производится поиск в глубину на ориентированном графе (см. рисунок 7).

С помощью алгоритма поиска в глубину можно классифицировать дуги ориентированного графа следующим образом:

остовные дуги получаются непосредственно при поиске в глубину, образуют дерево (или в общем случае лес), на рисунке обозначены пунктиром; прямые дуги соединяют предка и потомка в остовном пути, на рисунке обозначены буквой F; обратные дуги соединяют потомка и предка в остовном пути, на рисунке обозначены буквой B, интересно то, что каждая из таких дуг задаёт элементарный контур в графе; перекрёстные дуги все остальные дуги, на рисунке обозначены буквой C.

Вторым широко распространённым алгоритмом является поиск в глубину. Это алгоритм использует очередь для хранения списка обрабатываемых вершин. В результате работы алгоритмя также получается остовное дерево, которое в общем случае отличается от дерева поика в глубину. Можно предложить следующий алгоритм поиска в ширину:

Рассмотрим пример поиска в ширину на неориентированном графе, изображённый не рисунке 8. Остовный подграф, получившийся при обходе вершин обозначен пунктиром. Порядок следования вершин и состояние очереди на каждом шаге представлены в табице:

1.5. Матрицы достижимости и связности

Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V=<V1,…, VN>. Обозначим через Ak=[A(K)Ij] K-ю степень матрицы смежности A(D).

Элемент A(K)Ij матрицы Ak ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины K из Vi в Vj.

Матрица достижимости ориентированного графа D − квадратная матрица T(D)=[Tij] порядка N, элементы которой равны

Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[Sij] порядка N, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[Sij] порядка N, элементы которой равны

Утверждение 3. Пусть D=(V,X) – ориентированный граф, V=<V1,…, VN>, A(D) – его матрица смежности. Тогда

1) T(D)=sign[E+A+A2+A3+… AN-1],

2) S(D)=T(D)&TT(D) (TT-транспонированная матрица, &- поэлементное умножение).

Пусть G=(V,X) – граф, V=<V1,…, VN>, A(G) – его матрица смежности. Тогда

S(G)=sign[E+A+A2+A3+… AN-1] (E— единичная матрица порядка N).

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

Привет, сегодня поговорим про матрица достижимости, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое матрица достижимости , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

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

В неориентированном графе достижимость между всеми парами вершин может быть определена путем идентификации связанных компонентов графа. Любая пара вершин в таком графе может достигать друг друга тогда и только тогда, когда они принадлежат одной компоненте связности; следовательно, в таком графе достижимость симметрична ( достигает если только достигает ). Связные компоненты неориентированного графа могут быть идентифицированы за линейное время. Остальная часть статьи посвящена более сложной проблеме определения попарной достижимости в ориентированном графе (который, кстати, не обязательно должен быть симметричным).

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

Утверждение. ЕслиА– матрица смежности графа, то элементматрицыА п равен числу маршрутов длинып, соединяющих вершиныv_i иv_jграфаG.

Доказательство.Методом математической индукции по числуп.

База индукции.Прип= 1 утверждение верно, так как всякое ребро графаG– это маршрут длины 1.

Индуктивное предположение.Пусть утверждение справедливо для всехnk.

Индуктивный переход.Рассмотрим матрицуА k +1 . В ней.

В силу индуктивного предположения произведение есть число маршрутов длиныk+ 1, соединяющих вершинуv_i с вершинойv_jс предпоследней вершиной всех таких маршрутовv_m. Значит, суммадействительно равна числу маршрутов длинk+ 1, соединяющих вершинуv_i с вершинойv_j.

Следствие.Пусть– связный граф срвершинами. Тогда любые две вершины графаможно соединить простой цепью. Но в простой цепи не может быть более (р1) ребер. Следовательно, все элементы матрицыотличны от нуля. Ясно, что верно и обратное утверждение.

В некоторых случаях при вычислениях степеней матрицы Аи матрицыСважно знать не число соответствующих маршрутов, а только есть ли в графе эти маршруты или нет . Об этом говорит сайт https://intellect.icu . Тогда при вычислении элементов матрицА 2 ,А 3 , … ,А р -1 вместо обычного сложения используют операцию, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицыА,А 2 ,А 3 , …,A p — 1 ,Cсостоят только из нулей и единиц.

Полученная таким образом матрица Сназываетсяматрицей достижимостиграфаG. ГрафGсвязен тогда и только тогда, когда каждый элемент матрицы достижимости равен 1 (р3).

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

Случай орграфа ничем не отличается от случая неориентированного графа. Если G– орграф ср вершинами иА– его матрица смежности, то элементматрицыА п равен числу ориентированных маршрутов длинып, соединяющих вершинуv_i с вершинойv_j.

+Граф G сильно связен тогда и только тогда, когда каждый элемент его матрицы достижимостиравен 1.

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

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

Пусть дан простой граф , матрица смежности которого есть , где . Матрица смежности дает информацию о всехпутях длины 1 (то есть, ребрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения с самим собой:

.

По определению, матрица композиции отношений есть , где — конъюнкция, а — дизъюнкция.

После нахождения матриц композиций для всех , будет получена информация о всех путях длины от до . Таким образом, матрица есть искомая матрица достижимости.

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

Если булевы операции дизъюнкции и конъюнкции заменить обычными алгебраическими операциями сложения и умножения соответственно, нахождение матрицы достижимости сведется к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных ребер в графе.

Пример

Граф

Рассмотрим простой связный ориентированный граф . Он имеет матрицу смежности вида:

, , :

Таким образом, из вершины можно добраться в любую другую.

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

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

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

Существует другой алгоритм, позволяющий найти матрицу достижимости в точности за шагов — алгоритм Уоршелла.

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

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

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

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

Матрица сильной связности может быть построена из матрицы достижимости. Пусть — матрица достижимости орграфа . Тогда матрица сильной связности состоит из элементов .

Пример

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

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

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

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

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

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

Программа 1. Вычисление матрицы достижимости по заданной матрице смежностей с помощью алгоритма Уоршалла .

Связанные проблемы

Связанная с этим проблема — решить запросы о достижимости с некоторым числом. вершинных отказов. Например: «Может вершина все еще дойти до вершины хотя вершины потерпели неудачу и больше не могут быть использованы? »Подобная проблема может относиться к сбоям ребер, а не к сбоям вершин, или их сочетанию. Методика поиска в ширину работает так же хорошо с такими запросами, но создание эффективного оракула более важно сложно.

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

См. также

• Гаммоид
• st -соединение

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