Алгоритмы решения систем уравнений над различными классами конечных графов

Целью работы является исследование и решение конечных систем уравнений над конечными неориентированными графами. Уравнениями над графами называются атомарные формулы языка ${\rm L}$, состоящего из множества констант (вершин графа), бинарного предиката смежности вершин и предиката равенства. Доказано, что задача проверки совместности системы уравнений $S$ от $k$ переменных над произвольным обыкновенным $n$-вершинным графом $\Gamma$ является $\mathcal{NP}$-полной. Подсчитана вычислительная сложность процедуры проверки совместности системы уравнений $S$ над обыкновенным графом $\Gamma$ и процедуры нахождения общего решения этой системы. Вычислительная сложность алгоритма решения системы уравнений $S$ от $k$ переменных над произвольным обыкновенным $n$-вершинным графом $\Gamma$, включающего эти процедуры, составляет $O(k^2n^{k/2+1}(k+n)^2)$ при ${n \geq 3}$. Выделены полиномиально разрешимые случаи: системы уравнений над деревьями, лесами, двудольными и полными двудольными графами, для решения которых предложены полиномиальные алгоритмы трудоёмкости $O(k^2n(k+n)^2)$.