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

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

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

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

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

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

Утверждение. ЕслиА– матрица смежности графа, то элементматрицыА^правен числу маршрутов длинып, соединяющих вершины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 -соединение

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

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