CONCEPTOS BÁSICOS

Grafo dirigido
Un grafo dirigido, o digrafo, es un par G = (V, E) donde V es un conjunto cuyos elementos se llaman vértices y E es un conjunto de pares ordenados de elementos de V. Los vértices también suelen llamarse nodos. Los elementos de E se llaman aristas, o aristas dirigidas, o arcos. Para la arista dirigida (v, w) en E, u es su cola y w es su cabeza; (v, w) se representa en los diagramas con la flecha v -> w, pero escribimos simplemente vw.

Por ejemplo, si V= {1,2,..., 10}, puede tenerse las siguientes aristas, E = {(1,2),..., (1,10), (2,4), (2,6), (2,8), (2,10), (3,6), (3,9), (4,8), (5,10)}.

Grafo no dirigido
Un grafo no dirigido es un par G = (V, E) donde las aristas en E denotan arista no dirigida. En los diagramas esta arista es la línea v-w (sin flecha). Desde luego, vw = wv en el caso de grafos no dirigidos.
Por ejemplo, si V = {SF, OAK, SAC, STK, FRES, LA, SD}, pueden tenerse las siguientes aristas, E = { {SF, STK}, {SF, SAC}, {SF, LA}, {SF, SD}, {SF, FRES}, {SD, OAK}, {SAC, LA}, {LA, OAK}, {LA, FRES}, {LA, SD}, {FRES, STK}, {SD, FRES}}

Subgrafo

Un subgrafo de un grafo G = ( V, E) es un grafo G' = ( V', E') tal que V' es un subconjunto de V y E' de E.

Camino

Un camino de v a w en un grafo G = (V,E) es una sucesión de aristas v0v1, v1v2, ......., vk-1vk, tal que v = v0 y vk = w. La longitud del camino es k. Un camino simple es un camino tal que v0, v1, ..., vk son todos distintos.

Ejemplo: Camino del nodo SD al nodo SAC.

Ciclo en un grafo

En un grafo dirigido, un ciclo no es más que un camino no vacío tal que el primer vértice y el último sean el mismo y un ciclo simple es un ciclo en el que ningún vértice se repite, con la seguridad de que el primero y el último son el mismo.

En un grafo no dirigido las definiciones son similares, pero con el requisito adicional de que si cualquier arista aparece más de una vez, siempre aparece con la misma orientación

Un grafo es acíclico si no tiene ciclos.

Componente conectado

Un componente conectado de un grafo no dirigido G es un subgrafo de G que es máximo y está conectado.

Grafo ponderado

Es aquel que inlcuye un "peso" o costo en cada una de sus aristas, es representativo y ayuda a tener una visión más amplia y adecuada para la resolución de problemas.