Grafos

    

     En la entrada de esta semana hablare un poco sobre el tema de grafos, que es un grafo y que aplicación se le ha dado a esto en el área de la computación.

     Para iniciar es importante definir que es un grafo, según el documento elaborado por Exposito Lopez Daniel, Abraham García Soto, Martin Gomez Antonio Jose y Joaquín Fernández Valdivia llamado “Grafos”; la palabra grafo es de origen griego y su significado etimológico es "trazar". Pero ¿qué es un grafo? En grandes rasgos un grafo es una representación gráfica de un conjunto de tareas que indican su secuencia. Observar en la siguiente figura.

Grafo.

     Pero los grafos funcionan para representar gran cantidad de gráficos desde las conexiones entre ciudades hasta coincidencias en cadenas de ADN.

     Bien una vez que conocemos que son y un poco de para qué sirven. Vamos a mencionar el uso que estos tienen en la computación.

     Según el libro antes mencionado los grafos en la computación son vistos de la siguiente manera: “son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

·         Grafos Dirigidos.

·         Grafos no Dirigidos.

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido. Por el contrario, la red de carreteras de un país representa en general un grafo

no dirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos. “

     Pero bueno ¿qué quiere decir que sean una estructura de datos no lineales y además generalmente dinámica? Esto lo que indica es que son una estructura de datos cuyos enlaces van al siguiente nodo, pero adema al anterior y que puede ir creciendo a medida que sea necesario o disminuyendo si así se necesita. Su definición se parece un poco a lo que es un árbol esto debido a que la estructura llamada árbol es un grafo solo que cumple con características puntuales que lo hacen ser un árbol y no un grafo, como lo es el hecho de que un nodo solo pueda tener un padre, entonces podemos decir que todo árbol es un grafo mas no todo grafo es un árbol.

     Algunos ejemplos de aplicaciones que utilizan la teoría de grafos son Facebook, en donde cada usuario es un nodo el cual se conecta con todos los amigos que tiene agregados, con las páginas que sigue y demás. Otro ejemplo es la exitosa aplicación WhatsApp donde cada número registrado es un nodo el cual tiene conexión con todos los contactos que tiene guardados además de todas las personas a las cuales les ha escrito al menos una vez. Con esos 2 ejemplos podemos observar todas las características antes mencionadas, pues los grafos son dinámicos y gracias a esto es que en Facebook se crean miles de nuevos perfiles por día y no son lineales por lo que los usuarios de WhatsApp pueden comunicarse de un lado hacia el otro.

     Como podemos observar esta es una estructura de datos sumamente versátil que nos permite solucionar gran cantidad de problemas, como la distribución de tareas, organización de horarios en una empresa y demás. Es una herramienta más que nos brinda la computación para dejar correr nuestra imaginación.

Fuentes:

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/grafos.htm

https://teoriadegrafos.files.wordpress.com/2008/11/conocidos.jpg