Пусть{М} — множество матриц инцидентности всех примеров класса{и} и только их. Через M(uOj) обозначим матрицу инцидентности графа примера сOj (в дальнейшем фразу матрица инцидентности графа примера сOj будем заменять фразой матрица примера uoj).
Теорема. М({оо}) = • M(uOj), где суммирование в указанном выше смысле выполняется по всем примерам ио3 из класса{и?}.
Доказательство. Пусть оо — опорный пример. Тогда, в соответствии с определением, он (и все примеры, ему эквивалентные) порождают последовательный маршрут. Если иных примеров нет, то М = М(оо) и М(оо) является субматрицей матрицы М.
Если — пример, порождающий (по отношению к опорному примеру) параллельный маршрут, то, с одной стороны, М = М(и?) + М(iu>i), с другой — матрица графа параллельного маршрута окажется субматрицей матрицы М. Легко видеть, что действуя таким образом и далее, можно доказать теорему полностью.
Из теоремы следует, что если некоторый пример сам по себе или в паре с опорным примером порождает некоторый маршрут в графе, то, с одной стороны, матрица этого примера является субматрицей описания класса, с другой — матрица инцидентности порождённого примером маршрута оказывается субматрицей матрицы описания класса. Эта теорема, по-существу, обосновывает корректность процедуры построения описания класса.
Покажем теперь, что какой бы мы ни взяли пример из класса, он порождает один из маршрутов, определённых выше. Пусть M(iv) — матрица описания некоторого класса эквивалентности{(*}.
Теорема. Для любого и;, если ио Е{и}, и;| = М(ил).
Доказательство. Пусть S — симметрическая группа, действующая на множестве операторов из О. Будем полагать, что на О задан линейный порядок, и обозначим множество О с линейным порядком через О. Выделим в S следующие подгруппы подстановок: G1 — тождественная подгруппа, оставляющая все элементы
на своих местах;G2 — подгруппа транспозиций, действующая на множествах из двух смежных операторов (в смысле порядка, заданного на О) и меняющая их местами;остальные элементы остаются при этом неподвижными;подгруппа состоит из подстановок о = Oi/Oj и а= Oj/Oi;оо^1 = <т-1<т = 1;G3 — подгруппа инверсий, меняющая местами два элемента 0{-1 и Ог+i с неподвижным элементом Oi а = Oi-x/Oi+uOi/Oi, а-1 = 0Ш/0Т^,0{/Ог, G4 — подгруппа n-трансляций, заменяющая Ог+А-+1 на Oi+1, 2 на Oi+9, ..., Oij_2k на Oi+k;Oi+2*+1 вновь заменяется на Oi+1, ..., Oi+3k на Oi+k и т.д. п раз;G5 — условная подгруппа, действующая на фрагмент из попарно смежных операторов и заменяющая операторы этого фрагмента некоторыми иными операторами из О.