Дискретные модели системного анализа - 30 стр.

UptoLike

Составители:

Рубрика:

Тогда d(P,Q) = d(P’,Q’), поскольку P’ и Q’ можно получить из Р и Q циклическим

сдвигом последовательности {a,b,c,d} на два элемента.

Для формулировки следующей аксиомы введем понятие сегмента

ранжировки. Подмножество S из А называется сегментом ранжировки Р, если

каждый элемент а из A\S находится либо ниже любого элемента из S, либо выше

любого элемента из S. Например, в приведенном выше профиле множества

= {a,b}, S

= {b,c}, S

= {c,d} будут сегментами ранжировки Р. Множество {a,c}

не будет сегментом Р, так как между а и с находится b.

Если S = S (Р) – сегмент Р, то множество ST(P), содержащее все элементы

выше S в ранжировке Р, и множество SB(P), содержащее все элементы ниже S в Р,

тоже являются сегментами Р. Обозначим через Р(S), Р(ST), Р(SB) ранжировки,

полученные из Р

для элементов, входящих в сегменты S , ST , SB соответственно.

Будем говорить, что ранжировки P и Q согласованы вне S, если:

– S – их общий сегмент;

– ST(P) = ST(Q) = ST, SB(P) = SB(Q) = SB;

– P(ST) = Q(ST), P(SB) = Q(SB).

Например, P и Q согласованы вне S = {c,d,e} для следующего профиля:

P Q

c-d