http://npc-news.ru/

Корректность и полнота описаний классов эквивалентности

Пусть {М} — множество матриц инцидентности всех приме­ров класса {и;} и только их. Через 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 — условная подгруппа, действующая на фрагмент из по­парно смежных операторов и заменяющая операторы это­го фрагмента некоторыми иными операторами из О.


Комментарии закрыты.