stringtranslate.com

Grafo dirigido

Un gráfico dirigido simple

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

Definición

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

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

La definición antes mencionada 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 multidígrafos ).
Por otro lado, la definición antes mencionada 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 estrecha que no permite que los grafos dirigidos tengan bucles. [2] Los grafos dirigidos sin bucles pueden llamarse grafos dirigidos simples , mientras que los grafos dirigidos con bucles pueden llamarse dígrafos-bucles (véase la sección Tipos de grafo dirigido).

Tipos de grafos dirigidos

Subclases

Un gráfico acíclico dirigido simple
Un torneo en 4 vértices

Dígrafos con propiedades suplementarias

Terminología básica

Gráfico orientado con matriz de incidencia correspondiente

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

La matriz de adyacencia de un multidígrafo con bucles es la matriz de valores enteros con filas y columnas correspondientes a los vértices, donde una entrada no diagonal a ij es el número de arcos desde el vértice i al vértice j , y la entrada diagonal a ii es 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 hasta la permutación de filas y columnas.

Otra representación matricial de un gráfico dirigido es su matriz de incidencia .

Consulte la dirección para obtener más definiciones.

Grado de entrada y grado de salida

Un gráfico dirigido con vértices etiquetados (grado de entrada, grado de salida)

Para un vértice, la cantidad de extremos de cabeza adyacentes a un vértice se denomina grado de entrada del vértice y la cantidad 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 vV . El grado de entrada de v se denota deg ( v ) y su grado de salida se denota deg + ( v ).

Un vértice con deg ( v ) = 0 se denomina origen , ya que es el origen de cada uno de sus arcos de salida. De manera similar, un vértice con deg + ( v ) = 0 se denomina sumidero , ya que es el final de cada uno de sus arcos de entrada.

La fórmula de suma de grados establece que, para un gráfico dirigido,

Si para cada vértice vV , deg + ( v ) = deg ( v ) , el gráfico se denomina gráfico dirigido equilibrado . [8]

Secuencia de grados

La secuencia de grados de un grafo dirigido es la lista de sus pares de grados de entrada y de salida; para 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, la secuencia de grados, en general, no identifica de forma única a un grafo dirigido; en algunos casos, los dígrafos no isomorfos tienen la misma secuencia de grados.

El problema de realización de grafos dirigidos es el problema de encontrar un grafo dirigido con la secuencia de grados de una secuencia dada de pares de números enteros positivos . (Los pares de ceros finales pueden ignorarse ya que se realizan de manera trivial agregando un número apropiado de vértices aislados al grafo dirigido). Una secuencia que es la secuencia de grados de algún grafo dirigido, es decir, para la cual el problema de realización de grafos dirigidos tiene una solución, se llama 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 .

Conectividad de gráficos dirigidos

Un gráfico dirigido está débilmente conexo (o simplemente conexo [9] ) si el gráfico subyacente no dirigido obtenido al reemplazar todos los bordes dirigidos del gráfico con bordes no dirigidos es un gráfico conexo .

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 gráfico con raíz conectada (o gráfico de flujo ) es aquel en el que existe un camino dirigido a cada vértice desde un vértice raíz distinguido .

Véase también

Notas

  1. ^ Bang-Jensen y Gutin (2000). Bang-Jensen & Gutin (2018), Capítulo 1.Diestel (2005), Sección 1.10. Bondy y Murty (1976), Sección 10.
  2. ^ abc Chartrand, Gary (1977). Introducción a la teoría de grafos. Courier Corporation. ISBN 9780486247755Archivado desde el original el 4 de febrero de 2023. Consultado el 2 de octubre de 2020 .
  3. ^ Bang-Jensen y Gutin (2018), Capítulo 7 de Yeo.
  4. ^ ab Bang-Jensen & Gutin (2018), Capítulo 2 de Bang-Jensen y Havet.
  5. ^ Bang-Jensen & Gutin (2018), Capítulo 8 por Galeana-Sánchez y Hernández-Cruz.
  6. ^ Diestel (2005), Sección 1.10.
  7. ^ Bang-Jensen & Gutin (2018), Capítulo 3 de Gutin.
  8. ^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Matemáticas discretas y teoría de grafos , PHI Learning Pvt. Limitado. Ltd., pág. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Clases de matrices combinatorias, Enciclopedia de matemáticas y sus aplicaciones, vol. 108, Cambridge University Press, pág. 51, ISBN 978-0-521-86565-4.
  9. ^ Bang-Jensen & Gutin (2000) p. 19 en la edición de 2007; p. 20 en la 2ª edición (2009).

Referencias

Enlaces externos