УДК 517.6 Д 73 К.А. Дридгер Оренбургский государственный педагогический университет АЛГЕБРАИЧЕСКИЙ МЕТОД НАХОЖДЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА В ГРАФАХ Современные компьютерные технологии позволяют находить все новые методы решения задач, связанных с представлением программ на основе теоретико-графовых алгоритмов. <...> Широкое применение графов связано с тем, что они являются естественным средством объяснения сложных ситуаций на интуитивном уровне, что в настоящее время, очевидно, обусловливает возрастающий научный интерес к методам обработки графов. <...> Многие программные системы (системы принятия решения, системы автоматизации проектирования), как отмечают В.Н. Касьянов и В.А. Евстигнеев, включают элементы обработки графовых объектов и теоретико-графовых моделей. <...> Сегодня теория графов располагает достаточно обширным кругом методов нахождения гамильтонова цикла в графах (алгебраический метод, метод перебора, мультицепной метод). <...> Задачи, в которых требуется определить содержит ли граф гамильтонов цикл или нет, в основном относятся к проблеме упорядочения и планирования операций. <...> Наиболее яркими представителями класса задач теории графов по нахождению гамильтонова цикла являются следующие: 1) в данном ориентированном графе G требуется найти гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл; 2) в данном полном ориентированном графе G, дугам которого приписаны произвольные веса, найти такой гамильтонов цикл, который имеет наименьший общий вес (задача коммивояжера). <...> В современной науке алгебраический метод, позволяющий ответить на вопрос, существует или нет в графе гамильтонов цикл, больше представляет теоретический интерес, чем практический. <...> Так, алгебраические критерии НэшаУильямса, Оре, Поша слишком общие и не могут быть применены на практике для произвольных графов. <...> Имеющиеся на данный момент алгебраические методы определения гамильтонова цикла не пригодны в задачах <...>