En matemáticas , y más específicamente en teoría de grafos , un grafo dirigido (o dígrafo ) es un grafo que se compone de un conjunto de vértices conectados por aristas dirigidas a menudo llamadas arcos .
Definición
En términos formales, una gráfica dirigida 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 de vértices desordenados , que suelen denominarse aristas , enlaces o líneas .
La definición mencionada anteriormente no permite que un gráfico dirigido para tener múltiples flechas con la misma fuente y de destino nodos, pero algunos autores consideran una definición más amplia que permite dirigida gráficas para tener tales múltiples arcos (es decir, permiten que el conjunto de arco para ser un conjunto múltiple ) . Más específicamente, estas entidades se abordan como multigrafos (o multidigrafos ) dirigidos .
Por otro lado, la definición antes mencionada permite que un gráfico dirigido tenga bucles (es decir, arcos que conectan directamente los nodos con ellos mismos), pero algunos autores consideran una definición más estrecha que no permite que los gráficos dirigidos tengan bucles. [2] Más específicamente, los gráficos dirigidos sin bucles se tratan como gráficos dirigidos simples , mientras que los gráficos dirigidos con bucles se tratan como dígrafos de bucles (consulte la sección Tipos de gráficos dirigidos ).
Tipos de gráficos dirigidos
Subclases
- Los gráficos dirigidos simétricos son gráficos dirigidos donde todos los bordes son bidireccionales (es decir, para cada flecha que pertenece al dígrafo, también le pertenece la flecha inversa correspondiente).
- Los gráficos dirigidos simples son gráficos dirigidos que no tienen bucles (flechas que conectan directamente los vértices entre sí) y no tienen flechas múltiples con los mismos nodos de origen y destino. Como ya se ha introducido, en el caso de múltiples flechas, la entidad se suele direccionar como multigraph dirigido . Algunos autores describen dígrafos con bucles como bucle dígrafos . [2]
- Los gráficos dirigidos completos son gráficos dirigidos simples donde cada par de vértices está unido por un par simétrico de arcos dirigidos (es equivalente a un gráfico completo no dirigido con los bordes reemplazados por pares de arcos inversos). De ello se deduce que un dígrafo completo es simétrico.
- Dígrafos multipartitas Semicomplete son dígrafos simples en el que el conjunto de vértices es partición en conjuntos tripartitos tales que para cada par de vértices x y y en diferentes conjuntos tripartitos, hay un arco entre x y y . Nota que no puede haber un arco entre x y y o dos arcos en las 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, donde el número de vértices es igual al número de conjuntos de partitos. [4]
- Dígrafos cuasi-transitivo son dígrafos simples donde por cada triple de x , y , z de vértices distintos con arcos de x a y desde y hacia y a z , hay un arco entre x y z . Nota que no puede haber sólo un arco entre x y z o dos arcos en direcciones opuestas. Un dígrafo semicompleto es un dígrafo cuasi transitivo. Hay extensiones de dígrafos cuasi transitivos llamados dígrafos k -cuasi transitivos. [5]
- Los gráficos orientados son gráficos dirigidos que no tienen bordes bidireccionales (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 solo si no tiene 2 ciclos . [6]
- Los torneos son gráficos orientados que se obtienen eligiendo una dirección para cada borde en gráficos completos no dirigidos . Tenga en cuenta que un torneo es un dígrafo semicompleto. [7]
- Los gráficos acíclicos dirigidos (DAG) son gráficos dirigidos sin ciclos dirigidos . [8]
- Los árboles múltiples son DAG en los que no hay dos caminos dirigidos distintos de un único vértice inicial que se reúnan en el mismo vértice final.
- Los árboles orientados o polytrees son DAG que se forman al orientar los bordes de gráficos acíclicos no dirigidos.
- Los árboles enraizados son árboles orientados en los que todos los bordes del árbol no dirigido subyacente se dirigen hacia afuera o hacia la raíz (se denominan árboles externos e internos , respectivamente).
Dígrafos con propiedades complementarias
- 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 gráficos dirigidos con raíces (también conocidos como gráficos 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 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 con un conjunto de ecuaciones algebraicas o diferenciales lineales.
- Los diagramas de estado son multigrafos dirigidos que representan máquinas de estados finitos .
- 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 los grupos de Lie , un carcaj Q es un grafo dirigido que sirve como el 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 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 dimensión finita espacios vectoriales más de 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 las transformaciones lineales entre ellos, y se transforman mediante transformaciones naturales .
Terminología básica
Un arco ( x , Y ) se considera para ser dirigido desde x a y ; y se llama la cabeza y x se llama la 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 de cables de x a y , a continuación, y se dice que es un sucesor de x y alcanzable de x , y x se dice que es un precursor de Y . El arco ( y , x ) se llama arco inverso 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 única hasta una permutación idéntica de filas y columnas.
Otra representación matricial para un gráfico dirigido es su matriz de incidencia .
Consulte la dirección para obtener más definiciones.
Indegree y outdegree
En el caso de un vértice, el número de extremos de cabeza adyacentes a un vértice se denomina grado de indecisión 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 árboles).
Deje que G = ( V , A ) y v ∈ V . El grado de v se denota deg - ( v ) y su grado exterior se denota deg + ( v ).
Un vértice con deg - ( v ) = 0 se llama fuente , ya que es el origen de cada uno de sus arcos salientes. De manera similar, un vértice con deg + ( v ) = 0 se llama sumidero , ya que es el final de cada uno de sus arcos entrantes.
La fórmula de la suma de grados establece que, para un gráfico dirigido,
Si para cada vértice v ∈ V , deg + ( v ) = deg - ( v ) , la gráfica se llama gráfica dirigida balanceada . [9]
Secuencia de grados
La secuencia de grados de una gráfica dirigida es la lista de sus pares de grado y grado; para el ejemplo anterior tenemos la secuencia de grados ((2, 0), (2, 2), (0, 2), (1, 1)). La secuencia de grados es un gráfico dirigido invariante, 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 isomórficos 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 una secuencia dada de pares enteros positivos . (Los pares de ceros finales se pueden ignorar, 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 el cual el problema de realización de un gráfico dirigido tiene una solución. , se denomina 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 de gráficos dirigidos
Un gráfico dirigido está débilmente conectado (o simplemente conectado [10] ) 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 conectado .
Un grafo dirigido está conectado fuertemente o fuerte si contiene un camino dirigido desde 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 enraizado conectado (o diagrama de flujo ) es aquel en el que existe una ruta dirigida a cada vértice desde un vértice raíz distinguido .
Ver también
- Relación binaria
- Gráfico de Coates
- Diagrama de flujo de DRAKON
- Diagrama de flujo
- Glosario de teoría de grafos
- Teoría de grafos
- Gráfico (tipo de datos abstracto)
- Teoría de redes
- Orientación
- Hacer un pedido
- Clasificación topológica
- Transponer gráfico
- Gráfico de restricción vertical
- Conjunto globular
Notas
- ^ 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.
- ↑ a b c Chartrand, Gary (1977). Introducción a la teoría de grafos . Corporación de mensajería. ISBN 9780486247755.
- ^ Bang-Jensen y Gutin (2018) , Capítulo 7 de Yeo.
- ^ Bang-Jensen y Gutin (2018) , Capítulo 2 de Bang-Jensen y Havet.
- ^ Bang-Jensen y Gutin (2018) , Capítulo 8 de Galeana-Sanchez y Hernandez-Cruz.
- ^ Diestel (2005) , sección 1.10.
- ^ Bang-Jensen y Gutin (2018) , Capítulo 2 de Bang-Jensen y Havet.
- ^ Bang-Jensen y Gutin (2018) , Capítulo 3 de Gutin.
- ^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Matemáticas discretas y teoría de grafos , PHI Learning Pvt. Ltd., pág. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Clases de matriz combinatoria , Enciclopedia de las matemáticas y sus aplicaciones, 108 , Cambridge University Press, p. 51 , ISBN 978-0-521-86565-4.
- ^ Bang-Jensen y Gutin (2000) p. 19 en la edición de 2007; pag. 20 de la 2a 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 gráficos dirigidos , Springer , ISBN 3319718401.
- Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones , Holanda Septentrional, ISBN 0-444-19451-7.
- Diestel, Reinhard (2005), Graph Theory (3.a 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 los gráficos dirigidos , Nueva York: Wiley.
- Número de gráficos dirigidos (o gráficos dirigidos) con n nodos de la Enciclopedia en línea de secuencias de enteros