!Comencemos¡
¿Que es un Grafo?

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser: un gráfico de una serie de tareas a realizar, grafos matematicos que representan las relaciones binarias,una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad, una red de trabajo en un oficina. En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos). 

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes b
loques:

• Grafos Dirigidos.
• Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

 A la hora de diseñar el TDA grafo hay que tener en cuenta que hay que manejar datos correspondientes a sus vértices y aristas,  pudiendo cada uno de ellos estar o no etiquetados. Además hay que proporcionar operaciones primitivas que permitan manejar el tipo de dato sin necesidad de conocer la implementación. Así,los tipos de datos que se usarán y las operaciones primitivas consideradas son las siguientes: 

Los nuevos tipos aportados por el TDA grafo son los siguientes:

• grafo.
• vertice.
• arista.

Representación de grafos

Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptarán tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso o disperso.

Para nombrar los nodos utilizaremos letras mayúsculas, aunque en el código deberemos hacer corresponder cada nodo con un entero entre 1 y N (número de vértices) de cara a la manipulación de los mismos.

Representación por matriz de adyacencia

Es la forma más común de representación y la más directa. Consiste en una tabla de tamaño N x N, en que la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor será 0. Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el peso de la arista. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 (o con el peso) tanto la entrada a[i][j] como la entrada a[j][i], puesto que se puede recorrer en ambos sentidos.

Representación por lista de adyacencia

Otra forma de representar un grafo es por medio de listas que definen las aristas que conectan los nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia al nodo A.

Las listas de adyacencia serán estructuras que contendrán un valor entero (el número que identifica al nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado

 A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.

En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.

 Algunos conceptos Claves

Grafos no dirigidos
Grado de un vertice: número de arista que lo contienen.

 

Grafos dirigidos:

Grado de salida de un vertice V: número de arcos cuyo vertice inicial es V

Grado de entrada de un vertice V: Número de vertices cuyo vertice final es V.

Nodos/vertices adyacentes: arcos/aristas con un vértice común.

 Bucle: arco/arista cuyo vértice inicial y final coinciden.

Camino: sucesión de arcos adyacentes tal que el vertice final de cada arco coincide con el inicial del siguiente.

Circuito o ciclo: camino que acaba y comienza con el mismo vertice.

Grafo conexo: un grafo no dirigido es un grafo conexo si para todo par de nodos U y V existe un camino de U a V.

Componentes conexas: cada uno de los conjuntos maximales conexos. 

 

TIPOS DE GRAFOS:

 Grafo Etiquetado: cada arista o vertice tiene asociado una etiqueta o valor.

Grafo Ponderado (grafo con pesos): grafo etiquetado en el que existe un valor numerico asociado a cada arista o arco.

Multigrafo: grafo en el que se permite que entre dos vertices exista mas de un arista o arco.

Arbol: grafo conexo que no tiene ciclos.