Los grafos aparecen como una extensión del concepto de árbol, ya que en este nuevo tipo de estructuras cada elemento puede tener, además de más de un sucesor, varios elementos predecesores.
Esta propiedad hace a los grafos las estructuras más adecuadas para representar situaciones donde la relación entre los elementos es completamente arbitraria, como pueden ser mapas de carreteras, sistemas de telecomunicaciones, circuitos impresos o redes de ordenadores.
Cómo se conforma un grafo?
Formalmente, un grafo G consiste en dos conjuntos finitos N y A . N es el conjunto de elementos del grafo, también denominados vértices o nodos . A es el conjunto de arcos , que son las conexiones que se encargan de relacionar los nodos para formar el grafo. Los arcos también son llamados aristas o líneas .
Vértice o nodo
Los nodos suelen usarse para representar objetos y los arcos para representar la relación entre 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 n 1 , n 2 ∈ N a los que conecta. Aunque habitualmente los elementos son distintos, permitiremos que sean el mismo nodo (n 1 = n 2 ). Representaremos gráficamente un arco como una línea que une los dos nodos asociados.
Arco
Un arco o una arista corresponde a una relación entre dos vértices de un grafo.
Tipos de grafos (dígrafo y no dirigido)
Un grafo dirigido se podría usar para representar bloques de un programa mediante los nodos y la transferencia del flujo de control mediante los arcos.
Un nodo N se dice alcanzable desde un nodo M si y sólo si existe un camino desde M hasta N . Más formalmente, un nodo N se dice alcanzable desde un nodo M si:
(1) N y M son el mismo nodo, o
(2) N es alcanzable desde algún nodo que sea sucesor de M .
Para cada nodo de un grafo existe un conjunto de nodos alcanzables desde ese nodo, denominado conjunto alcanzable .
Un nodo N se dice directamente alcanzable desde un nodo M si y sólo si son adyacentes y N es el sucesor de M .
Un grafo conexo acíclico no dirigido es un árbol libre . Un árbol libre puede convertirse en un árbol general si se elige cualquier nodo deseado como raíz y se orienta el cada arco desde ella.
Los árboles libres tienen dos propiedades interesantes:
-Todo árbol libre con n nodos tiene exactamente n-1 arcos.
- Si se agrega cualquier arco a un árbol libre, se genera un ciclo.
En que consiste el camino en un grafo?
Un camino es una secuencia de nodos n 1 , n 2 , ..., n m tal que ∀ i, 1 ≤ i ≤ (m-1), cada par de nodos (n i , n i+1 ) son adyacentes. 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 ese camino. 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 (n 1 = n m ). Si un camino desde un nodo a él mismo no contiene otros nodos entonces decimos que es un ciclo degenerado .
