Gráfico dirigido

Un gráfico dirigido (o dígrafo para abreviar ) es un gráfico (múltiple) a cuyos bordes se les asigna una dirección. Los bordes dirigidos también se denominan arcos y, en algunas fuentes, simplemente se denominan bordes. Un grafo en el que no se asigna una dirección a ningún borde se llama grafo no dirigido o no dígrafo .

Conceptos básicos

Formalmente, un dígrafo consta de un conjunto , cuyos elementos se denominan vértices , y un conjunto de pares ordenados de vértices .

El arco es incidente a los vértices y . En este caso, dicen que  es el vértice inicial del arco, y  es el vértice final .

Un dígrafo obtenido de un gráfico simple mediante la orientación de los bordes se llama dirigido . A diferencia de este último, en un dígrafo simple arbitrario, dos vértices pueden estar conectados por dos arcos dirigidos de manera diferente.

Un grafo completo dirigido se llama torneo .

Conectividad

Un recorrido en un dígrafo es una secuencia alterna de vértices y arcos , de la forma (los vértices se pueden repetir). La longitud de la ruta  es el número de arcos en ella.

Un camino es una ruta en un dígrafo sin arcos repetidos, un camino simple  es sin vértices repetidos. Si hay un camino de un vértice a otro, entonces el segundo vértice es accesible desde el primero.

Un contorno es un camino cerrado .

Para la mitad de la ruta , se elimina la restricción sobre la dirección de los arcos , y la mitad de la ruta y la mitad del contorno se definen de manera similar .

Un dígrafo es fuertemente conexo , o simplemente fuerte , si todos sus vértices son alcanzables entre sí ; unidireccional conectado , o simplemente unidireccional , si para dos vértices cualesquiera al menos uno es accesible desde el otro; débilmente conexo , o simplemente débil , si ignorando la dirección de los arcos se obtiene un (multi)grafo conexo;

El subgrafo fuerte máximo se llama componente fuerte ; el componente unilateral y el componente débil se definen de manera similar.

La condensación de un dígrafo es un dígrafo cuyos vértices son componentes fuertes , y un arco en muestra la presencia de al menos un arco entre los vértices incluidos en los componentes correspondientes.

Definiciones adicionales

Un grafo o bulto acíclico dirigido es un dígrafo sin contorno.

Una gráfica dirigida que se obtiene a partir de una dada cambiando la dirección de las aristas a la opuesta se llama inversa .

Imagen y propiedades de todos los dígrafos de tres nodos

Leyenda: S  es débil, OC  es unilateral, SS  es fuerte, H  es un gráfico dirigido, G  es una hamaca (acíclica), T  es un torneo

Aplicación de dígrafos

Los dígrafos se usan ampliamente en programación como una forma de describir sistemas con conexiones complejas. Por ejemplo, una de las principales estructuras utilizadas en el desarrollo de compiladores y en general para la representación de programas informáticos es el gráfico de flujo de datos.

Relaciones binarias

Una relación binaria sobre un portador finito se puede representar como un dígrafo . Las relaciones antirreflexivas se pueden representar mediante un dígrafo simple ; en el caso general, se requiere un dígrafo con bucles. Si la relación es simétrica , entonces puede representarse mediante un gráfico no dirigido , y si es antisimétrica, entonces mediante un gráfico dirigido .

Varios

El algoritmo de Suurballe es un algoritmo para encontrar dos caminos que no se intersecan (sin bordes comunes) en un gráfico dirigido con pesos no negativos, de modo que ambos caminos conectan el mismo par de vértices y tienen una longitud común mínima.

Literatura

• Harari F. Teoría de grafos. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .
• Ore, Oistin . Teoría de grafos. — M .: URSS , 2008. — 352 p. - ISBN 978-5-397-00044-4 .
• Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compiladores : Principios, Técnicas y Herramientas, 2ª edición = Compiladores: Principios, Técnicas y Herramientas. - 2ª ed. - M .: "Williams" , 2008. - ISBN 978-5-8459-1349-4 .