Математическая энциклопедия - трансверсальная система

трансверсальная схема, Т- система,система T0(m, t )множеств, определяемая для заданной совокупности тпопарно непересекающихся конечных множеств S1, . . ., Sm, каждое из к-рых имеет мощность t. А именно: Т. с. Т 0( т, t )есть система из t² множеств Y1, . . ., (блоков, или трансверсалей), содержащих каждое тэлементов и таких, что:

В Т. с. любые два элемента и встречаются вместе ровно в одном блоке. Существование Т. с. T0(m, t )эквивалентно существованию ортогональной таблицы ОА (t, т).

Т. с. используются в рекурсивных методах построения блок-схем.

Множество из tтрансверсалей в Т 0( т, t )наз. параллельным, если никакие две из них не пересекаются. Если Т. с. Т 0( т, t )содержит е(или более) параллельных множеств, то она обозначается Т е( т, t).

Нек-рые из основных свойств Т. с.:

а) если существуют Т d( т, s )и Te(m, t), то существует и Tde(m, st);б) Tt(m-1, t)существует тогда и только тогда, когда существует Т 0( т, t);в) если . и s таковы, что существуют Ts(m, t )и Т 0( т, s), то существует Ts2(m, st).

Лит.:[1] Холл М., Комбинаторика, пер. с англ., М., 1970; [2] Наnani Н., лAnn. Math. Stat.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985