Estructuras de datos en red: los grafos

Estructuras de datos en red: los grafos

Siguiendo con nuestro curso de programación hoy introduciremos los conceptos básicos sobre los grafos, un tipo de estructura de datos. Podemos definir los grafos como un conjunto de vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

ejemplo_grafo

El estudio de los grafos se estudia en una teoría o disciplina denominada teoría de grafos. La teoría de grafos es una teoría vital en el mundo de la informática en la que se tratan no solo temas relacionados con las características o los tipos de grafos, si no con su implementación mediante un lenguaje de programación.

Representación de los grafos

Para representar un grafo podemos usar varios tipos de estructuras:

  • Estructura de lista: como pueden ser las lista de adyacencia donde cada vértice tiene una lista de vértices los cuales son adyacentes a él.
  • Estructura de matris: como pueden ser las matrices de adyacencia donde el grafo está representado por una matriz cuadrada M de tamaño n cuadrado, donde n es el número de vértices.

Si nos fijamos, para la construcción de estructuras complejas tendremos que utilizar otras estructuras más simples, las listas, esto no siempre será así, ya que por ejemplo, con las estructuras jerárquicas (en concreto algunos tipos de árboles como los binarios de búsqueda) se utilizarán referencias o punteros. Las matrices son también estructuras de datos más complejas que se forman mediante listas de elementos. Nosotros utilizaremos las matrices de adayacencia, ya que estas matrices son especialmente útiles en el caso de grafos densos. Los grafos densos son aquellos grafos que tienen varias aristas por cada nodo.

Conceptos básicos

  • Grado de un nodo: Número de arcos u aristas conectados al nodo.
  • Grado de Entrada (gE) de un nodo: Número de arcos o aristas que tienen al nodo como destino.
  • Grado de Salida (gS) de un nodo: Número de arcos o aristas que tienen al nodo como origen.
  • Nodo fuente: Si cumple que GradoSalida > 0 y GradoEntrada = 0
  • Nodo sumidero: Si cumple que GradoSalida = 0 y GradoEntrada > 0.
  • Nodo aislado: Si cumple que GradoSalida = 0 y GradoEntrada = 0.
  • Capacidad de un grafo: n = número de nodos de un grafo.
  • Camino Simple entre dos nodos Vi, Vj (Vi ≠ Vj): Es aquel camino en el que no se repite ningún nodo.
  • Excentricidad: La excentricidad de un nodo V es el máximo de los costes de todos los caminos de coste mínimo con destino V.
  • Nodo centro de un grafo: será aquel nodo de mínima excentricidad.

Estos conceptos serán aplicables al grafo que nosotros implementemos mediante los métodos. Cada uno de estos conceptos los representaremos mediante un método que nos permitirá añadirle funcionalidad a nuestro grafo.

Tipos de grafos

  • Grafo simple. o simplemente grafo es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.
  • Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.
  • Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha
  • Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.
  • Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.
  • Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.
  • Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Es importante dejar claro que algunos de los tipos no son restrictivos, un grafo puede poseer varios tipos. Nosotros nos centraremos en el desarrollo e implementación de un grafo simple, dirigido y etiquetado ya que por lo general son los grafos más utilizados, y los que nos permiten un menor nivel de abstracción posibilitándonos una forma sencilla de representarlos. Por ejemplo (como vemos en la imagen del artículo) podemos usar este grafo simple, dirigido y etiquetado para indicar el coste de las carreteras que unen unas determinadas ciudades. Estas ciudades serán los nodos y las carreteras serán las aristas.

En los siguientes artículos trataremos de implementar estos grafos mediante el lenguaje de programación C# y de paso ampliaremos nuestros conocimientos en pruebas unitarias para comprobar que este grafo que desarrollemos se ajuste al que hemos tratado de definir.

Para ti
Queremos saber tu opinión. ¡Comenta!