Связность в направленных графах

До настоящего момента мы рассматривали задачи, относящиеся к ненаправленным графам; теперь посмотрим, в какой степени эти идеи применимы к направленным графам.

Напомним, что в направленном графе ребро (и, v) имеет направление: оно про- ходит из и в v.

В этом случае отношение между и и v является асимметричным, что имеет качественные последствия для структуры полученного графа. Например, в разделе 3.1 Всемирная паутина упоминалась как экземпляр большого, сложного направленного графа, узлами которого являются страницы, а ребрами — гипер- ссылки. Процесс веб-серфинга может быть представлен последовательностью ребер этого направленного графа; направленность важна, потому что в общем случае переход по гиперссылкам в обратном направлении невозможен.

В то же время многие базовые определения и алгоритмы имеют естественные аналоги в направленных графах. Например, к их числу относится представление списка смежности и алгоритмы поиска в графах, такие как BFS и DFS.

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

Еще по теме Связность в направленных графах:

  1. Направленность
  2. § 6. Направленность личности
  3. НАПРАВЛЕННОСТЬ ЛИЧНОСТИ
  4. ПОВЕДЕНЧЕСКОЕ НАПРАВЛЕНИЕ 1.
  5. НАПРАВЛЕНИЕ СПРАШИВАНИЯ
  6. 2.1. Направления объективного подхода
  7. Глава 1 ПСИХОДИНАМИЧЕСКОЕ НАПРАВЛЕНИЕ
  8. Глава 3 КОГНИТИВНОЕ НАПРАВЛЕНИЕ
  9. НАПРАВЛЕННОСТЬ ЛИЧНОСТИ
  10. ЛИЧНОСТЬ: НАПРАВЛЕННОСТЬ
  11. Б. Классификация гражданских договоров по признаку направленности
  12. Профессиональная направленность юриста
  13. 2.2.3. Психологическое направление