GRAFOS

CONCEPTO:

Un grafo es un conjunto de nodos con enlaces entre ellos, llamados aristas o arcos. Esto quiere decir que para expresar un grafo, es necesario hablar de los puntos (nodos) y aristas (arcos) que indican los diferentes nodos que se relacionan.

Sistema de Grafo utilizado para el Metro de Barcelona

Podemos tomar como ejemplo de un grafo. El metro de Barcelona, ya que muestra las diferentes conexiones que existen entre sus estaciones. Cuando hablamos de construcciones, edificaciones, montajes de red, es muy importante y necesario la implementación de grafos, pues si no existe una planificación gráfica y todos las variables que la conllevan, definitivamente estaríamos hablando de un proyecto sin base (inestable). Por ejemplo, si vamos a montar una red de internet local y el cliente nos pide que la implementemos en un local con espacio muy reducido, es iperativo que realicemos una planificación de los equipos que pueden adaptarse a su necesidad, el tipo de conexión, la ubicación de los equipos, los puntos de comunicación con el servidor base, la distancia entre equipos y todos los componentes  físicos que puedan afectar en gran manera la ejecución del proyecto.

VERTICE O NODO

Son los caminos o enlaces que existen entre los nodos que conforma el grafo.


ARCO O ARISTA

Son los puntos que conectan cada enlace del grafo.

Grafo con 7 aristas y 6 vértices

visualizar reglas para crear grafos

MATRIZ DE ADYACENCIA: Se asocian filas y columnas a cada nodo del grafo. Por ejemplo del siguiente grafo, determinar la matriz de adyacencia.

LISTA DE ADYACENCIA: Listado de nodos que sean adyacentes al primero. Por ejemplo del siguiente grafo, determinar la lista de adyacencia.

GRAFOS EULERIANOS

Un circuito que contiene todas las aristas, recibe el nombre de circuito euleriano. Quiere decir que un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice, pasa por cada vértice al menos una vez y sólo una vez por cada arista

Ejemplo: C = {1,2,3,4,6,3,5,4,1} es un grafo euleriano, porque recorre todas las aristas sin repetir ninguna, pero si puede repetir los nodos.

El origen de los ciclos eulerianos inició con el propio Leonhard Euler en 1736 en un problema llamado Siete puentes de la ciudad de Königsberg.

El problema dice: Dos islas, se unen entre ellas mediante siete puentes. ¿Es posible recorrer cada puente una sola vez, sin repetirlo, llegando a su estado inicial?

Euler, llega a la conclusión que no es posible, ya que el numero de líneas no es par.

Ejercicio: De los siguientes grafos determine cual es euleriano.

a) No es euleriano porque tiene un vértice separado.
b) No es euleriano porque al tomar cualquier ciclo, necesariamente pasa 2 veces por la arista.
c) El grafo es euleriano, ya que pasa por las 2 aristas sin repetirlas.
d) El grafo es euleriano, ya que pasa por las 3 aristas sin repetirlas.
e) No es euleriano ya que al pasar por todas las aristas repite uno de los vértices.


GRAFOS HAMILTONIANOS

Un circuito hamiltoniano es un ciclo simple, que contiene todos los vértices. Es decir, que un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vértice, no tiene aristas repetidas y pasa por cada vértice una sola vez.

Ejemplo: Demostrar el siguiente grafo que tiene un ciclo hamiltoniano:

Al recorres los vértices en ese orden, tenemos un ciclo de hamilton. a,b,c,d,e,a

Ejercicio: Determine el recorrido que debe hacer el caballo en un tablero de ajedrez, sin pasar 2 veces por el mismo camino.

Para culminar con el tema de grafos, veamos un breve resumen y otros temas relacionados, en el siguiente video: http://www.youtube.com/watch?v=tNelu-8Fhmw