Графы. Матрицы связности. Утверждение о матрицах связности, матрицы достижимости, матрицы сильной связности.
Матрица достижимости простого ориентированого графа G = (V,E) — бинарная матрица замыкания по транзитивности отношения E (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.
Способы построения матрицы достижимости
Перемножение матриц
Пусть дан простой граф G = (V,E), матрица смежности которого есть , где . Матрица смежности даёт информацию о всех путяхдлины 1 (то есть, рёбрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения E с самим собой:
.
По определению, матрица композиции отношений есть , где — конъюнкция, а — дизъюнкция.
После нахождения матриц композиций для всех k, будет получена информация о всех путях длины от 1 до n. Таким образом, матрица есть искомая матрица достижимости.
Матрица сильной связности
Матрица сильной связности простого орграфа — бинарная матрица, содержащая информацию обо всех сильно связанных вершинах в орграфе. Матрица сильной связности симметрична. У сильно связного графа такая матрица заполнена единицами.
Построение матрицы сильной связности
Матрица сильной связности может быть построена из матрицы достижимости. Пусть — матрица достижимости орграфа G = (V,E). Тогда матрица сильной связности состоит из элементов .
Графы. Выделение компонент связности. Алгоритм нахождения числа компонент сильной связности и матрицы смежности этих компонент.
Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа | |
| |
| Разделим все вершины графа на три разновидности: Вершины, про которые ничего не известно; Вершины, про которые известно, что они могут быть достигнуты из начальной вершины и которые не были обработаны. Вершины, про которые известно, что они могут быть достигнуты из начальной вершины и которые были обработаны. |
Выделение связной компоненты графа. | |
| |
|
В этом алгоритме три этапа - первоначальная разметка, распространение разметки и формирование результата. |
1. Первоначальная разметка | |
| |
|
Пометим все вершины первым маркером - нам про них ничего не известно Выберем любую вершину (например первую (или нулевую)), пометим ее вторым маркером, ведь она может быть достигнута сама из себя. |
2. Разметка соседних вершин | |
| |
|
Если нет вершин, помеченных вторым маркером - переходим к третьему этапу. Выберем любую вершину, помеченную вторым маркером. Пометим ее третьим маркером. Все вершины, соседние с данной и помеченные первым маркером, пометим вторым маркером. Повторим этот пункт с начала. |
3. Завершение работы | |
| |
|
Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные третьим маркером, в отдельный массив. Если нужно получить список вершин, не входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные первым маркером в отдельный массив и возвращаем полученный массив. Если нужно просто проверить граф на связность, то считаем вершины, помеченные первым маркером, и сравниваем получившееся число с нулем. Если число вершин, помеченные первым маркером, равно нулю, то граф связный. |
Компоненты сильной связности ориентированного графа
С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.
Cоставляем матрицу смежности A(D) размерности (n− количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин , из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины vi и входящая в vj, то элемент матрицы смежности, стоящий на пересечении i-той строки и j-того столбца равен 1, иначе – 0.).
Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.
Алгоритм выделения компонент сильной связности
1. Присваиваем p=1 (p − количество компонент связности), .
2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицыSp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.
3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу какSp+1, присваиваем p=p+1 и переходим к п. 2.
Yandex.RTB R-A-252273-3
- Универсальное множество: Универсальное множество (универсум) — множество, содержащее все мыслимые объекты. Упорядоченное множество — множество, на котором задано отношение порядка.
- Множество. Способы задания множеств (перечислением или списком, порождающей процедурой, описанием характеристического свойства). Привести примеры.
- Объединение более чем двух множеств. Пусть дано семейство множеств Тогда его объединением называется множество, состоящее из всех элементов всех множеств семейства:
- Алгебра множеств. Законы алгебры множеств. Доказать один из законов алгебры множеств.
- Множество. Мощность множества. Нахождение мощности объединения множеств (для двух множеств, для трех множеств, для n-множеств). Привести пример.
- Векторы. Прямое произведение множеств. Мощности прямого произведения множеств.
- Отношения. Основные понятия отношений (отношения; унарные, бинарные, n-местные отношения)
- Отношения. Бинарные отношения. Основные понятия (определение, обозначения, область определения, область значений, способы задания бинарных отношений). Привести примеры.
- Способы задания бинарных отношений
- Отношения. Свойства бинарных отношений (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность). Привести примеры.
- Переключательные (булевы) функции. Происхождение булевых функций.
- Булевы функции от одного аргумента. (Определение. Все булевы функции от одного аргумента).
- Булевы функции от двух аргументов (Определение булевой функции двух аргументов, тождественный ноль, тождественная единица, конъюнкция, штрих Шеффера, дизъюнкция, стрелка Пирса (функция Вебба)).
- Свойства дизъюнкции, конъюнкции и отрицания (теорема 4.3).
- Свойства эквиваленции, импликации и отрицания (теорема 4.4).
- Выражение одних булевых функций через другие (теорема 4.5).
- Булевы функции от n аргументов (определение, равенство булевых функций, суперпозиция булевых функций). Булевы функции от n переменных
- Булевы функции и формулы алгебры высказываний.
- Нормальные формы булевых функций.
- Применение булевых функций к релейно-контактной схеме. Две основные задачи теории релейно-контактных схем.
- Релейно-контактные схемы в эвм. Двоичный полусумматор. Одноразрядный двоичный сумматор.
- Графы. Основные понятия и определения (вершины, ребра, петли, кратность ребра, псевдограф, мультиграф, граф, орграф, неориентированный граф). Привести примеры.
- Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.
- Графы. Свойства матрицы смежности и инцидентности. Утверждение о числе всех путей (маршрутов) длины k из одной вершины в другую. Утверждение о наличие хотя бы одного контура.
- Графы. Связность. Компоненты связности. (Достижимость вершины, связный (сильно связный орграф) граф, слабо связанный, несвязанный, компонента связности (сильной связности)). Привести примеры.
- Графы. Матрицы связности. Утверждение о матрицах связности, матрицы достижимости, матрицы сильной связности.
- Графы. Поиск путей (маршрутов) с минимальным числом дуг (ребер). Алгоритм фронта волны.
- Графы. Минимальные пути (маршруты) в нагруженных орграфах (графах). Алгоритм Форда-Беллмана.