Теория приближений

Дагестанские Электронные Математические Известия: Выпуск №13 (2020)


Решение головоломок методом О. Оре

УДК: 519.1

Страницы: 22 - 30


В ряде случаев представление головоломки в терминах теории графов позволяет рассматривать ее решение как поиск пути в связном ориентированном ациклическом графе. Это утверждение из монографии О. Оре по теории графов получило в статье подтверждение на задачах принципиально различной природы. В каждом случае задаче сопоставляется связный ориентированный ациклический граф, узлы которого соответствуют некоторым <<состояниям>>, а дуги служат для указания переходов между состояниями; затем показывается, что решение задачи сводится к поиску пути между узлами построенного графа.


Ключевые слова: алгоритм, дуга, узел, ориентированный граф, путь.




В содержание выпуска

Скачать полный текст