Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 26

G — простой неориентированный граф. Некоторые вершины графа G имеют нечетную степень. Добавьте узел v к G и сделайте его смежным с каждой вершиной нечетной степени G. Результирующий граф обязательно будет
(А) регулярный
(B) Завершено
(С) гамильтониан
(D) Эйлер

Ответ: (D)
Пояснение: для того чтобы граф был графом Эйлера, все степени должны быть четными для всех узлов. В любом графе все узлы нечетной степени связаны с узлом.
И число вершин нечетной степени должно быть четным.
Таким образом, степень этого нового узла будет четной, и поскольку между этим новым узлом и всеми остальными узлами нечетной степени образуется новое ребро, следовательно, здесь не существует ни одного узла со степенью нечетного

=> График Эйлера
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2008 | Вопрос 26

0.00 (0%) 0 votes