Разбиение графа на подграфы

Операция разбиения графа позволяет в ряде случаев существенно упростить задачу анализа сложной системы, представленной в виде графа. Иногда такое разбиение само является целью анализа графовой модели системы. Изложение методики разбиения будет вестись, как и ранее, на основе множественного подхода (использования операций теории множеств – пп. 1.2,1.3) и матричного подхода (использования теории матриц – пп. 1.4, 1.5).

Определение существенных вершин

на пути из вершины x_i в вершину x_j

Так как RM(x_i), определяемое формулой (2.5), является множеством вершин, достижимых из x_i, а QM{x_j}, определяемое формулой (2.6), является множеством вершин, из которых можно достигнуть x_j, то их пересечение RM(x_i) Ç QM(x_j) определяет множество таких вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от x_i к x_j. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин x_i и x_j. Все остальные вершины x_k Ï Ï RM(x_i) Ç QM(x_i) называются несущественными или избыточными, поскольку их удаление не влияет на пути от x_i к x_j.