Gráfico dirigido
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 .
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 tratan 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 comográ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 ).
Se considera que un arco ( x , y ) está dirigido de xay ; y se llama cabeza yx se llama 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 xay , entonces se dice que y es un sucesor de xy alcanzable desde x , y se dice que x es un predecesor 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.
Para un vértice, el número de extremos de la cabeza adyacentes a un vértice se llama el grado de indegrado del vértice y el número de extremos de la cola adyacentes a un vértice es su grado exterior (llamado factor de ramificación en los árboles).
