En el dominio matemático de la teoría de grafos , un grafo bidireccional (introducido por Edmonds y Johnson 1970) [1] es un grafo en el que a cada arista se le da una orientación independiente (o dirección, o flecha) en cada extremo. Por lo tanto, hay tres tipos de aristas bidireccionales: aquellas en las que las flechas apuntan hacia afuera, hacia los vértices, en ambos extremos; aquellas en las que ambas flechas apuntan hacia adentro, alejándose de los vértices; y aquellas en las que una flecha apunta lejos de su vértice y hacia el extremo opuesto, mientras que la otra flecha apunta en la misma dirección que la primera, alejándose del extremo opuesto y hacia su propio vértice.
Las aristas de estos tres tipos pueden denominarse, respectivamente, extravertidas , introvertidas y dirigidas . Las aristas "dirigidas" son las mismas que las aristas dirigidas ordinarias en un grafo dirigido ; por lo tanto, un grafo dirigido es un tipo especial de grafo bidirigido.
A veces es deseable tener también aristas con un solo extremo ( medias aristas ); éstas tienen solo una flecha. Una arista sin extremos (una arista suelta ) no tiene flechas. Las aristas que no son ni medias aristas ni aristas sueltas pueden llamarse aristas ordinarias .
Un gráfico antisimétrico es el gráfico de doble cobertura de un gráfico bidireccional.
Un gráfico bidireccional puede considerarse como una orientación de un gráfico con signo , de manera similar a cómo un gráfico dirigido puede verse como una orientación de un gráfico ordinario no dirigido .
Un gráfico dirigido simétrico (es decir, un gráfico dirigido en el que el reverso de cada arista también es una arista) a veces también se denomina "gráfico bidirigido". [2]