Алгоритм перебора с возвратами, реализованный рекурсивной процедурой find(path) исключает зацикливание (каждый город на пути встречается только один раз), что позволяет исходный граф рассматривать как дерево. Какие утверждения справедливы для графов, перебора с возвратом, и связанных с ними деревьев вариантов?
(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
для всякого графа можно построить остовное дерево, удалив часть узлов графа.
единственное отличие алгоритма перебора от обхода дерева состоит в том, что алгоритм перебора останавливается в узле, где выполняется условие поиска(Верный ответ)
для всякого графа можно построить остовное дерево, удалив часть дуг графа(Верный ответ)
алгоритм перебора с возвратами сводится к инфиксному обходу дерева вариантов
граф без циклов является деревом(Верный ответ)
алгоритм перебора с возвратами сводится к префиксному обходу дерева вариантов(Верный ответ)
алгоритм перебора с возвратами сводится к постфиксному обходу дерева вариантов