Двунаправленный граф

Граф, рёбра которого имеют независимые направления на обоих концах

В математической области теории графов двунаправленный граф (введенный Эдмондсом и Джонсоном в 1970 году) ^[1] — это граф , в котором каждому ребру задана независимая ориентация (или направление, или стрелка) на каждом конце. Таким образом, существует три вида двунаправленных ребер: те, в которых стрелки указывают наружу, к вершинам, на обоих концах; те, в которых обе стрелки указывают внутрь, от вершин; и те, в которых одна стрелка указывает от своей вершины и к противоположному концу, в то время как другая стрелка указывает в том же направлении, что и первая, от противоположного конца и к своей собственной вершине.

Ребра этих трех типов можно назвать, соответственно, экстравертными , интровертными и направленными . «Направленные» ребра — это то же самое, что и обычные направленные ребра в направленном графе ; таким образом, направленный граф — это особый вид двунаправленного графа.

Иногда желательно иметь также ребра только с одним концом ( полуребра ); они получают только одну стрелку. Ребро без концов ( свободное ребро ) не имеет стрелок. Ребра, которые не являются ни половинными, ни свободными ребрами, можно назвать обычными ребрами .

Кососимметричный граф — это граф двойного покрытия двунаправленного графа.

Двунаправленный граф можно рассматривать как ориентацию знакового графа , аналогично тому, как ориентированный граф можно рассматривать как ориентацию обычного неориентированного графа .

Другие значения

Симметричный направленный граф (то есть направленный граф, в котором обратная сторона каждого ребра также является ребром) иногда также называют «двунаправленным графом». ^[2]

Смотрите также

Ссылки

^ Эдмондс, Джек ; Джонсон, Эллис Л. (1970), «Сопоставление: хорошо решенный класс линейных программ», Комбинаторные структуры и их приложения: Труды симпозиума в Калгари, июнь 1969 г. , Нью-Йорк: Гордон и Брич. Перепечатано в Combinatori Optimization — Eureka, You Shrink! , Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, стр. 27–30, doi :10.1007/3-540-36478-1_3.
^ Мельхорн, Курт ; Сандерс, Питер (2008), Алгоритмы и структуры данных: базовый набор инструментов, Springer Science & Business Media, стр. 49 и 170–171, ISBN 978-3-540-77978-0

Эта статья по теории графов — заглушка . Вы можете помочь Википедии, расширив ее.

[1] Эдмондс, Джек ; Джонсон, Эллис Л. (1970), «Сопоставление: хорошо решенный класс линейных программ», Комбинаторные структуры и их приложения: Труды симпозиума в Калгари, июнь 1969 г. , Нью-Йорк: Гордон и Брич. Перепечатано в Combinatori Optimization — Eureka, You Shrink! , Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, стр. 27–30, doi :10.1007/3-540-36478-1_3.

[MehlhornSanders2008-2] Мельхорн, Курт ; Сандерс, Питер (2008), Алгоритмы и структуры данных: базовый набор инструментов, Springer Science & Business Media, стр. 49 и 170–171, ISBN 978-3-540-77978-0