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

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

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

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

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

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

Сеть

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

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

Для \(V'=(v'_1,\ldots,v'_p)\) и \(V''=(v''_1,\ldots,v''_q)\) матрица M имеет размер \(p\times q\) и определяется формулой

\(M[i,j]=1\), если \(v''_j\) достижима из \(v'_i\), и \(M[i,j]=0\) в противном случае. 1

Если \(V'=V''\), матрица рефлексивна и транзитивна. Для рефлексивной булевой матрицы транзитивность равносильна \(M^{2}=M\), где произведение вычисляется в булевой алгебре. Это матричный способ зафиксировать замыкание отношения достижимости.1

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

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

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

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

Частые ошибки
  • Путать матрицу достижимости с матрицей смежности. Первая учитывает наличие пути любой длины, а не только одного ребра.
  • Менять местами индексы: строка соответствует входу, столбец — выходу.
  • Использовать обычное арифметическое умножение в равенстве \(M^{2}=M\). Здесь произведение булево.

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

Источники

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