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 ).

An arc (x, y) is considered to be directed fromxtoy; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x and reachable from x, and x is said to be a predecessor of y. The arc (y, x) is called the reversed arc of (x, y).

The adjacency matrix of a multidigraph with loops is the integer-valued matrix with rows and columns corresponding to the vertices, where a nondiagonal entry a_ij is the number of arcs from vertex i to vertex j, and the diagonal entry a_ii is the number of loops at vertex i. The adjacency matrix of a directed graph is a logical matrix, and is unique up to permutation of rows and columns.

Another matrix representation for a directed graph is its incidence matrix.

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