Математика \ Специальные главы математики

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

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

Матрица достижимостей состоит из элементов .

, если вершина достижима из и в противном случае.

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

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

Матрица контрдостижимостей может быть получена транспонированием матрицы .

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

c d

Матрица смежности имеет вид:

Находим :

Поскольку следует искать и вычислять :

Т.к. , то процесс закончен, и рассчитываем матрицу достижимостей:

Матрицу контрдостижимостей находим путем транспонирования матрицы достижимостей:

Для определения множества вершин достижимых из рассматриваем строку матрицы : 00111. Единичные элементы соответствуют вершинам, которые достигаются из : , , .

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

Известен простой алгоритм определения матрицы достижимостей :

Шаг 1. Задаем номер строки и осуществляем переход к шагу 2.

Шаг 2. Записываем строка матрицы . В ней помечаем единицей элементы, для которых существует путь из вершины длиной 1. (Это строка матрицы смежности).

Шаг 3. Отмечаем элемент строки матрицы равный 1, определяем номер соответствующего ему столбца. Выбираем строку матрицы смежности и дополняем строку матрицы единичными элементами строки.

Шаг4. Если остаток строки заполнен единицами, либо все 1 первой строки помечены, то переход к шагу 5. Если же в первой строке есть еще неотмеченные элементы, то переходим к шагу 3.

Шаг 5. Если не все строки обработаны, то увеличиваем номер строки на единицу и переходим к шагу 2, иначе – шаг 6.

Шаг 6. В полученной матрице элементы главной диагонали заполняются единицами.

Попробуйте проследить работу этого алгоритма для предыдущего примера.

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

b c

d e f

Этот граф не связный, т.к. нет некоторых цепей, например из в , из в и т. д.

Любой граф можно разбить на подграфы, каждый из которых является связным. Минимальное число таких подграфов, называется числом связности графа. Примером области применения этого понятия являются вычислительные сети.

Пусть граф задан множеством вершин и множеством ребер . При определении связности можно воспользоваться следующим алгоритмом:

Шаг 1. Определить множество . Задать значение коэффициенту связности .