2. Упорядочим
строки матрицы ,
для чего построим матрицу следующим образом. В первую строку матрицы поместим пару (a,b) с наибольшим
весом р(a,b). В нашем случае (a,b) = (2,3), р(2,3) = 3. Из всех пар, имеющих общий компонент с
парой (a,b) выбирается пара (g,d) с наибольшим весом и заносится во вторую строку матрицы . Ясно, что {a,b}×{g,d}¹0. Затем из всех
пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с
наибольшим весом и заносится в матрицу и т.д.. В случае равенства весов пар
вычисляются суммы весов компонентов пар (весом р(a) компонента a называется число
появлений a в матрице )
и в матрицу заносится
пара с наибольшей суммой весов. В рассматриваемом автомате на второе место
вслед за парой (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-м будут
остальные две. Выполнив упорядочивание всех пар, получим матрицу в виде: