Предтопологический порядок
В области информатики претопологический порядок или предтопологический порядок ориентированного графа — это линейный порядок его вершин, такой, что если существует направленный путь от вершины u к вершине v , и v стоит перед u в порядке , то существует также направленный путь из вершины v в вершину u . [1] [2]
Если граф представляет собой ориентированный ациклический граф (DAG), топологические порядки являются предтопологическими порядками, и наоборот. [1] В других случаях любое предтопологическое упорядочение дает частичный порядок .
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Шрийвер, Александр (10 декабря 2002 г.). Комбинаторная оптимизация: многогранники и эффективность . Springer Science & Business Media. п. 89. ИСБН 9783540443896 .
- ^ Седжвик, Роберт ; Уэйн, Кевин (26 сентября 2016 г.). «ориентированные графы» . Алгоритмы, 4-е издание . Проверено 6 сентября 2017 г.