La teoría de grafos se utiliza en diferentes problemas cuantificables y en él intervienen unos elementos que tienen relación entre sí o que están conectados.
Estos problemas pueden ser; por ejemplo, los relativos a redes de comunicación y transporte, estructuras de producto complejas o relaciones de orden entre diferentes actividades.
Los grafos son herramientas que nos permiten hacer modelos de relaciones de este tipo, de manera que, con ellos, se podrían resolver inconvenientes generalmente de una forma menos costosa que por ejemplo la programación lineal.
INDICE EDUCATIVO
Qué es la teoría de grafos
Conocida también como teoría de las gráficas, se encarga de estudiar las propiedades que poseen los grafos, objetos de los que se hablarán más adelante. Esta es una rama de las ciencias de la telecomunicación y por supuesto, de las matemáticas.
Sin embargo, la hipótesis extrae conceptos de distintos campos como lo es la geometría, la aritmética, el álgebra, la topología, la probabilidad, y muchos otros. Pero actualmente ha tenido una mayor huella y atención en las redes de telecomunicaciones y demás.
Qué son los grafos
Los grafos son representaciones gráficas de un conjunto de objetos conocidos como vértices, interconectados mediante aristas, arcos o simplemente lados. Estos nos ayudan a representar relaciones binarias, es decir, entre elementos de dos conjuntos.
Los grafos son entonces, modelos matemáticos que expresan situaciones reales, como por ejemplo, un mapa de carreteras, una red de PCs, un plano de un circuito eléctrico, etc.
Estos se definen como un conjunto de pares no ordenados de elementos diferentes y otros elementos.
Grafo= G
Conjunto de pares no ordenados= E
Elementos = V
Donde G= (V, E)
V= (v1, v2,…, vn)
E= (vivj, vn, vm,…)
Por ejemplo:
G= (V, E)
V= (co, M, G, J, A)
E= ((Co,G), (M,G), (G,J), (G,A), (M,J)
En este caso, “Co” debe estar unido con “G”, y a su vez “G” debe estar unido con “A” y con “M”.
Luego M con J, J con G y a sólo con G al igual que Co.
Se dice entonces que dos vértices vi, vj son adyacentes si se da el caso de que los extremos de una arista son parte de E, es decir, que los vértices serán adyacentes siempre y cuando los extremos que se tocan en la arista son parte del conjunto de pares no ordenados.
Donde V= al número de vértices y E la cantidad de aristas.
Tipos de grafos
Existen diferentes clases o tipos de grafos, todos estos se basan en la cantidad de aristas que poseen o cómo están organizadas.
Multígrafo
Este es básicamente un grafo con varias aristas entre sólo dos vértices, como por ejemplo:
V= (V1, V2, V3)
E= (v1v2, v2v3, v2v3, v3v1, v3v1)
Pseudografo
Esta clase de grafos tiene aristas cuyos extremos coinciden con el propio vértice (ambos extremos). Este es un tipo especial de arista y se le conoce como lazo, esto es debido a la manera en la que se asemejan a los lazos hechos con cuerdas.
Ejemplo:
V= (V1, V2, V3)
E= (v1v1, v1v2, v2v2, v2v3, v3v3)
Dígrafos
Este se conoce de esta manera cuando los elementos son pares ordenados, por lo que sí es importante cuál de los vértices se posiciona primero, a diferencia de los otros grafos que era completamente aleatorio.
Aplicaciones de la teoría de los grafos
Gracias a la hipótesis de los grafos es cómodo solventar distintos problemas como por ejemplo, la elaboración de circuitos que requieren secuencias. Siendo posible utilizarlos en todas las ramas de la ingeniería.
Los grafos se utilizan también para diseñar trayectorias principalmente, como por ejemplo, un autobús dentro de las calles de la ciudad.