Grafo 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.

Definición

En términos formales, un grafo dirigido es un par ordenado G = (V, A) donde

• 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 denominado 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 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). Más específicamente, estas entidades se tratan como multigrafos dirigidos (o multidigraphs).Por otro lado, la definición anterior 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. 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 bucle (ver la sección Tipos de gráficos dirigidos).

Tipos de grafos dirigidos

Subclases

• Los grafos dirigidos simétricos son grafos dirigidos donde todas las aristas son bidireccionales (es decir, por cada flecha que pertenece al dígrafo, también le pertenece la flecha invertida correspondiente).
• Los gráficos dirigidos simples son gráficos 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 introdujo, en el caso de flechas múltiples, la entidad generalmente se trata como multigrafo dirigido. Algunos autores describen los dígrafos con bucles como loop-digraphs.
  • 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.
  • Los dígrafos multipartitos semicompletos son dígrafos simples en los que el conjunto de vértices se divide en conjuntos de particiones, de modo que para cada par de vértices x e y en diferentes conjuntos de particiones, hay un arco entre x e y. Tenga en cuenta que puede haber un arco entre xey o dos arcos en direcciones opuestas.
  • 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 partículas.
  • Los dígrafos cuasi-transitivos 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. Tenga en cuenta que puede haber solo 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 k -dígrafos cuasi-transitivos.
  • 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 grafo dirigido es un grafo orientado si y solo si no tiene 2 ciclos.
    • Los torneos son gráficos orientados que se obtienen eligiendo una dirección para cada arista en gráficos completos no dirigidos. Tenga en cuenta que un torneo es un dígrafo semicompleto.
    • Los gráficos acíclicos dirigidos (DAG) son gráficos dirigidos sin ciclos dirigidos.
      • Los multiárboles son DAG en los que no hay dos caminos dirigidos distintos desde un solo vértice inicial que se reencuentren en el mismo vértice final.
      • Los árboles orientados o poliárboles son DAG formados 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 están dirigidos hacia o desde la raíz (se denominan árboles externos e internos, respectivamente).

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).
  • Las redes de flujo son grafos 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 enraizados 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 (aristas, 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 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 el mismo 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 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 funtores FinVct _K 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

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 y accesible desdex, 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 la permutación idéntica 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 interior y exterior

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).

Sea G = (V, A) y v ∈ V. El grado interior de v se denota grado (v) y su grado exterior se denota grado (v).

Un vértice con grado (v) = 0 se llama fuente, ya que es el origen de cada uno de sus arcos salientes. De manera similar, un vértice con grado (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 todo vértice v ∈ V, grado (v) = grado (v), el grafo se llama grafo dirigido balanceado.

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 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, en general, no identifica 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 de manera trivial 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 denomina gráfica dirigida 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 conectado (o simplemente conectado) 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 gráfico 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 máximos fuertemente conectados.

Un grafo enraizado conectado (o grafo de flujo) es aquel en el que existe una ruta dirigida a cada vértice desde un vértice raíz distinguido.