Un grafo G agrupa entes físicos o conceptuales y las relaciones entre ellos. Por tanto, un grafo está formado por un conjunto de vértices o nodos V, que representan a los entes, y un conjunto de arcos A.

Un grafo G agrupa entes físicos o conceptuales y las relaciones entre ellos. Por tanto, un grafo está formado por un conjunto de vértices o nodos V, que representan a los entes, y un conjunto de arcos A. Estos arcos representan las relaciones entre vértices. Un arco o arista representa una relación entre dos nodos. Esta relación, al estar formada por dos nodos, se representa por (u, v) siendo u, v el par de nodos. Estos grafos pueden ser pesados o no pesados y esta calificación se denomina grafo ponderado.

Al modelar un conjunto de objetos y sus relaciones mediante un grafo, una de las cuestiones, que generalmente interesa saber es si desde cualquier vértice se puede acceder al resto de los vértices del grafo, es decir, si todos los vértices están conectados, o simplemente, si el grafo es conexo. Para un grafo dirigido, la conectividad entre todos los vértices se denomina:  grafo fuertemente conexo

Los grafos son valorados o no valorados y ambos poseen caminos; La longitud de un camino en un grafo no valorado es el número de arcos en el camino mientas que en un grafo valorado la longitud del camino con pesos es la suma de los pesos de los arcos en el camino.

Historia

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. El problema planteaba lo siguiente: ¿Es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?

Si definimos como “grado” al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez sí, salvo a lo sumo dos, todos los puntos tienen un grado par.

Representación de grafos

Matriz de adyacencia

La característica más importante de un grafo, es el conjunto de pares de vértices que están relacionados, o que son adyacentes. La forma más sencilla de representar un grafo es mediante una matriz, de tantas filas / columnas como nodos, que permite modelar fácilmente esa cualidad. La matriz de adyacencia representa los arcos, las relaciones ente un par de nodos de un grafo. En un grafo valorado cada elemento representa el peso de la arista, y por ello se denomina matriz de peso.

Lista de adyacencia

La representación de un grafo con matriz de adyacencia no es eficiente cuando el grafo es poco denso, (disperso), es decir tiene pocos arcos y, por tanto, la matriz de adyacencia tiene muchos ceros.  Para grafos dispersos la matriz de adyacencia ocupa el mismo espacio que si el grafo tuviera muchos arcos (grafo denso).  Cuando esto ocurre, se elige la representación del grafo mediante listas enlazadas, denominadas listas de adyacencia. Las listas de adyacencia son una estructura multi enlazada formada por una tabla directorio donde cada elemento de la tabla representa un vértice del grafo, del que emerge una lista enlazada con todos sus vértices adyacentes.

Propiedades

• Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
• Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
• Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
• Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Bibliografía

• Wikipedia®. (29 de mayo de 2015). Obtenido de https://es.wikipedia.org/wiki/Grafo

• Medium. (23 de novimbre de 2017). Obtenido de https://medium.com/@matematicasdiscretaslibro/cap%C3%ADtulo-11-teoria-de-grafos-3b00228dd81c

•  Grapheverywhere. (2015). Obtenido de https://www.grapheverywhere.com/que-son-los-grafos/