Так как граф описывает бинарное отношение, то все операции над бинарными отношениями можно трактовать как операции над графами, в том числе и теоретико-множественные операции: дополнение, пересечение, объединение. Дополнение проводится до полного графа и включает в результат все дуги, которых нет в исходном графе.
Рассматриваются специальные «графовые» операции.
Рёберный граф графа G. В нём каждому ребру G сопоставляется вершина, вершины связываются ребром, если в G сопоставленные им ребра инцидентны.
Граф достижимости графа G. В нём множество вершин то же, что в G, и вершины связаны дугой, если в графе G между ними существует путь. В табл. 3.8 и 3.9 приведены матрицы смежности графа дополнения и реберного графа для графа, приведённого на рис.3.15.
Группа операций связана с операциями над матрицами смежности, описывающими граф. Обозначим операцию, сопоставленную матричному умножению для графов G и H, как G×H.
Табл.ица 3.8
Рассмотрим частный случай, когда G=H, т.е. операцию G×G. Обозначим её как G2.
В этом случае получается матрица, (I,j)- я компонента которой вычисляется по формуле, где n =½А½.
Таблица. 3.9
1,2
1,4
2,5
2,4
3,1
3,5
4,3
5,3
1,2
1,4
2,5
2,4
3,1
3,5
4,3
5,3
Результирующая матрица может содержать значения большие, чем 1, т.е. результатом будет мультиграф. В этом графе дуга (i,j) имеет кратность, равную числу путей длины 2 между вершинами аi и aaj в графе G. На рис.3.16 приведён граф G, для которого G2 представлен на рис.3.17. В нём дуга (2,5) имеет кратность 2, так как между вершинами 2 и 5 два пути длины 2– через вершины 1 и 3.
Можно показать, что для графа G3 результатом будет мультиграф, в котором между aai и aaj будет столько дуг, сколько путей длины 3 между этими вершинами в исходном графе.
Значит, если объединить все степени графа G (считая, что G1=G) от 1 до бесконечности, то результатом будет граф достижимости, описанный выше.
Введём ещё одну бинарную операцию над графами, результирующий граф для которой задан на декартовом произведении множеств вершин графов-аргументов.
Пусть G=<A,R> и H=<B,S>. P=GxH, где P=<C,T>, C=AxB, T={((a,b),(R(a),S(b)))}.
Такую операцию называют произведением графов. Рассмотрим эту операцию подробнее на примере. Пусть G и Н имеют вид рис. 3.18 и 3.19. Произведение этих графов приведено на рис.3.20, его матрица записана в табл.3.10.
Матрица произведения может быть получена по такому правилу. Запишем матрицу одного. из сомножителей, затем в ней каждую клетку заменим на матрицу, размер которой совпадает с размером матрицы второго графа, а содержание равно пустой матрице, если соответствующий элемент матрицы первого графа равен 0, или совпадает с содержимым матрицы второго графа, если элемент равен 1. Такие матрицы получили название правильные клеточные матрицы.
Табл. ица 3.10
1aa
1b
2aa
2b
3aa
3b
1aa
1b
2aa
2b
3aa
3b
Семантика операции. Пусть имеется два блока, составляющие систему, функционирующую в общем дискретном времени. Каждый блок описан графом, вершины которого сопоставлены с состояниями блока, дуга (i,j) определяет возможный переход блока из состояния i в следующий момент времени. Блоки функционируют независимо и параллельно.
В этом случае возможные состояния системы определяются состояниями блоков (декартовым произведением), а произведению соответствует граф перехода системы во времени. Так, если в примере первый блок находится в состоянии 1, второй в это время находится в состоянии bb, то система находится в состоянии (1,bb) и в следующий момент возможны переходы в состояние (3,aa) или (3,bb).
Задание. Система состоит из двух блоков, функционирующих в общем времени, и в каждый момент времени меняет состояние только один блок (последовательная работа блоков). Определите операцию над графами, описывающими переходы блоков системы, результатом которой является граф переходов системы.
