Двунаправленный график - Bidirected graph

Различные типы ребер в двунаправленном графе

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

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

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

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

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

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

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

Рекомендации

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