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

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

Вопрос: Q19-4c9f66

Пусть G = (V, E) — конечный ориентированный ациклический граф с

Что из следующего должно быть верным?

1

У G есть вершина без входящего ребра

2

(2) G имеет вершину без исходящего ребра

3

G имеет изолированную вершину, то есть вершину, не имеющую ни входящего, ни исходящего ребра

Ответы

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

Объяснение

• Ну у DAG должна быть хотя бы
  • одна вершина без входов,
  • одна вершина без выходов,
  • иначе циклы будут.
• «3» необязательно, например в деревьях.

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

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

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

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