En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas).
Teoría de grafos
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas).
¿Qué es un grafo exactamente?
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de conexiones, llamadas aristas que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Estructuras de datos en la representación de grafos
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices.
Estructura de lista
- Listas de incidencia: Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.
- Listas de adyacencia: Cada vértice tiene una lista de vértices los cuales son adyacentes a él.
Estructuras matriciales
- Matriz de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado)
- Matriz de adyacencia: El grafo está representado por una matriz cuadrada M de tamaño n ala dos, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es m sub x, y es 1, de lo contrario, es 0.
Clasificación de grafos por sus características
Grafos Simples
Son aquellos que surgen cuando una única arista logra unir dos vértices.
Grafos complejos
Presentan más de una arista en unión con los vértices.
Por otra parte, un grafo es conexo si dispone de dos vértices conectados a través de un camino. ¿Qué quiere decir esto?
Que, para el par de vértices (p, r), tiene que existir algún camino que permita llegar desde p hasta r.
En cambio, un grafo es fuertemente conexo si el par de vértices tiene conexión a través de, como mínimo, dos caminos diferentes.
Grafos dirigidos
Grafo en el que los arcos tienen sentido. Si los arcos no tienen sentido hablamos de un grafo no dirigido.
Grafo ponderado
Grafo en el que las aristas tienen un peso asociado.
Camino
Es un grafo en el que podemos nombrar a los nodos de modo que dos nodos están conectados si y solo si su diferencia es 1.
Árbol
Grafo conexo y sin ciclos.
Cuando se trabaja con grafos dirigidos etiquetados o ponderados con factores de peso no negativos, es frecuente buscar el camino más corto entre dos vértices dados; es decir, el camino que nos permita llegar desde un vértice origen a un vértice destino recorriendo la menor distancia o con el menor costo.
Los algoritmos más usados para este fin son: Dijkstra, Floyd y Warshall. Los tres algoritmos utilizan una matriz de adyacencia ponderada o etiquetada: que es la misma matriz de adyacencia utilizada para representar grafos, pero con la diferencia que en lugar de colocar un número “1” cuando dos vértices son adyacentes, se coloca el peso o ponderación asignado a la arista que los une.
Aplicaciones
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas, por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.