@habrdima

Чем отличаются двунаправленные графы от графа с дугами в обе стороны?

Не знаю как спросить в интернете
есть такие графы
639a28d872be1767969286.png
а есть такие
639a28e7199f1533579014.png
почему делают такие дуги?
чем они отличаются от просто линии?
  • Вопрос задан
  • 265 просмотров
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Ориентированный граф, у которого все ребра идут парами туда и обратно, полностью соответсвует неориентированному графу. Но если хотя бы где-то нет обратной дуги (как на правой картинке), то это уже отличие.

Почему вообще придумали использовать ориентированне графы? Потому что они полезны. Например, отношение "любовь" между людьми можно описать ориентированным графом, а вот неориентированным - нет (ибо есть безответная любовь).

Иногда имеет смысл рассматривать неориентированный граф как оринетированный с парными дугами, если в процессе работы симетрия как-то нарушается. Например в алгоритмах поиска максимального потока на графе так и происходит. Поэтому он не работает с неориентированными графами - в них надо каждое ребро разбить на два туда и обратно.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы