Упражнения с решениями Упражнение с решением 1

Возьмем направленный ациклический граф G на рис. 3.9. Сколько топологических упорядочений он имеет?

Рис.

3.9. Сколько топологических упорядочений существует у этого графа?

Решение

Вспомните, что топологическим упорядочением G называется такое упорядочение узлов v1, v2, ..., vя, при котором все ребра указывают «вперед»: для каждого ребра (v., v) выполняется условие i < j.

Конечно, чтобы ответить на вопрос, можно перебрать все 5 · 4 · 3 · 2 · 1 = 120 воз- можных упорядочений и проверить, является ли каждое из них топологическим упорядочением. Впрочем, такой перебор займет много времени.

Лучше действовать иначе. Как было показано в тексте (и как следует непосред- ственно из определения), первым узлом топологического упорядочения должен быть узел, не имеющих входящих ребер. Аналогичным образом последним узлом должен быть узел, не имеющий выходящих ребер. Следовательно, в каждом топо- логическом упорядочении G узел a должен стоять на первом месте, а узел e — на последнем.

Теперь нужно понять, как должны располагаться узлы b, c и d в середине упо- рядочения. Ребро (c, d) требует, чтобы узел c предшествовал d, однако b может

находиться в любой позиции относительно этих двух узлов: до обоих, между с и d, или после обоих. Других вариантов нет, и мы можем заключить, что существуют три возможных топологических упорядочения:

a, b, c, d, e

a, c, b, d, e

a, c, d, b, e

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения с решениями Упражнение с решением 1:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения