Grafo dirigido

En matemáticas , y más específicamente en teoría de grafos , un grafo dirigido (o digrafo ) es un grafo que está formado por un conjunto de vértices conectados por aristas dirigidas , a menudo llamadas arcos .

En términos formales, un grafo dirigido es un par ordenado G = ( V , A ) donde ^{[ 1 ]}

• V es un conjunto cuyos elementos se denominan vértices , nodos o puntos ;
• A es un conjunto de pares ordenados de vértices, llamados arcos , aristas dirigidas (a veces simplemente aristas con el conjunto correspondiente llamado E en lugar de A ), flechas o líneas dirigidas .

Se diferencia de un grafo ordinario o no dirigido en que este último se define en términos de pares no ordenados de vértices, que generalmente se denominan aristas , enlaces o líneas .

La definición anterior no permite que un grafo dirigido tenga múltiples flechas con los mismos nodos de origen y destino, pero algunos autores consideran una definición más amplia que permite que los grafos dirigidos tengan tales arcos múltiples (es decir, permiten que el conjunto de arcos sea un multiconjunto ). A veces, estas entidades se denominan multigrafos dirigidos (o multidigrafos ). Por otro lado, la definición anterior permite que un grafo dirigido tenga bucles (es decir, arcos que conectan directamente nodos consigo mismos), pero algunos autores consideran una definición más restrictiva que no permite que los grafos dirigidos tengan bucles. ^{[ 2 ]} Los grafos dirigidos sin bucles pueden denominarse grafos dirigidos simples , mientras que los grafos dirigidos con bucles pueden denominarse digrafos de bucle (véase la sección Tipos de grafos dirigidos ).

Un arco ( x , y ) se considera dirigido de x a y ; y se denomina cabeza y x se denomina cola del arco; se dice que y es un sucesor directo de x y x se denomina un predecesor directo de y . Si un camino va de x a y , entonces se dice que y es un sucesor de x y alcanzable desde x , y se dice que x es un predecesor de y . El arco ( y , x ) se denomina arco inverso de ( x , y ) .

La matriz de adyacencia de un multigrafo con bucles es una matriz de valores enteros cuyas filas y columnas corresponden a los vértices. En esta matriz, una entrada no diagonal a _{_ij} representa el número de arcos desde el vértice i hasta el vértice j , y una entrada diagonal a _{_ii} representa el número de bucles en el vértice i . La matriz de adyacencia de un grafo dirigido es una matriz lógica y es única salvo permutación de filas y columnas.

Otra representación matricial para un grafo dirigido es su matriz de incidencia .

Consulte las instrucciones para obtener más definiciones.

Para un vértice, el número de extremos de cabeza adyacentes a un vértice se llama grado de entrada del vértice y el número de extremos de cola adyacentes a un vértice es su grado de salida (llamado factor de ramificación en los árboles).

Sea G = ( V , E ) y v ∈ V . El grado de entrada de v se denota deg ⁻ ( v ) y su grado de salida se denota deg ⁺ ( v ).

Un vértice con grado ⁻ ( v ) = 0 se denomina fuente , puesto que es el origen de cada uno de sus arcos salientes. Del mismo modo, un vértice con grado ⁺ ( v ) = 0 se denomina sumidero , puesto que es el extremo de cada uno de sus arcos entrantes.

La fórmula de suma de grados establece que, para un grafo dirigido,

${\displaystyle \sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.}$

Si para cada vértice v ∈ V , deg ⁺ ( v ) = deg ⁻ ( v ) , el grafo se denomina grafo dirigido balanceado . ^{[ 8 ]}

La secuencia de grados de un grafo dirigido es la lista de sus pares de grados de entrada y salida; en el ejemplo anterior, tenemos la secuencia de grados ((2, 0), (2, 2), (0, 2), (1, 1)). La secuencia de grados es un invariante de grafos dirigidos, por lo que los grafos dirigidos isomorfos tienen la misma secuencia de grados. Sin embargo, en general, la secuencia de grados no identifica de forma única un grafo dirigido; en algunos casos, los digrafos no isomorfos tienen la misma secuencia de grados.

El problema de realización de grafos dirigidos consiste en encontrar un grafo dirigido con una secuencia de grados igual a una secuencia dada de pares enteros positivos . (Los pares de ceros finales pueden ignorarse, ya que se obtienen fácilmente añadiendo un número adecuado de vértices aislados al grafo dirigido). Una secuencia que coincide con la secuencia de grados de algún grafo dirigido, es decir, para la cual el problema de realización de grafos dirigidos tiene solución, se denomina grafo dirigido o secuencia gráfica dirigida. Este problema puede resolverse mediante el algoritmo de Kleitman-Wang o mediante el teorema de Fulkerson-Chen-Anstee .

Un grafo dirigido es débilmente conectado (o simplemente conectado ^{[ 9 ]} ) si el grafo subyacente no dirigido obtenido al reemplazar todas las aristas dirigidas del grafo con aristas no dirigidas es un grafo conectado .

Un grafo dirigido es fuertemente conexo o fuerte si contiene un camino dirigido de x a y (y de y a x ) para cada par de vértices ( x , y ) . Los componentes fuertes son los subgrafos fuertemente conexos máximos.

Un grafo enraizado conectado (o grafo de flujo ) es aquel en el que existe un camino dirigido a cada vértice desde un vértice raíz distinguido .

• Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: teoría, algoritmos y aplicaciones , Springer , ISBN 1-85233-268-9(La primera edición corregida de 2007 ya está disponible gratuitamente en el sitio web de los autores; la segunda edición apareció en 2009 ISBN) 1-84800-997-6).
• Bang-Jensen, Jørgen; Gutin, Gregory (2018), Clases de gráficos dirigidos , Springer , ISBN 978-3319718408.
• Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones , North-Holland, ISBN 0-444-19451-7.
• Diestel, Reinhard (2005), Teoría de grafos (3.ª  ed.), Springer , ISBN 3-540-26182-6(La tercera edición electrónica está disponible gratuitamente en el sitio web del autor).
• Harary, Frank ; Norman, Robert Z.; Cartwright, Dorwin (1965), Modelos estructurales: Una introducción a la teoría de los grafos dirigidos , Nueva York: Wiley.
• Número de grafos dirigidos (o grafos dirigidos) con n nodos de la Enciclopedia en línea de secuencias de enteros