Abstract: Работа посвящена исследованию систем алгебраических уравнений над конечными обыкновенными графами. Исследование совместности и решение систем уравнений над графами тесно связано с решением таких сложных в вычислительном отношении комбинаторных задач на графах, как задача об изоморфном подграфе и задача о доминирующем множестве вершин. К исследованию систем уравнений над графами могут быть сведены многие имеющие большое практическое значение комбинаторные задачи на графах, такие, например, как задача о наибольшем независимом множестве вершин графа, задача о наибольшей клике в графе, задача о гамильтоновом цикле и другие. Рассматривается два класса систем уравнений над произвольными конечными обыкновенными графами: бескоэффициентные системы уравнений, в запись которых не входят константы; системы уравнений диофантовых языков, т. е. таких языков, в которых множество констант совпадает с множеством вершин графа. Основной целью работы является формулировка необходимых, а также достаточных условий совместности систем уравнений над графами. Эти условия в дальнейшем могут быть использованы в алгоритмах исследования совместности систем уравнений над графами.

Cite: Ильев А.В. , Ильев В.П.
Условия совместности систем уравнений над графами
In compilation Проблемы машиноведения : материалы II Международной научно-технической конференции (Россия, Омск, 27–28 февраля 2018 г.). – Изд-во ОмГТУ., 2018. – C.278–281. – ISBN 978-5-8149-2600-5.

Identifiers: No identifiers

Citing: Пока нет цитирований