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

А. М. Магомедов^a, С. А. Лавренченко<sup>b

a</sup> Дагестанский государственный университет, г. Махачкала
^b Российский государственный университет туризма и сервиса, Московская обл., Пушкинский р-н, пос. Черкизово

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

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

УДК: 519.1

Поступила в редакцию: 07.03.2020
Исправленный вариант: 21.05.2020
Принята в печать: 22.05.2020

DOI: 10.31029/demr.10.7