6.6. Поиск контуров и путей по матрице изоморфности

6

Матрица изоморфности D

Алгоритм идентификации контуров следующий:

1. Просмотреть строки матрицы. Для i-й строки просмотреть элементы до обнаружения отрицательного элемента D_{i j} <0. Запомнить номер строки и значение элемента D_{i j}.

2. Найти строки в матрице содержащие элемента D _{k l} == - D_{i j}. Для каждой найденной строки выполнить пп. 1, до тех пор пока в найденной последовательности повторно не вертится уже обнаруженная дуга, или программе не удастся обнаружить новую дугу, выходящую из этой вершины.

Пример для графа, представленного на рис. 6.5.

1. В 0-й строке нашел D[0][0]= -1 ;

2. Нашел D[1][1]= 1 ;

3. Â 1-é строке нашел новый отрицательный элемент D[1][0] = -2 ;

4. Нашел D[2][1]= 2 ;

5. В 2-й строке нашел новый отрицательный элемент D[2][0] = -3 ;

6. Нашел D[3][0] = 3 ;

7. Â 3-é строке нашел новый отрицательный элемент D[3][2] = -4 ;

8. Нашел D[4][0]= 4 ;

9. Â 4-é строке нашел новые отрицательные элементы D[4][1] = -5, D[4][1] = -6, D[4][1] = -9. Необходимо разветвить поиск ;

10. Нашел D[3][1]= 5 ;

11. Â 3-é строке нашел отрицательный элемент D[3][2] = -4. Этот элемент уже был в цепочки поиска. Поиск по этой ветки прекращен. Возвращаемся в пп.9 ;

12. Нашел D[1][2]= 6 ;

13. Â 1-é строке нашел отрицательный элемент D[1][0] = -2. Этот элемент уже был в цепочки поиска. Поиск по этой ветки прекращен. Возвращаемся в пп.9 ;

14. Нашел D[6][0]= 9 ;

15. Â 6-é строке нашел новый отрицательный элемент D[6][1] = -7 ;

16. Нашел D[0][1]= 7 ;

17. В 0-й строке нашел D[0][0]= -1. Этот элемент уже был в цепочки поиска. Поиск по этой ветки прекращен.

18. Новых отрицательных элементов в матрице не осталось поиск прекращен.

После завершения поиска имеем:

По данным этого списка составляем контура.

Обычно в литературе указывается на высокую эффективность данного алгоритма. Он действительно выглядит очень просто и наглядно. Однако при его реализации придется организовывать разветвление работы алгоритма. Это можно сделать либо через рекурсию, либо организовать запоминание дерева перебора и незавершенные точки перебора. Что приводит к значительным затратам ресурсов ЭВМ, не учитывающихся большинством авторов анализирующих эффективность данного алгоритма.