2011-gre-cs-practice-book.pdf/Q30 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Вопрос: Q30-08c765)
Строка 5: Строка 5:
  
 
[[File:graph.png|480px]]
 
[[File:graph.png|480px]]
 +
<graph>
 +
digraph G{
 +
  rankdir=UD;
 +
  edge [color=blue];
 +
  10 -> 5
 +
  10 -> 20
 +
  5 -> 13
 +
  5 -> 17
 +
  20 -> 17
 +
  20 -> 30
 +
  13 -> 14
 +
  14 -> 7
 +
  17-> 7
 +
  7 -> 30
 +
}
 +
</graph>
  
 
Что из перечисленного является топологической сортировкой вершин графа[https://habr.com/ru/companies/otus/articles/499138/]?
 
Что из перечисленного является топологической сортировкой вершин графа[https://habr.com/ru/companies/otus/articles/499138/]?

Версия 17:52, 19 декабря 2024

Задача зарезервирована: Urmat A 14:58, 19 декабря 2024 (UTC)

Вопрос: Q30-08c765

Дан ориентированный граф:

Graph.png [svg]

Что из перечисленного является топологической сортировкой вершин графа[1]?

Ответы

  1. 5, 7, 10, 13, 14, 17, 20, 30
  2. 10, 5, 13, 14, 7, 30, 17, 20
  3. 10, 5, 13, 17, 20, 14, 7, 30
  4. 10, 5, 20, 13, 17, 30, 14, 7
  5. Правильный ответ: 10, 20, 5, 17, 13, 14, 7, 30

Объяснение

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

Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30. Далее можно пойти либо в 7, либо в 20. Но из 20 можно попасть 7, значит эта вершина стоит раньше. Тогда идем выбираем 7. Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот. Пойдём так дальше до 13. Получили 13-14-7-30. Из 13 опять вилка - либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30. Далее очевидный выбор между 10 и 20. Получили 10-20-5-17-13-14-7-30.Check-me-animated.gif Решено: Urmat A 15:49, 19 декабря 2024 (UTC)

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q30&oldid=34300»