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

Question

[habrdima]

Не знаю как спросить в интернете
есть такие графы

а есть такие

почему делают такие дуги?
чем они отличаются от просто линии?

Answer 1

[Wataru]

Ориентированный граф, у которого все ребра идут парами туда и обратно, полностью соответсвует неориентированному графу. Но если хотя бы где-то нет обратной дуги (как на правой картинке), то это уже отличие.

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

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

Comments

[habrdima]

Иногда имеет смысл рассматривать неориентированный граф как оринетированный с парными дугами, если в процессе работы симетрия как-то нарушается

как она нарушается?

алгоритмах поиска максимального потока

посмотрел не много, но мне кажется еще рано к этому переходить, можно пример попроще?

[Wataru]

habrdima, попроще примеров придумать не могу. Это редкость, на самом деле. Нарушение симметрии там в том, что поток имеет направление и в процессе работы алгоритма получается, что в одну сторону течет, а в другую - нет. И это очень естественно обрабатывается, ели изменить пропускную способность направленных ребер.

[habrdima]

Wataru, ладно, главное, что
1)это одно и тоже
2)разница в определенных обстоятельствах, когда дуга может быть направленна в одну сторону, а потом обратно?

[Wataru]

habrdima, Это одно и то же, если все симметрично.
Разница, если симметрия нарушается: в одну сторону дуга есть, в другую нет.

[habrdima]

Wataru, значит две стрелки означает что может быть только одна из них?

[Wataru]

habrdima, 2 стрелки означают, что есть связь и туда и обратно. Ромео людит Джульетту и Джульетта любит Ромео. Стрелочки и туда и обратно. Чудище любит Эсмиральду, но не обратно. Стрелочка только в одну сторону.

Линия без стрелок означает, что связь есть в обе стороны. То же самое, что и две стрелочки туда и обратно. Просто, если в графе нет и не может быть одиноких стрелочек, граф называют неориентированным и не усложняют модель парами.

[habrdima]

Wataru, но вы же уже это указали что это одно и тоже, но есть нюанс по этому разница есть, я так понял для этого и указывают две дуги, что бы показать что может быть нюанс

Разница, если симметрия нарушается: в одну сторону дуга есть, в другую нет.

из за чего работает только одна стрелка из двух?

[Wataru]

habrdima, Зависит от конкретной задачи/предметной области.

из за чего работает только одна стрелка из двух?

Ну вот допустим у вас граф отношение любви описывает. Ну вот не любит эсмиральда горбуна и все. Стрелочка есть только в одну сторону.

Или у вас граф описывает дороги в городе. Вот решило ГИБДД поставить знак "односторонее движение" на этой улице. И все. Стрелочка только в одну сторону. Где-то бетонный блок поставили - стрелочек нет ни в какую сторону. Такой граф стоит рассматривать как ориентированный. Даже если где-то есть двусторонние дороги, хранить надо обе половинки, ведь в любой момент одна из них может пропасть.

[habrdima]

Wataru, это значит что из за нюанса направление может быть в обе стороны (что тоже самое что одна линия) а может в одну из двух, в одну или другую сторону? и нюанс что то вроде динамически может менять стрелки, по этому граф рисуют с двумя дугами, что бы указать что может направление меняться?

вроде все сходиться)