Как составить матрицу достижимости по матрице смежности

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

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х_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 удобны для обработки на ЭВМ, так как с вычислительной точки зрения основными операциями являются быстродействующие логические операции.

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

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

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

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

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

Утверждение. ЕслиА– матрица смежности графа, то элементматрицыА^правен числу маршрутов длинып, соединяющих вершины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 . Тогда при вычислении элементов матрицА²,А³, … ,А^р-1вместо обычного сложения используют операцию, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицыА,А²,А³, …,A^p—1,Cсостоят только из нулей и единиц.

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

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

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

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

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

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

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

.

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

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

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

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

Пример

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

Найдем булевы степени этой матрицы , , :

, , .

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

#include <iostream.h>
#define MaxNodes 4

class Warshall
{
  private:
    unsigned Adj[MaxNodes][MaxNodes];  //Матрица смежностей.
    unsigned Path[MaxNodes][MaxNodes]; //Матрица достижимости.
  public:
    void Vvod();
    void TransClose();
    void Vyvod();
};

void Warshall::Vvod()
{
  //Ввод матрицы смежностей заданного графа.
  cout <<"Вводите элементы матрицы смежностей по строкам:n";
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
     {
       cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
       cin >> Adj[i][j];
     }
}

void Warshall::TransClose()
//Вычисление матрицы достижимости.
{
  //Инициализация матрицы Path матрицей смежностей Adj.
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
      Path[i][j] = Adj[i][j];
  //Нахождение следующих значений матрицы Path.
  for (int k=0;k<MaxNodes;k++)
    for (i=0;i<MaxNodes;i++)
      if (Path[i][k]==1) 
         for (int j=0;j<MaxNodes;j++)
               Path[i][j] = (Path[i][j] || Path[k][j]);
}

void Warshall::Vyvod()
//Вывод матрицы достижимости.
{
  cout << "Матрица достижимости:n";
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;j<MaxNodes;j++)
      cout << Path[i][j] << " ";
    cout << endl;
  }
}

void main()
{
  Warshall A;
  A.Vvod();
  A.TransClose();
  A.Vyvod();
}

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

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

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

Вау!! 😲 Ты еще не читал? Это зря!

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

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

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

Задач,
в которых используется понятие
достижимости,
довольно много. Вот одна из них. Граф
может быть моделью какой-то организации,
в которой люди представлены вершинами,
а дуги интерпретируют каналы связи. При
рассмотрении такой модели можно поставить
вопрос, может ли информация от одного
лица х_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
}
Г^-1x_i)

Г^-2x_i)

…

Г^-px_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 удобны
для обработки на ЭВМ, так как с
вычислительной точки зрения основными
операциями являются быстродействующие
логические операции.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

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

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

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

• :
• : для любого

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

1-й столбец

2-й столбец

3-6 столбцы

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

1-й столбец

2-й столбец

3-6 столбцы

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

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

bool visited[N] = {false, ... }; // массив флагов посещённых вершин
edge edges[M];                   // массив рёбер

// рекурсивная процедура поиска
void deep_search(vertex_t v) {

    visited[v] = true; // отметить вершину как посещённую     
    ...                // сделать с вершиной то, ради чего обход затевался

    for(size_t i = 0; i < M; i++) {
        edge e = edges[i];
        if(e.from == v && !visited[e.to]) {
             deep_search(e.to);
        }  
    }
}

bool visited[N] = {false, ... }; // массив флагов посещённых вершин
edge edges[M];                   // массив рёбер
stack<vertex_t> s;               // стэк

// нерекурсивная процедура поиска
void deep_search(vertex_t v0) {

    s.push(v0);

    while(!s.empty()) {
        vertex_t v = s.pop();

        if(visited[v]) continue; // пропустить посещённую вершину

        visited[v] = true; // отметить вершину как посещённую
        ...                // сделать с вершиной что-то
   
        for(size_t i = 0; i < M; i++) {
            edge e = edges[i];
            if(e.from == v && !visited[e.to]) {
                s.push(e.to);
            }  
        }
    }
}

остовные дуги

получаются непосредственно при поиске в глубину, образуют дерево (или
в общем случае лес), на рисунке обозначены пунктиром;

прямые дуги

соединяют предка и потомка в остовном пути, на рисунке обозначены
буквой F;

обратные дуги

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

перекрёстные дуги

все остальные дуги, на рисунке обозначены буквой C.

bool visited[N] = {false, ... };   // массив флагов посещённых вершин
edge edges[M];                     // массив рёбер
queue<vertex_t> q;                 // очередь

// процедура поиска
void wide_search(vertex_t v0) {

    q.push(v0);

    while(!q.empty()) {
        vertex_t v = q.pop();

        if(visited[v]) continue; // пропустить посещённую вершину
        visited[v] = true;       // отметить вершину как посещённую      
        ...                      // сделать с вершиной что-то
   
        for(size_t i = 0; i < M; i++) {
            edge e = edges[i];
            if(e.from == v && !visited[e.to])
               q.push(e.to);
        }
    }
}