Toyo

grafos dirigidos:
Son grafos con aristas orientadas en una dirección. Son útiles en sistemas dinámicos como computadoras digitales o sistemas de flujo.
Un grafo dirigido G, o dígrafo, consta de dos partes:
* Un conjunto V cuyos elementos ordenados se denominan vértices, nodos o puntos.
* Un conjunto E de pares ordenados (u, v) de vértices que se denominan arcos, aristas o aristasdirigidas.
En caso contrario que en grafos no dirigidos donde (u, v) = (v, u), para un dígrafo e= (u, v) usando la terminología:
* “e” empieza en u y termina en v.
* “u” es el origen o punto inicial de e, y “v” es el destino o punto final de e.
* “u” es adyacente a “v” y “v” es adyacente a “u”.
* “v” es un sucesor de “u”.
a
b
c
g
d
f
e
A
B
C
D
G
Si las aristas y/o vérticesde un grafo dirigido G se etiquetan con algún tipo de datos, entonces G se denomina grafo dirigido etiquetado.

Las aristas a y b del grafo se dice que son paralelas ya que ambas inician en el mismo vértice y como llegada entran a un mismo vértice, la arista f es un lazo dirigido y el grafo en general es un multigrafo dirigido.
grados de un vertice:
El grafo de salida de un vértice v de G,es el número de aristas que empiezan en v, y el grado de entrada de v es el número de aristas que terminan en v.
Teorema:
La suma de los grados de salida de los vértices de un grafo dirigido G es igual a la suma de los grados de entrada de los vértices, que es igual al número de aristas en G.
Un vértice v con grado de entrada cero (0) se denomina fuente y un vértice con grado de salida cero (0)se denomina sumidero.
caminos:
Los conceptos de camino, camino simple, recorridos y ciclos validos para grafos no dirigidos se aplican a los grafos dirigidos, excepto que las direcciones de las aristas deben coincidir con la dirección del camino.
A manera de resumen tenemos:
* Un camino dirigido p en G es una secuencia alterna de vértices y aristas dirigidas p=( V0, e1, v1, e2, v2,…,en,vn), tal que la arista ei empieza en vi-1 y termina en vi.
* La longitud del camino p es n, su número de aristas.
* Un camino simple es un camino con vértices distintos. Un recorrido es un camino con aristas distintas.
* Un camino cerrado tiene los mismos vértices inicial y final.
* Un camino de expansión contiene todos los vértices de G.
* Un ciclo es un camino cerrado convértices distintos (excepto inicial y final).
* Un semicamino es lo mismo que un camino, excepto que la arista ei puede empezar en vi-1 o en vi y terminar en el otro vértice. Los semirecorridos y los caminos semisimples se definen en forma análoga.
Conectividad de un grafo dirigido:
En un grafo dirigido G hay tres tipos de conectividad:
1. G es fuertemente conexo o fuerte si para cualquier parde vértices u y v en G, hay un camino de u a v y un camino de v a u; es decir, cada uno es alcanzable desde el otro.
2. G es unilateralmente conexo o unilateral si para cualquier par de vértices u y v en G, hay un camino de u a v o un camino de v a u; es decir, uno de ellos es alcanzable desde el otro.
3. G es débilmente conexo o débil si entre cualquier par de vértices u y v en G hay unsemicamino.
Sea G´ el grafo no dirigido que se obtiene a partir de un grafo dirigido G al dejar que todas las aristas de G sean no dirigidas. Resulta evidente que G es débilmente conexo si y sólo si el grafo G´ es conexo.
Observe que fuertemente conexo implica unilateralmente conexo, lo cual implica débilmente conexo. Se dice que G es estrictamente unilateral si es unilateral pero no fuerte, yse dice que G es estrictamente débil si es débil pero no unilateral.
La conectividad puede expresarse en términos de caminos de expansión según el teorema:
Sea G un grafo dirigido finito. Entonces:
I. G es fuerte si y sólo si G tiene un camino de expansión cerrado.
II. G es unilateral si y sólo si G tiene un camino de expansión.
III. G es débil si y sólo si G tiene un camino de...