Gráfico orientado

En la teoría de grafos , un grafo dirigido es un par formado por un conjunto de nodos y un conjunto de arcos, cada arco está asociado con un par de nodos en una dirección representada por una flecha. ${\ Displaystyle G = (V, A)}$ $V$ $A$

Definiciones

Dado un arco , decimos que es el origen (o fuente) de y que es el final (o objetivo) de . $(x, y)$ $X$ $(x, y)$ $y$ $(x, y)$
El medio grado externo (grado de salida ) de un nodo, indicado , es el número de arcos que tienen este nodo como origen. ${\ Displaystyle d ^ {+} (x)}$
El medio grado interior (grado entrante ) de un nodo, indicado , es el número de arcos con ese nodo en su extremo. ${\ Displaystyle d ^ {-} (x)}$
Cada arco que tiene un origen y un solo extremo, la gráfica tiene tantos grados saliente de grados entrantes: . ${\ Displaystyle \ sum _ {x \ in V} d ^ {+} (x) = \ sum _ {x \ in V} d ^ {-} (x)}$
${\ Displaystyle x_ {1} x_ {2}, x_ {2} x_ {3}, \ cdots, x_ {n-1} x_ {n}}$ es un camino si y solo si es un arco; decimos que el camino es elemental si todos son distintos. ${\ Displaystyle \ forall p \ in \ {1,2, \ cdots, n-1 \}, (x_ {p}, x_ {p + 1})}$ $x_ {i}$
el camino es un circuito si y solo si es un arco. ${\ Displaystyle x_ {1} x_ {2}, x_ {2} x_ {3}, \ cdots, x_ {n-1} x_ {n}}$ ${\ Displaystyle (x_ {n}, x_ {1})}$
el gráfico es un subgráfico del gráfico dirigido si y solo si contiene . Más precisamente, si y solo si y . ${\ Displaystyle G '= (V', A ')}$ ${\ Displaystyle G = (V, A)}$ $GRAMO$ $G '$ ${\ Displaystyle G '\ subseteq G}$ ${\ Displaystyle V '\ subseteq V}$ ${\ Displaystyle A '\ subseteq \ {(x, y) \ in A \ mid x \ in V' \ wedge y \ in V '\}}$

El gráfico transpuesto de un gráfico dirigido se obtiene manteniendo todos los nodos de e invirtiendo todos los arcos de . En otras palabras, con . También hablamos de gráfico inverso. ${\ Displaystyle G ^ {T}}$ ${\ Displaystyle G = (V, A)}$ $V$ $A$ ${\ Displaystyle G ^ {T} = (V, A ^ {T})}$ ${\ Displaystyle A ^ {T} = \ {(y, x) \ mid (x, y) \ in A \}}$

Ejemplos relacionados con las figuras 1 y 2

el gráfico dibujado en la figura 1 está definido por y por . ${\ Displaystyle V = \ {1,2,3,4 \}}$ ${\ Displaystyle A = \ {(1,2), (1,3), (3,2), (3,4), (4,3) \}}$
el grado saliente . Dos arcos se originan en el nodo . ${\ Displaystyle d ^ {+} (1) = 2}$ $1$
el grado entrante . Ningún arco termina en el nudo . ${\ Displaystyle d ^ {-} (1) = 0}$ $1$
${\ Displaystyle 1,3,2}$ es una ruta del gráfico (desde y pertenece a ). $GRAMO$ ${\ Displaystyle (1,3)}$ $(3,2)$ $A$
${\ Displaystyle 3,4}$ es un circuito de la gráfica (y es el único circuito elemental si lo identificamos con el circuito ), porque los arcos y pertenecen a . $GRAMO$ ${\ Displaystyle (4.3)}$ ${\ displaystyle (3,4)}$ ${\ Displaystyle (4.3)}$ $A$
${\ Displaystyle G '= (\ {1,2,3 \}, \ {(1,3), (3,2) \})}$ es un subgrafo de . $GRAMO$
${\ Displaystyle G ^ {T} = (\ {1,2,3,4 \}, \ {(2,1), (3,1), (2,3), (4,3), (3 , 4) \})}$ es la transposición de . $GRAMO$

Modelado de gráficos dirigido

Los gráficos dirigidos son modelos para diversas situaciones.

Sistemas viales con calles de un solo sentido, sistemas de transporte asimétricos ...
Gráficos de estado que mezclan transiciones reversibles e irreversibles (ejemplo: autómatas de estado finito) .
El flujo de control de un programa.
Las redes de flujo son gráficos dirigidos cuyos arcos están etiquetados por capacidades.

Notas y referencias

Se utilizan ambos términos, véase Olivier Carton, “ Algorithmes sur les graphes ” para gráfico transpuesto, y Jean-Charles Régin y Arnaud Malapert, “ Théorie des graphes ” , para gráfico inverso.

Bibliografía

Claude Berge , Teoría de grafos y sus aplicaciones , Paris, Dunod,1958, 275 p. ( OCLC 780360 ).