Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 23

Какой из следующих графиков имеет эйлерову схему?
(A) Любой k-регулярный граф, где k — четное число.
(B) Полный граф на 90 вершинах
(C) дополнение цикла на 25 вершин
(D) Ничего из вышеперечисленного

Ответ: (с)
Объяснение: Граф имеет эйлерову схему, если выполняются следующие условия.

… .A) Все вершины с ненулевой степенью связны. Мы не заботимся о вершинах с нулевой степенью, потому что они не принадлежат циклу Эйлера или Path (мы рассматриваем только все ребра).
… .B) Все вершины имеют четную степень.

Давайте проанализируем все варианты.
А) Любой k-регулярный граф, где k — четное число . не является эйлеровым, так как регулярный граф ak может быть не связан (свойство b верно, но a может и не быть)

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

ВОРОТА | GATE-CS-2007 | Вопрос 23

0.00 (0%) 0 votes