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]
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 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 simpleUn torneo en 4 vértices
Los grafos dirigidos simétricos son grafos dirigidos en los que todas las aristas aparecen dos veces, una en cada dirección (es decir, por cada flecha que pertenece al dígrafo, también le pertenece la flecha inversa correspondiente). (A veces, a esta arista se la denomina "bidireccional" y a estos grafos se los denomina "bidireccionales", pero esto entra en conflicto con el significado de los grafos bidireccionales ).
Los grafos dirigidos simples son grafos dirigidos que no tienen bucles (flechas que conectan directamente los vértices entre sí) ni flechas múltiples con los mismos nodos de origen y destino. Como ya se ha introducido, en el caso de flechas múltiples, la entidad suele denominarse multigrafo dirigido . Algunos autores describen los dígrafos con bucles como dígrafos-bucles . [2]
Los grafos dirigidos completos son grafos dirigidos simples en los que cada par de vértices está unido por un par simétrico de arcos dirigidos (equivale a un grafo completo no dirigido con las aristas reemplazadas por pares de arcos inversos). De ello se deduce que un dígrafo completo es simétrico.
Los dígrafos multipartitos semicompletos son dígrafos simples en los que el conjunto de vértices está dividido en conjuntos de modo que para cada par de vértices x e y en conjuntos diferentes, existe un arco entre x e y . Puede haber un arco entre x e y o dos arcos en direcciones opuestas. [3]
Los dígrafos semicompletos son dígrafos simples en los que hay un arco entre cada par de vértices. Todo dígrafo semicompleto es un dígrafo semicompleto multipartito de manera trivial, en el que cada vértice constituye un conjunto de la partición. [4]
Los dígrafos cuasititransitivos son dígrafos simples en los que por cada triple x , y , z de vértices distintos con arcos de x a y y de y a z , hay un arco entre x y z . Puede haber solo un arco entre x y z o dos arcos en direcciones opuestas. Un dígrafo semicompleto es un dígrafo cuasititransitivo. Existen extensiones de dígrafos cuasititransitivos llamadas dígrafos k -cuasititransitivos. [5]
Los grafos orientados son grafos dirigidos que no tienen pares opuestos de aristas dirigidas (es decir, como máximo uno de ( x , y ) y ( y , x ) pueden ser flechas del grafo). De ello se deduce que un grafo dirigido es un grafo orientado si y solo si no tiene 2-ciclos . [6] (Este no es el único significado de "grafo orientado"; véase Orientación (teoría de grafos) .)
Los torneos son grafos orientados que se obtienen eligiendo una dirección para cada arista en grafos completos no dirigidos . Un torneo es un dígrafo semicompleto. [4]
Los multiárboles son DAG en los que no hay dos caminos dirigidos distintos desde el mismo vértice inicial al mismo vértice final.
Los árboles orientados o poliárboles son DAG formados al orientar los bordes de los árboles (gráficos conectados, acíclicos y no dirigidos).
Los árboles enraizados son árboles orientados en los que todos los bordes del árbol subyacente no dirigido se dirigen hacia o desde la raíz (se denominan, respectivamente, arborescencias o árboles externos y árboles internos ).
Dígrafos con propiedades suplementarias
Los gráficos dirigidos ponderados (también conocidos como redes dirigidas ) son gráficos dirigidos (simples) con pesos asignados a sus flechas, de manera similar a los gráficos ponderados (que también se conocen como redes no dirigidas o redes ponderadas ). [2]
Las redes de flujo son gráficos dirigidos ponderados donde se distinguen dos nodos, una fuente y un sumidero .
Los grafos dirigidos con raíz (también conocidos como grafos de flujo ) son dígrafos en los que se ha distinguido un vértice como raíz.
Los gráficos de flujo de control son dígrafos con raíz que se utilizan en informática como representación de las rutas que se pueden recorrer a través de un programa durante su ejecución.
Los gráficos de flujo de señales son gráficos dirigidos en los que los nodos representan variables del sistema y las ramas (bordes, arcos o flechas) representan conexiones funcionales entre pares de nodos.
Los gráficos de flujo son dígrafos asociados a un conjunto de ecuaciones algebraicas o diferenciales lineales.
Los diagramas conmutativos son dígrafos utilizados en la teoría de categorías , donde los vértices representan objetos (matemáticos) y las flechas representan morfismos, con la propiedad de que todos los caminos dirigidos con los mismos puntos de inicio y final conducen al mismo resultado por composición.
En la teoría de grupos de Lie , un carcaj Q es un grafo dirigido que sirve como dominio de, y por lo tanto caracteriza la forma de, una representación V definida como un funtor , específicamente un objeto de la categoría de funtor FinVct K F ( Q ) donde F ( Q ) es la categoría libre en Q que consiste en caminos en Q y FinVct K es la categoría de espacios vectoriales de dimensión finita sobre un cuerpo K . Las representaciones de un carcaj etiquetan sus vértices con espacios vectoriales y sus aristas (y por lo tanto caminos) de manera compatible con transformaciones lineales entre ellos, y se transforman mediante transformaciones naturales .
Terminología básica
Grafo orientado con matriz de incidencia correspondiente
Se considera que un arco ( x , y ) va 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 que x es un predecesor directo de y . Si un camino va de x a y , se dice que y es un sucesor de x y se puede alcanzar desde x , y se dice que x es un 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 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 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 v ∈ V , 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 trivialmente 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 .
^ Bang-Jensen y Gutin (2000). Bang-Jensen y Gutin (2018), Capítulo 1.Diestel (2005), Sección 1.10. Bondy y Murty (1976), Sección 10.
^ 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 .
^ Bang-Jensen & Gutin (2018), Capítulo 7 de Yeo.
^ ab Bang-Jensen & Gutin (2018), Capítulo 2 de Bang-Jensen y Havet.
^ Bang-Jensen & Gutin (2018), Capítulo 8 de Galeana-Sanchez y Hernandez-Cruz.
^ Diestel (2005), Sección 1.10.
^ Bang-Jensen & Gutin (2018), Capítulo 3 de Gutin.
^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Matemáticas discretas y teoría de grafos , PHI Learning Pvt. Limitado. Ltd., pág. 460, ISBN978-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.
^ Bang-Jensen & Gutin (2000) p. 19 en la edición de 2007; p. 20 en la 2ª edición (2009).
Referencias
Bang-Jensen, Jørgen; Gutin, Gregory (2000), Dígrafos: teoría, algoritmos y aplicaciones, Springer , ISBN 1-85233-268-9(la primera edición corregida de 2007 ahora está disponible gratuitamente en el sitio de los autores; la segunda edición apareció en 2009 ISBN 1-84800-997-6 ).
Bang-Jensen, Jørgen; Gutin, Gregory (2018), Clases de grafos dirigidos , Springer , ISBN 978-3319718408.
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 del autor).
Harary, Frank ; Norman, Robert Z.; Cartwright, Dorwin (1965), Modelos estructurales: una introducción a la teoría de grafos dirigidos , Nueva York: Wiley.
