Графы, сети и схемы как структурные модели управляющих систем; матрицы достижимости

Граф задаёт вершины и связи, но для управляющих систем этого недостаточно. (p,q)-сеть — граф с выделенными упорядоченными входами и выходами. Она позволяет описать, какие выходы достижимы из каких входов.¹

Матрица достижимости \(M\in B^{p,q}\) определяется правилом M[i,j]=1 тогда и только тогда, когда j-й выход достижим из i-го входа. Если входная и выходная выборки совпадают, M рефлексивна и транзитивна. Для рефлексивной булевой матрицы транзитивность эквивалентна равенству M²=M.¹

Что важно запомнить

Граф описывает вершины и рёбра. Сеть дополнительно фиксирует входные и выходные полюса.
Достижимость означает наличие ориентированной цепи от одной вершины к другой, причём вершина достижима сама из себя.
M[i,j]=1 ⇔ выход j достижим из входа i.
В булевом произведении матриц сложение заменяется дизъюнкцией, а умножение — конъюнкцией.

Граф как основа структурной модели

В ориентированном графе вершина u достижима из v, если u=v или существует ориентированная цепь из v в u. Отношение достижимости всегда рефлексивно и транзитивно. В ориентированном ациклическом графе оно становится частичным порядком. Такие графы естественно описывают структуры вычисления без обратных циклов.¹

Сеть

Сеть G=(G;V′;V″) состоит из графа G, входной выборки V′ длины p и выходной выборки V″ длины q. Элементы этих выборок называют входными и выходными полюсами. Остальные вершины считаются внутренними. Выделение полюсов превращает абстрактный граф в объект, у которого можно обсуждать передачу информации от заданных входов к заданным выходам.¹

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

Для V′=(v′1,…,v′p) и V″=(v″1,…,v″q) матрица M имеет размер p×q и определяется формулой

M[i,j]=1, если v″j достижима из v′i, и M[i,j]=0 в противном случае. ¹

Если V′=V″, матрица рефлексивна и транзитивна. Для рефлексивной булевой матрицы транзитивность равносильна M²=M, где произведение вычисляется в булевой алгебре. Это матричный способ зафиксировать замыкание отношения достижимости.¹

От сети к схеме

Чтобы получить модель управляющей системы, сеть дополняют метками и правилами функционирования. Входам сопоставляют входные переменные, а внутренним вершинам или элементам — функции преобразования. Тогда структура графа задаёт связи между операциями, а вычисленные в выходах значения образуют реализуемую систему функций. Так графы и сети становятся структурной основой формул, схем из функциональных элементов и других классов управляющих систем.¹

Пример простыми словами

Пусть у сети два входа a1,a2 и один выход z. Если из каждого входа существует ориентированный путь к z, матрица достижимости имеет два элемента в единственном столбце, и оба равны 1. Если путь от a2 к z удалить, второй элемент станет 0. Матрица фиксирует сам факт достижимости, а не число путей и не выполняемую логическую функцию.

Частые ошибки

Путать матрицу достижимости с матрицей смежности. Первая учитывает наличие пути любой длины, а не только одного ребра.
Менять местами индексы: строка соответствует входу, столбец — выходу.
Использовать обычное арифметическое умножение в равенстве M²=M. Здесь произведение булево.

Другие вопросы

Источники

1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 2, §1, МГУ, факультет ВМК