GRAFOS

GRAFOS Y SUS APLICACIONES

Proposición 8.1: un grafo  es conexo si y solo si existe un camino simple entre cualesquiera dos nodos de G.

Se dice que un grafo g es completo si cada nodo u de g es adyacente a todos los demás nodos  de g. claramente, un grafo así es conexo. Un grafo completo de n nodos tendrá n(n-1)­­/2 aristas. Un grafo conexo t sin ciclos se llama grafo árbol o árbol libre o simplemente árbol.

Un grafo g se dice que esta etiquetado si sus aristas tienen datos asignados. En particular, se dice g tiene peso si cada arista  e de g tiene asignado un valor numérico  no negativo w(e) llamado peso o longitud  de e. en ese caso, a cada camino p de g se le asigna un peso o una longitud que es la suma de los pesos de las aristas que constituyen el camino p.

La definición de un grafo puede ser generalizada si permitimos lo siguiente:

1)    aristas múltiples. dos aristas e y e’ distintas se llaman aristas múltiples si conectan los mismos extremos, o sea, si e=[u,v] y e´=[u,v].

2)    bucles. una arista e se llama bucle si tiene extremos idénticos, o sea, si e=[u,v].

Tal generalización M se llama multígrafo. en otras palabras, la definición de un grafo normalmente no permite ni aristas múltiples ni bucles.
Un multígrafo M se dice que es finito si tiene un numero finito de nodos y de aristas. observe que un grafo g con un numero finito de nodos debe automáticamente tener un numero finito de aristas y por tanto debe ser finito; pero esto no es necesariamente cierto para un multígrafo M, ya que M puede tener múltiples aristas. A menos que se indique lo contrario, los grafos y multígrafos de este texto serán finitos.