Grafos

Formalmente, un grafo G consiste en dos conjuntos finitos V y A. V es el conjunto de elementos del grafo, también denominados vértices o nodos. A es el conjunto de arcos, que son las conexiones quese encargan de relacionar los nodos para formar el grafo. Los arcos también son llamados aristas o líneas.
Los nodos suelen usarse para representar objetos y los arcos para representar la relaciónentre ellos. Por ejemplo, los nodos pueden representar ciudades y los arcos la existencia de carreteras que las comunican.
Cada arco queda definido por un par de elementos a1, a2 ∈ V a los queconecta.
Aunque habitualmente los elementos son distintos, permitiremos que sean el mismo nodo (n1= n2). Representaremos gráficamente un arco como una línea que une los dos nodos asociados.

Figura 1.Si queremos representar mediante un grafo la red de vuelos de una compañía aérea entre diferentes ciudades, tendríamos el siguiente grafo G = {V, A}; V = {Málaga, Zaragoza, Madrid, Barcelona}; A ={(Madrid, Málaga), (Madrid, Barcelona), (Málaga, Barcelona), (Zaragoza, Barcelona)}. La representación gráfica sería la de la figura 1.

Se dice que dos nodos son adyacentes o vecinos si hay un arcoque los conecta. Los nodos adyacentes pueden ser representados por pares (a, b).
Un camino es una secuencia de nodos a1, a2,..., am tal que ∀i, 1 ≤ i ≤ (m-1), cada par de nodos (ni, ni+1) sonadyacentes. Se dice que un camino es simple si cada uno de sus nodos, excepto tal vez el primero y el último, aparece sólo una vez en la secuencia.
La longitud de un camino es el número de arcos de esecamino. Se puede considerar como caso especial un nodo por sí mismo como un camino de longitud 0.
Un ciclo es un camino simple en el que el primer y último nodos son el mismo (n1 = nm). Si un caminodesde un nodo a él mismo no contiene otros nodos entonces decimos que es un ciclo degenerado.
Un grafo sin ciclos se dice acíclico.
Si en un grafo G = {V, A}, V está formado por dos o más...