База ответов ИНТУИТ

Графы и алгоритмы

<<- Назад к вопросам

Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?

(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
если в качестве стартовой выбрана концевая вершина, то будет построен эйлеров путь. (Верный ответ)
будет построен маршрут, не проходящий через некоторые ребра
если в качестве стартовой выбрана не концевая вершина, то будет построена последовательность вершин, не являющаяся маршрутом(Верный ответ)
будет построен маршрут, проходящий через некоторые ребра дважды
Похожие вопросы
К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).
Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?
Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Пусть (E,\Phi ) - матроид и на множестве E задана весовая функция w с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества E упорядочиваются не по убыванию, а по возрастанию весов?
Как может измениться цикломатическое число при добавлении к графу нового ребра?
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?