Двунаправленный граф
В математической области теории графов ( двунаправленный граф введен Эдмондсом и Джонсоном, 1970 г. ) [1] — это граф , в котором каждому ребру на каждом конце присвоена независимая ориентация (или направление, или стрелка). Таким образом, существует три типа двунаправленных ребер: те, у которых стрелки направлены наружу, к вершинам на обоих концах; те, где обе стрелки направлены внутрь, в сторону от вершин; и те, у которых одна стрелка указывает от своей вершины к противоположному концу, а другая стрелка указывает в том же направлении, что и первая, от противоположного конца и к своей собственной вершине.
Ребра этих трех типов можно назвать соответственно экстравертными , интровертными и направленными . «Направленные» ребра аналогичны обычным направленным ребрам в ориентированном графе ; таким образом, ориентированный граф — это особый вид двунаправленного графа.
Иногда желательно иметь также ребра только с одного конца ( полукрая ); они получают только одну стрелу. Край без концов ( свободный край ) не имеет стрелок. Края, которые не являются ни половинками, ни свободными краями, можно назвать обычными краями .
— Кососимметричный граф это граф двойного покрытия двунаправленного графа.
Двунаправленный граф можно рассматривать как ориентацию знакового графа , аналогично тому, как ориентированный граф можно рассматривать как ориентацию обычного неориентированного графа .
Другие значения [ править ]
Симметричный ориентированный граф (то есть ориентированный граф, в котором обратная сторона каждого ребра также является ребром) иногда также называют «двунаправленным графом». [2]
См. также [ править ]
Ссылки [ править ]
- ^ Эдмондс, Джек ; Джонсон, Эллис Л. (1970), «Сопоставление: хорошо решаемый класс линейных программ», Комбинаторные структуры и их приложения: материалы симпозиума в Калгари, июнь 1969 г. , Нью-Йорк: Гордон и Брич . Перепечатано в журнале «Комбинаторная оптимизация» — Эврика, ты уменьшаешься! , Springer-Verlag, Конспекты лекций по информатике 2570, 2003 г., стр. 27–30, дои : 10.1007/3-540-36478-1_3 .
- ^ Мельхорн, Курт ; Сандерс, Питер (2008), Алгоритмы и структуры данных: базовый набор инструментов , Springer Science & Business Media, стр. 49 и 170–171, ISBN. 978-3-540-77978-0
 | Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |