Двунаправленный граф
В математической области теории графов двунаправленный граф (представленный Edmonds & Johnson 1970 ) [1] — это граф , в котором каждому ребру дана независимая ориентация (или направление, или стрелка) на каждом конце. Таким образом, существует три вида двунаправленных ребер: те, у которых стрелки направлены наружу, к вершинам, с обоих концов; те, где обе стрелки указывают внутрь, от вершин; и те, в которых одна стрелка указывает от своей вершины к противоположному концу, а другая стрелка указывает в том же направлении, что и первая, от противоположного конца к своей вершине.
Ребра этих трех типов можно назвать соответственно экстравертными , интровертными и направленными . «Направленные» ребра такие же, как и обычные ориентированные ребра в ориентированном графе ; таким образом, ориентированный граф — это особый вид двунаправленного графа.
Иногда желательно иметь ребра только с одним концом ( полуребра ); они получают только одну стрелу. Ребро без концов ( свободное ребро ) не имеет стрелок. Ребра, которые не являются ни половинчатыми, ни свободными ребрами, можно назвать обычными ребрами .
Симметричный ориентированный граф (то есть ориентированный граф, в котором реверс каждого ребра также является ребром) иногда также называют «двунаправленным графом». [2]
