Параллельный алгоритм решения задачи об изоморфизме графов

В данной работе предлагается параллельный алгоритм решения задачи об изоморфизме графов. Целевым результатом для нас выступает построение подходящей подстановки вершин, либо доказательство отсутствия таковой. Задача решается для неориентированных графов без петель и кратных ребер, допускается, что графы могут быть несвязными. Вопрос о существовании либо отсутствии алгоритма с полиномиальной трудоемкостью в настоящее время является открытым. Следовательно, как и для любой трудоемкой задачи, возникает вопрос об ускорении ее решения за счет распараллеливания алгоритма. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Для решения нашей задачи и проведения численного эксперимента было разработано несколько приложений на языке C#. Целью эксперимента было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. В качестве исходных данных использовались специально сгенерированные случайные регулярные графы с различной степенью вершин. Подробное описание алгоритма и эксперимента, а также полученные результаты также приводятся в работе.