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 , frecuentemente llamados arcos .
Definición
En términos formales, un gráfico 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 denominado E en lugar de A ), flechas o líneas dirigidas .
La definición antes mencionada no permite que un gráfico dirigido tenga múltiples flechas con los mismos nodos de origen y destino, pero algunos autores consideran una definición más amplia que permita que los gráficos dirigidos tengan tales arcos múltiples (es decir, permiten que el conjunto de arcos sea un conjunto múltiple ). . A veces estas entidades se denominan multigrafos dirigidos (o multidigrafos ). Por otro lado, la definición antes mencionada permite que un grafo dirigido tenga bucles (es decir, arcos que conectan directamente los nodos consigo mismos), pero algunos autores consideran una definición más estrecha que no permite que los grafos dirigidos tengan bucles. [2]
Los gráficos dirigidos sin bucles pueden denominarse gráficos dirigidos simples , mientras que los gráficos dirigidos con bucles pueden denominarse dígrafos de bucle (consulte la sección Tipos de gráficos dirigidos).
Tipos de grafos dirigidos
Subclases
Un gráfico acíclico dirigido simpleUn torneo en 4 vértices
Los gráficos dirigidos simétricos son gráficos dirigidos donde 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). (Esta arista a veces se denomina "bidireccional" y estos gráficos a veces se denominan "bidireccionales", pero esto entra en conflicto con el significado de los gráficos bidireccionales ).
Los gráficos dirigidos simples son gráficos dirigidos que no tienen bucles (flechas que conectan directamente los vértices entre sí) ni múltiples flechas con los mismos nodos de origen y destino. Como ya se introdujo, en el caso de varias flechas, la entidad generalmente se aborda como multigrafo dirigido . Algunos autores describen los dígrafos con bucles como dígrafos en bucle . [2]
Los grafos dirigidos completos son grafos dirigidos simples donde 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 se divide en conjuntos de modo que para cada par de vértices x e y en diferentes conjuntos, hay un arco entre x e y . Puede haber un arco entre xey o dos arcos en direcciones opuestas. [3]
Los dígrafos semicompletos son dígrafos simples donde hay un arco entre cada par de vértices. Cada dígrafo semicompleto es un dígrafo multipartito semicompleto de manera trivial, constituyendo cada vértice un conjunto de la partición. [4]
Los dígrafos cuasitransitivos son dígrafos simples donde 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 xyz o dos arcos en direcciones opuestas. Un dígrafo semicompleto es un dígrafo cuasitransitivo. Hay extensiones de dígrafos cuasitransitivos llamados k -dígrafos cuasitransitivos. [5]
Los gráficos orientados son gráficos 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 gráfico). De ello se deduce que un gráfico dirigido es un gráfico orientado si y sólo si no tiene 2 ciclos . [6] (Este no es el único significado de "gráfico orientado"; consulte Orientación (teoría de grafos) .)
Los torneos son gráficos orientados que se obtienen eligiendo una dirección para cada arista en gráficos 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 hasta el mismo vértice final.
Los árboles orientados o poliárboles son DAG formados orientando los bordes de los árboles (gráficos no dirigidos, acíclicos y conectados).
Los árboles enraizados son árboles orientados en los que todos los bordes del árbol no dirigido subyacente están dirigidos hacia o lejos de la raíz (se denominan, respectivamente, arborescencias o árboles externos y árboles internos ).
Digrafos 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 grafos dirigidos ponderados donde se distinguen dos nodos, una fuente y un sumidero .
Los grafos dirigidos enraizados (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 arraigados que se utilizan en informática como una representación de las rutas que pueden recorrerse 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 con un conjunto de ecuaciones diferenciales o algebraicas 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 el mismo punto inicial y final conducen al mismo resultado por composición.
En la teoría de los grupos de Lie , un carcaj Q es un gráfico dirigido que sirve como dominio 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 functor FinVct K F ( Q ) donde F ( Q ) es la categoría libre en Q que consta de caminos en Q y FinVct K es la categoría de espacios vectoriales de dimensión finita sobre un campo K . Las representaciones de un carcaj etiquetan sus vértices con espacios vectoriales y sus bordes (y por lo tanto caminos) de manera compatible con transformaciones lineales entre ellos, y se transforman mediante transformaciones naturales .
Terminología básica
Gráfico orientado con su correspondiente matriz de incidencia.
Se considera que un arco ( x , y ) está dirigido de xa y ; y se llama cabeza y x se llama cola del arco; Se dice que y es un sucesor directo de x y se dice que x es un predecesor directo de y . Si un camino va de x a y , entonces se dice que y es un sucesor de x y accesible desde x , y se dice que x es un predecesor de y . El arco ( y , x ) se llama 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 gráfico 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 interno y externo
Un gráfico dirigido con vértices etiquetados (grado interno, grado externo)
Para un vértice, el número de extremos de cabeza adyacentes a un vértice se llama grado interno del vértice y el número de extremos de cola adyacentes a un vértice es su grado externo (llamado factor de ramificación en los árboles).
Sea G = ( V , A ) y v ∈ V . El grado de entrada de v se denota grados − ( v ) y su grado exterior se denota grados + ( v ).
Un vértice con grados − ( v ) = 0 se llama fuente , ya que es el origen de cada uno de sus arcos salientes. De manera similar, un vértice con grados + ( v ) = 0 se llama sumidero , ya que es el final de cada uno de sus arcos entrantes.
La fórmula de suma de grados establece que, para un gráfico dirigido,
Si para cada vértice v ∈ V , grados + ( v ) = grados − ( v ) , la gráfica se llama gráfica dirigida balanceada . [8]
secuencia de grados
La secuencia de grados de un gráfico dirigido es la lista de sus pares de grados de entrada y de salida; para el ejemplo anterior tenemos una secuencia de grados ((2, 0), (2, 2), (0, 2), (1, 1)). La secuencia de grados es una invariante de gráfico dirigido, por lo que los gráficos dirigidos isomórficos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados no identifica, en general, de forma única un gráfico dirigido; en algunos casos, los dígrafos no isomorfos tienen la misma secuencia de grados.
El problema de realización de gráficos dirigidos es el problema de encontrar un gráfico dirigido con la secuencia de grados de una secuencia dada de pares de enteros positivos . (Los pares de ceros finales pueden ignorarse ya que se realizan trivialmente agregando un número apropiado de vértices aislados al gráfico dirigido). Una secuencia que es la secuencia de grados de algún gráfico dirigido, es decir, para la cual el problema de realización del gráfico dirigido tiene una solución. , se llama gráfico 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 gráfica dirigida
Un gráfico dirigido es 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 gráfico dirigido es fuertemente conexo o fuerte si contiene una ruta dirigida de x a y (y de y a x ) para cada par de vértices ( x , y ) . Los componentes fuertes son los subgrafos máximos fuertemente conectados.
Un gráfico raíz conectado (o gráfico de flujo ) es aquel en el que existe una ruta dirigida a cada vértice desde un vértice raíz distinguido .
^ 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.
^ a b C Chartrand, Gary (1977). Introducción a la teoría de grafos. Corporación de mensajería. ISBN 9780486247755. Archivado 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 las matemáticas y sus aplicaciones, vol. 108, Cambridge University Press, pág. 51, ISBN 978-0-521-86565-4.
^ Bang-Jensen y Gutin (2000) pág. 19 en la edición de 2007; pag. 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 está ahora 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 gráficos 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 gráficos dirigidos , Nueva York: Wiley.
