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

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

  • автор:

10.3.5. Матрица достижимости. Алгоритм Уоршалла

Mатрица достижимости – это квадратная матрица d из n строк и n столбцов, где n количество вершин графа, в которой dij=1, если в графе существует путь от вершины i до вершины j, и dij = 0 в противном случае.

Пример матрицы достижимости для графа, изображенного на рис. 5, приведен на рис. 9.

Рис. 9. Матрица достижимости

Для построения матрицы достижимости используется алгоритм Уоршалла.

В начале алгоритма на основе матрицы смежности выполняется инициализация матрицы достижимости: 1 расставляются для прямых путей между вершинами графа (если a[i][j]!=0, то d[i][j]=1) и для элементов главной диагонали матрицы (d[i][i]=1), остальные элементы заполняются 0. Далее над матрицей достижимости выполняется n итераций, чтобы узнать, можно ли достигнуть из i-вершины j-вершину через k-вершину. Если пары вершин i, k и k, j связаны, то вершина j достижима из вершины i.

Текст функции, реализующей алгоритм Уоршалла:

void Warshall(int d[ ][size], int a[ ][size ], int n)

/* d –матрица достижимости, а – матрица смежности, n – количество вершин графа, size глобальная константа */

int i, j, k; //номера вершин

//Начальное заполнение матрицы достижимости

//Выполнение n итераций над матрицей

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

bool path (int i, int j, int a[ ][size ], int n)

// i и j – номера вершин

// а – матрица смежности

// n – количество вершин графа

// size – глобальная константа (максимальное количество вершин)

int d[size][size]; // матрица достижимости

Дополнительные сведения об алгоритмах выполнения операций над графом, таких как поиск в глубину, поиск сильно связанной компоненты, проверка ацикличности графа, вывода кратчайшего пути, приведены в [4-6].

Библиографический список

  1. Павловская Т.А. С/ С++. Программирование на языке высокого уровня. – СПб.: Питер, 2002
  2. Дейтл Х.М., Дейтл П.Дж. Как программировать на С++. – М.: Бином -2000
  3. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001
  4. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001
  5. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах. Часть 5. – М.: ДиаСофт, 2002
  6. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Бином, 2006

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

Author24 — интернет-сервис помощи студентам

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

В интернете алгоритм представлен мутновато, я не смог разобраться

Если можно, покажите на конкретном примере

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

По заданной матрице смежности ребер неориентированного графа построить матрицу
По заданной матрице смежности ребер неориентированного графа построить матрицу B, у которой.

Построить матрицу весов по матрице смежности
Дано задание построить матрицу весов неориентированного по матрице смежности по правилу.

Изобразите матрицу достижимости графа

Составить матрицу инцидентности, достижимости и список ребер для графа
Помогите пожалуйста Составить матрицу инцидентности, достижимости и список ребер для графа:

204 / 141 / 57
Регистрация: 25.12.2014
Сообщений: 446

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

204 / 141 / 57
Регистрация: 25.12.2014
Сообщений: 446

Лучший ответ

Сообщение было отмечено grigandal1580 как решение

Решение

Вот на этом рисунке показан процесс для работы с нулями и единицами в матрице смежности.

1)Ищем в матрице единицу — пусть нашли ее в i-й строке и j-м столбце (на рисунке 1 выделена красным).
2)Из j-й строки копируем все единицы в i-ю строку (синие стрелки на рисунке), скопированные единицы выделены зеленым. Если в i-й строке на этом месте и так была 1, то ничего не изменится, а если там был 0, то в матрице появится новая единица.
3)продолжаем шаги 1, 2 пока в матрице появляются новые единицы. Если в шаге 1 невозможно найти единичный элемент, такой чтобы при выполнении шага 2 появились новые единицы, то стоп.
В результате этого процесса из матрицы смежности получится матрица достижимости.

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

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

3 фев 2016 в 22:03
Я тоже так думал, но здесь тоже получают матрицу, в которой есть нулевые диагональные элементы.
4 фев 2016 в 5:36

видимо это вопрос соглашений, считать ли пути нулевой длины валидными путями. В примере на atomlex считают пути нулевой длины валидными, там берут дизъюнкцию A^0 V A^1 V . V A^ (N — 1), где (A^ 0 = E). На википедии же A^1 V . V A^N. Вроде так.

4 фев 2016 в 9:38

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Никакой ошибки нет.

введите сюда описание изображения

Посмотрите внимательно на граф: Из узлов 2 3 4 можно добраться «из себя в себя» по некоторому пути. А из узлов 1 и 5 «в себя» не доберёшься. Поэтому такая матрица и получается:

0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 

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

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

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

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

Утверждение. ЕслиА– матрица смежности графаМатрица достижимости, то элементМатрица достижимостиматрицыА п равен числу маршрутов длинып, соединяющих вершиныvi иvjграфаG. Доказательство.Методом математической индукции по числуп. База индукции.Прип= 1 утверждение верно, так как всякое ребро графаG– это маршрут длины 1. Индуктивное предположение.Пусть утверждение справедливо для всехnk. Индуктивный переход.Рассмотрим матрицуА k +1 . В нейМатрица достижимости. В силу индуктивного предположения произведение Матрица достижимостиесть число маршрутов длиныk+ 1, соединяющих вершинуvi с вершинойvjс предпоследней вершиной всех таких маршрутовvm. Значит, суммаМатрица достижимостидействительно равна числу маршрутов длинk+ 1, соединяющих вершинуvi с вершинойvj. Следствие.ПустьМатрица достижимости– связный граф срвершинами. Тогда любые две вершины графаМатрица достижимостиможно соединить простой цепью. Но в простой цепи не может быть более (р1) ребер. Следовательно, все элементы матрицыМатрица достижимостиотличны от нуля. Ясно, что верно и обратное утверждение. В некоторых случаях при вычислениях степеней матрицы Аи матрицыСважно знать не число соответствующих маршрутов, а только есть ли в графе эти маршруты или нет. Об этом говорит сайт https://intellect.icu . Тогда при вычислении элементов матрицА 2 ,А 3 , … ,А р -1 вместо обычного сложения используют операцию, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицыА,А 2 ,А 3 , …,A p 1 ,Cсостоят только из нулей и единиц. Полученная таким образом матрица Сназываетсяматрицей достижимостиграфаG. ГрафGсвязен тогда и только тогда, когда каждый элемент матрицы достижимости равен 1 (р3).

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

Случай орграфа ничем не отличается от случая неориентированного графа. Если G– орграф ср вершинами иА– его матрица смежности, то элементМатрица достижимостиматрицыА п равен числу ориентированных маршрутов длинып, соединяющих вершинуvi с вершинойvj. +Граф G сильно связен тогда и только тогда, когда каждый элемент его матрицы достижимостиМатрица достижимостиравен 1.

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

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

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

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

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

Пример

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

Граф

Рассмотрим простой связный ориентированный граф Матрица достижимости. Он имеет матрицу смежности Матрица достижимостивида:  \mathbf E = \begin0&1&1&0 \\ 0&0&0&0 \\ 0&1&0&1 \\ 0&0&1&0 \end Найдем булевы степени этой матрицы Матрица достижимости, Матрица достижимости, Матрица достижимости:  \mathbf<E^2>= \begin 0&1&0&1 \\ 0&0&0&0 \\ 0&0&1&0 \\ 0&1&0&1 \end » />, <img decoding=Таким образом, из вершины Матрица достижимостиможно добраться в любую другую. При использовании же алгебраических операций получится матрица Матрица достижимостиОна показывает количество путей длины от 1 до 4 между вершинами орграфа.

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

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

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

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

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

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

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

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

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

Пример

Рассмотрим тот же граф, что и ранее. Его матрица достижимости: Матрица достижимостиИз нее получаем матрицу сильной связности: Матрица достижимостиВершины 3 и 4 сильно связаны друг с другом и сами с собой.

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

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

#include #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 for (int i=0;ifor (int j=0;j> Adj[i][j]; > > void Warshall::TransClose() //Вычисление матрицы достижимости. < //Инициализация матрицы Path матрицей смежностей Adj. for (int i=0;ifor (int j=0;j//Нахождение следующих значений матрицы Path. for (int k=0;kfor (i=0;iif (Path[i][k]==1) for (int j=0;j void Warshall::Vyvod() //Вывод матрицы достижимости. < cout for (int i=0;ifor (int j=0;j > void main()

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

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

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

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

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

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

Добавить комментарий

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