2004-gre-cs-practice-book.pdf/Q58

Ссылки сюда (2) →

Вопрос: Q58-4c9f66

Эйлеров цикл в неориентированном графе — цикл, в которой каждое ребро графа встречается ровно один раз.

В каком из неориентированных графов он должен быть?

1. Полный граф с 12 вершинами
2. Полный граф с 13 вершинами
3. Дерево с 13 вершинами

Ответы

• Только 1
• Правильный ответ: Только 2
• Только 3
• 1 и 2
• 1 и 3

Объяснение

Исходники — вопрос 58 на 39 странице книги «2004-gre-cs-practice-book.pdf»

• У нас циклы Эйлера и необходимые и достаточные условия разбираются в теме Приближенный_алгоритм_для_метрической_задачи_коммивояжера, необходимы и достаточны четные степени вершин («вошел → сжег входной мост → вышел»).
• Дерево отпадает сразу.
• Полный на 12 вершин — тоже, там степень 11.
• Полный на 13 — норм, там степени 12.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.