Definición.

La teoría de grafos tiene su origen en el año 1736 cuando Leonhard Euler publicó un trabajo que daba seguimiento al problema conocido como “Los puentes de Königsberg”. Dicho problema surgió en la ciudad de Prusia (en la actualiad Kaliningrado, Rusia), donde el río Pregel recorre el poblado y también dos islas (de nombre Kneiphof) que están en el centro, causando que la ciudad quede dividida en cuatro partes: dos regiones a cada lado del rio y las islas de en medio; todas ellas unidas por siete puentes. La siguiente imagen ejemplifica las regiones del lugar:



Ante esta situación, muchas personas comenzaron a averiguar si era posible cruzar los siete puentes pasando solamente una vez por cada uno de ellos. Euler demostró que esto no era posible, y para probarlo elaboró un modelo con un grupo de puntos que representaban las áreas de tierra y líneas que simbolizaban los puentes; fue así como surgió el primer ejemplo de un grafo.



Tomando como referencia la segunda imagen, las flechas indican el camino que se toma para recorrer los cuatro puntos y, como se puede notar, es necesario cruzar al menos dos veces por algunos enlaces para poder cumplir el ciclo.

A partir del trabajo de Euler, la teoría de grafos fue convirtiéndose en una útil herramienta para crear modelos en temas tan dispares como las matemáticas, la química, la física, las telecomunicaciones, internet, la economía, el estudio de probabilidades, temas de planificación, sistemas GPS, en redes neuronales, en programación, etc; propiamente en gran parte de la Informática aparecen los grafos, especialmente los grafos de árbol y los grafos dirigidos. Los diagramas de flujo, por ejemplo, son grafos dirigidos.

Enfocando la teoría de grafos a la informática, se puede elaborar un sencillo ejemplo: Representar una red de comunicaciones donde la colocación ideal de los elementos evite interrupciones accidentales, en otras palabras, que no haya desconexión de la red. El siguiente grafo expone que no existe ninguna línea que, al ser eliminada, desconecte la red.



Conceptos generales.

Se puede definir al grafo1 como una representación abstracta de las relaciones (denominadas “aristas” o “arcos”) entre una serie de puntos (denominados “nodos” o “vértices”). Por su parte, la teoría de grafos2 es la disciplina que estudia los diferentes tipos de grafos, sus propiedades y los múltiples problemas relacionados a su análisis, manipulación y visualización.

Un nodo3 es la unidad básica de la que están formados los grafos, generalmente se representan por un punto. Una arista4 es la relación (unión) entre dos nodos de un grafo. Dos nodos son adyacentes5 si hay una arista que los conecte. Si un nodo es conecta consigo mismo se dice que existe un lazo6; y cuando un nodo no está conectado a ningún otro se denomina como nodo aislado7. También hay casos donde dos nodos están unidos por más de una arista, a esto se le conoce como aristas múltiples8 o paralelas.



Se dice que un grafo es completo cuando cada nodo es adyacente a todos los demás, es decir, que todos los nodos se conecten entre ellos, ejemplo:



Los grafos pueden ser representados por matrices, mismas que se les conoce como matriz de adyacencia1. Una matriz de adyacencia no es mas que una matriz cuadrada de n filas por n columnas; n representa el número de nodos del grafo. Para construirlo, se agrega el valor 1 cuando dos nodos están conectados y el valor 0 cuando no es así:



Un ejemplo de una matriz de adyacencia y su respectivo grafo es el siguiente:



En la ilustración anterior, la matriz de adyacencia está del lado izquierdo y su grafo del lado derecho; se generaron una serie de "checkbox" para representar los 1 y 0, si tiene una selección verde (palomita) equivale a 1 y en caso contrario equivale a 0.


Grafo Dirigido.

Los grafos dirigidos son aquellos cuyas aristas están orientadas (generalmente representadas por flechas), es decir, los nodos tienen una dirección definida. También se les conoce como digrafos.



Todo grafo dirigido puede representarse con una matriz de adyacencia. Si un nodo se dirige hacia otro se escribe 1, y cuando no es así se coloca 0.



Grafo No Dirigido.

Por otro lado, los grafos no dirigidos no tienen la dirección de sus aristas definida, es decir, están sin orientar.



Los grafos no dirigidos también pueden representarse en una matriz de adyacencia, el 1 se coloca cuando hay conexión y 0 cuando no es el caso.



Subgrafos.

Un subgrafo no es más que un grafo cuya definición de nodos y aristas están basados en un subconjunto de un grafo “padre”.



Todos los grafos pueden generar algún tipo de subgrafo, esto es porque de ellos se derivarían otros grafos más pequeños para ejemplificar situaciones. Tomando como base la Figura 11, podría decirse que el grafo “Padre” representa la conexión entre diversas computadoras de un laboratorio, y el subgrafo consecuente únicamente representa la unión entre las computadoras que están compartiendo algún archivo, a través de la red, en ese momento.



Bibliografía:

  • a) Jordan, C. (1996). "Introducción a la teoría de grafos y sus algoritmos". España: Universidad Politécnica de Valencia Servicio de Publicaciones.
  • b) Vieites Rodríguez, A. (2014). "Teoría de grafos". Madrid: Paraninfo.
  • c) Caicedo, A. (2010). Introducción a la Teoría de Grafos. Armenia. Ediciones Elizcom.


Consulta electrónica:

  • a) Cancela, H. (2009). “Curso de Bioinformática”. Recuperado el 8 de marzo de 2017. Disponible en: https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/index.html

Ejercicios

Consultar el listado de ejercicios propuestos.

Acceder