Алгоритмы решения систем уравнений над различными классами конечных графов | Прикладная дискретная математика. 2021. № 53. DOI: 10.17223/20710410/53/6

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