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 llamados arcos .
Se diferencia de un grafo ordinario o no dirigido , en que este último se define en términos de pares desordenados de vértices, que suelen denominarse aristas , enlaces o líneas .
La definición antes mencionada no permite que un gráfico dirigido tenga varias flechas con los mismos nodos de origen y de destino, pero algunos autores consideran una definición más amplia que permite 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 lazos (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 lazos. [2]
Los gráficos dirigidos sin bucles pueden llamarse gráficos dirigidos simples, mientras que los gráficos dirigidos con bucles pueden llamarse dígrafos de bucle (ver la sección Tipos de gráficos dirigidos ).
Se considera que un arco ( x , y ) está dirigido de x a y ; y se llama la cabeza y x se llama la cola del arco; y se dice que es un sucesor directo de x y x se dice que es un predecesor directo de y . Si un camino lleva de x a y , entonces se dice que y es un sucesor de x yaccesible 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 una matriz lógica y es única hasta la permutación de filas y columnas.
Para un vértice, el número de extremos de cabeza adyacentes a un vértice se denomina grado interior del vértice y el número de extremos de cola adyacentes a un vértice es su grado exterior (llamado factor de ramificación en árboles).
