TY  - SER
AU  - Ильев,Артем Викторович
AU  - Ильев, Виктор Петрович
TI  - Алгоритмы решения систем уравнений над различными классами конечных графов
KW  - графы
KW  - системы уравнений
KW  - вычислительная сложность
KW  - статьи в журналах
N1  - Библиогр.: 13 назв
N2  - Целью работы является исследование и решение конечных систем уравнений над конечными неориентированными графами. Уравнениями над графами называются атомарные формулы языка L, состоящего из множества констант (вершин графа), бинарного предиката смежности вершин и предиката равенства. Доказано, что задача проверки совместности системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г является N P -полной. Подсчитана вычислительная сложность процедуры проверки совместности системы уравнений S над обыкновенным графом Г и процедуры нахождения общего решения этой системы. Вычислительная сложность алгоритма решения системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г, включающего эти процедуры, составляет O(k2nk/2+1(k+ n )2) при n @ 3. Выделены полиномиально разрешимые случаи: системы уравнений над деревьями, лесами, двудольными и полными двудольными графами, для решения которых предложены полиномиальные алгоритмы трудоёмкости O(k2n(k + n)2)
UR  - http://vital.lib.tsu.ru/vital/access/manager/Repository/koha:000723365
ER  -