Page 87 - 4128

2 Упорядкуємо рядки матриці Т , для чого побудуємо
матрицю М таким чином. У перший рядок матриці М
помістимо пару (,) з найбільшою вагою р(,). У нашому
випадку (,) = (2,3), р(2,3)= 3. Зі всіх пар, що мають загальний
компонент з парою (,) вибирається пара (,) з найбільшою
вагою і заноситься в другий рядок матриці М . Ясно, що
{,}{,}0. Потім зі всіх пар, що мають загальний компонент
хоча б з однією з внесених вже в матрицю М пара вибирається
пара з найбільшою вагою і заноситься в матрицю М і т.д.. У
разі рівності вагів пар обчислюються суми вагів компонентів пар
(вагою р() компоненту  називається число появ  у матриці
Т ) і в матрицю М заноситься пара з найбільшою сумою вагів.
У даному автоматі на друге місце вслід за парою (2,3)
претендують пари: (1,2) з р(1,2)= 2; (3,4) з р(3,4)= 2, (3,5) з р(3,5)=
2.
Для визначення того, яка пара займе друге місце в матриці
М знаходимо вагу компонентів пар:
р(1)= 3 р(2)= 3 р(1)+ р(2)= 6
р(3)= 4 р(4)= 2 р(3)+ р(4)= 6
р(3)= 4 р(5)= 2 р(3)+ р(5)= 6
В даному випадку для всіх пар співпадають і їх вага і вага
їх компонентів. Тому на друге місце матриці М може бути
поставлена будь-яка з пар (1,2), (3,4), (3,5). Але тоді на 3-у і 4-у
будуть інші дві. Виконавши впорядковування всіх пар, одержимо
матрицю М у вигляді:
i j p(i,j)
2 3 3
1 2 2
M = 3 4 2
3 5 2
1 3 1
1 5 1
2 4 1

86