Introducción a la teoría de grafos

Teoría de grafos

En matemáticas, hay toda una rama de estudio dedicada a la teoría de grafos . ¿Qué es? Es el estudio de gráficos. Sí, es posible que no crea que los gráficos puedan ser tan complicados, pero como verá, el estudio de los gráficos y cómo se conectan es un gran campo de estudio. Tan grande, de hecho, que las grandes empresas y las empresas de transporte público dedican mucho tiempo a la teoría de grafos para asegurarse de que todo funcione sin problemas.

Por ejemplo, las empresas de servicios públicos, como las que suministran electricidad, se basan en la teoría de grafos cuando configuran sus postes de energía para asegurarse de que los postes estén ubicados en la mejor ubicación posible en relación con todos los demás polos. Las empresas de transporte público, como los autobuses, utilizan la teoría de gráficos para planificar la mejor ruta posible entre varios destinos. Sí, todos estos utilizan la teoría de grafos. Si miras un mapa e intentas planificar una ruta desde el punto A al punto B, estás practicando la teoría de grafos.

Un gráfico

Si dibujara una versión simplificada de su mapa, tendría puntos para sus ciudades y líneas rectas que conectan los puntos que representan las carreteras. Esta versión simplificada de su mapa es el tipo de gráfico que verá en la teoría de grafos:

Mapa de teoría de grafos

Si este gráfico es una versión simplificada de nuestro mapa, entonces vemos que tenemos cuatro ciudades, los cuatro puntos, y cinco carreteras, las cinco líneas rectas. Entonces, la teoría de grafos se trata de estudiar este gráfico y ver cuál es la mejor ruta posible a seguir entre dos puntos cualesquiera en este gráfico. Las empresas de transporte público pueden utilizar este gráfico para encontrar la mejor ruta posible entre los puntos A y C, por ejemplo. Las empresas de servicios públicos pueden utilizar este gráfico para determinar qué polos están conectados entre sí y cuál es la mejor forma de suministrar energía a todos los polos.

Vértices

Ahora, por el vocabulario. Observe los puntos A, B, C y D. Estos puntos se llaman vértices en la teoría de grafos. Cuando tenemos varios puntos, tenemos vértices. Si tenemos un solo punto, lo llamamos vértice . Los vértices son los puntos de donde vienen y salen las líneas. Algunos vértices pueden tener solo una línea que se conecta a ellos. Otros pueden tener varias líneas que se conectan a otros vértices. Por ejemplo, en nuestro gráfico, los puntos A y C tienen dos líneas que los conectan con otros puntos. Los puntos B y D, por otro lado, tienen tres líneas. En teoría de grafos, puede tener un número ilimitado de líneas que conectan un punto con otros puntos. El gráfico que tenemos aquí es un gráfico muy simple solo para comenzar a aprender sobre la teoría de grafos.

Bordes

Nuestra siguiente palabra de vocabulario es bordes . Estas son las líneas que conectan nuestros vértices. Los puntos A y B están conectados por un borde. Los puntos B y D están conectados por un borde. Los puntos A y C, sin embargo, no lo son. Pero podemos ir del punto A al punto C pasando por el punto B o el D, ya que todos están conectados por bordes. Esto me recuerda a las rutas de los aviones. Algunos vuelos son vuelos directos de un punto a otro, mientras que otros requieren una escala en algún lugar. El vuelo directo es como ir del punto B al punto D, mientras que el vuelo de escala es como ir del punto A al punto C pasando por el punto B.

Bucles

Nuestra última palabra de vocabulario es bucles . Un bucle es una arista que se conecta al mismo vértice. Si tienes cordones, míralos y verás lazos. Eso es lo que también verá en el dibujo del gráfico. He aquí un ejemplo:

Bucle en el punto C

En este ejemplo, tenemos un bucle en el punto C. ¿Ves cómo se redondea este borde? Parece un bucle y te lleva de regreso al punto de partida; se conecta al mismo vértice. En teoría de grafos, puede permitir o no permitir la presencia de estos bucles.

Resumen de la lección

Repasemos ahora lo que hemos aprendido. Aprendimos que la teoría de grafos es el estudio de grafos. Este es un campo útil porque le permite encontrar las mejores rutas posibles entre dos puntos. Puedes decir que un gráfico parece un mapa simplificado. En teoría de grafos, tenemos algo de vocabulario básico. El primero es vértice o vértices . Se refieren a un punto o puntos del gráfico. El siguiente son los bordes . Esto se refiere a las líneas del gráfico. Por último, tenemos bucles . Se refieren a aristas que se conectan al mismo vértice. Si estuviera viajando en uno de estos bucles, terminaría donde comenzó.

Los resultados del aprendizaje

Puede lograr estos objetivos después de haber terminado con esta lección:

• Recita la definición de teoría de grafos.
• Señale dónde se usa la teoría de grafos a través de ejemplos del mundo real
• Comparar un gráfico con un mapa simple
• Analizar el vocabulario utilizado en la teoría de grafos: vértices, aristas y bucles.

Rodrigo Ricardo Editor y fundador