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

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

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

Рубрика: 

33
P Q
a-b
A\{a,b}
a
b
A\{a,b}
Тогда δ
P,Q
(a,b) = 1 и δ
P,Q
(х,у) = 0 для всех остальных пар, поэтому d(P,Q) = 1.
Таким образом, минимальное положительное расстояние равно единице.
При |A| = 3 расстояния легко вычисляются с помощью фигуры, показанной
на рис.3.1.
Рис.3.1 Фигура для определения расстояний между ранжировками при |A| = 3
Для определения расстояния между двумя произвольными ранжировками P
и Q следует найти на рис
.3.1 кратчайшую цепь из Р в Q и положить расстояние
равным сумме весов ее ребер. Например, расстояние между ранжировками
а b-c
b и a
с
b
a
c
a-b
c
1
1
2
2
1
1
2
1
1
2 2
1 1
1
1
1
1
a
b
c
a
c
b
c
a
b
c
b
a
b
c
a
b
a-c
a
b-c
c
a-b
a-c
b
b-c
a

Страницы