Conceptos y terminología de la teoría de grafos

Un gráfico

Los gráficos que ves en la teoría de gráficos , el estudio de gráficos, se parecen mucho a un juego de conectar los puntos. Sin embargo, no siempre obtendrá una buena imagen al final. En cambio, obtendrá muchos puntos con varias líneas que conectan los puntos. Y, a diferencia del juego de conectar los puntos, algunos de los puntos pueden tener más de una línea que los conecta con otros. Los gráficos se verán así:

Este es un ejemplo de un gráfico simple. Parece un juego de conectar los puntos, ¿no? Pero el producto terminado no parece un animal lindo o un objeto interesante. Simplemente parece un montón de puntos con líneas que los conectan. El estudio de cómo estas líneas conectan los puntos es de lo que se trata la teoría de grafos.

Puede sonar aburrido y sin sentido, pero si piensa en una ciudad, sus muchas intersecciones y carreteras, y luego piensa en planificar la mejor ruta para llegar del punto A al punto B, entonces puede ver cómo entra en juego la teoría de grafos. La teoría de grafos le permite encontrar la mejor ruta dadas las carreteras que conectan las distintas intersecciones. Mire el gráfico nuevamente, y es posible que ahora pueda ver un pequeño pueblo. Los círculos son casas y las líneas son caminos que conectan las casas. Esta es solo una aplicación de la teoría de grafos y hay otras. Pero muestra lo importante que es la teoría de grafos. Es por eso que hay todo un campo de las matemáticas dedicado a este estudio.

Vértices

A medida que profundice en la teoría de grafos, encontrará algunos términos clave muy importantes, que cubriremos en esta lección en video. Comenzamos con los términos relacionados con nuestros vértices , nuestros puntos.

Podemos tener varios estilos diferentes de vértices. Podemos tener un vértice aislado , que es un vértice sin líneas que lo conecten con otros. Un vértice aislado en un gráfico estará solo. No tendrá ninguna conexión.

El vértice del extremo derecho de este gráfico es un vértice aislado. ¿Ves cómo no tiene líneas que lo conecten con otros? Parece bastante solitario. Si nuestro gráfico representa un pequeño pueblo, entonces este vértice aislado podría ser una casa sin caminos hacia él. Tendrías que caminar por el desierto para llegar a él.

Otro término que probablemente verá es vértices adyacentes . Esto se refiere a vértices conectados que están uno al lado del otro. Por ejemplo, mirando nuestro último gráfico, los dos vértices en la parte superior de nuestro gráfico son vértices adyacentes porque están conectados y están uno al lado del otro.

A continuación, tenemos el grado de un vértice . Esto nos dice cuántas líneas están conectadas al vértice. Por ejemplo, el vértice aislado tiene un grado de 0. El vértice del extremo izquierdo tiene un grado de 2 porque tiene dos líneas. El vértice en la parte superior tiene un grado de 3 porque tiene tres líneas que lo conectan con otras. Si nuestro grado es par, llamamos al vértice un vértice par . Si el grado es impar, lo llamamos vértice impar . Eso es bastante fácil de recordar. Impar para un número impar de conexiones e incluso para un número par de conexiones.

Bordes

Ahora, repasemos los términos para las aristas , nuestras líneas. Podemos tener múltiples aristas si tenemos caminos que son paralelos entre sí o líneas que conectan los mismos vértices. También tenemos bordes adyacentes , que, como un vértice adyacente, son bordes que están uno al lado del otro. Mirando nuestro gráfico, los bordes en el extremo izquierdo del gráfico son adyacentes porque están uno al lado del otro.

Caminos y otros

Ahora que hemos cubierto los términos para vértices y aristas, hablemos de los términos para otros aspectos de nuestro gráfico. Aquí tenemos lo que se llama camino , una ruta que te lleva de un vértice a otro. Por ejemplo, es posible que queramos llegar desde la casa del extremo izquierdo, el punto A, hasta la casa del fondo del camino, el punto B.

Las aristas que tomamos y los vértices por los que pasamos son parte de nuestro camino. El número de aristas que tomamos se conoce como la longitud del camino . Entonces, por ejemplo, si comenzamos a bajar desde el punto A y continuamos tomando los bordes más bajos, tendríamos una longitud de camino de 3 ya que usamos tres bordes para ir del punto A al punto B. Si nuestro camino nos lleva desde un punto , digamos el punto A, y nos lleva de regreso al mismo punto A, luego llamamos a esta ruta un circuito.

En este ejemplo, debido a que todos nuestros vértices están conectados, podemos llamar a esto un gráfico conectado . Si tenemos un gráfico que no está todo conectado, como el que se muestra a continuación, entonces tenemos un gráfico desconectado . Puede pensar en un gráfico desconectado como vecinos o casas que no están conectadas a los otros vecinos o casas. Si viviera en un vecindario, no podría llegar al otro vecindario ya que no hay carreteras que conecten los dos.

Ahora, mire este gráfico:

Este gráfico tiene dos componentes o dos subgrafos. Estos subgrafos son gráficos en sí mismos, pero no están conectados con el resto del gráfico. Si tuviéramos que agregar una conexión como esta, entonces tendríamos solo un gráfico con un componente:

Esta conexión entre los componentes se llama puente . Al igual que un puente en la vida real, si lo rompe o se deshace de él, no podrá llegar al otro lado. En teoría de grafos, un puente es el único camino que puede tomar de un componente a otro. Entonces, es como tener un solo puente desde el continente hasta una isla. Si el puente se derrumbaba, no habría forma de llegar a la isla. Y ahí tenemos nuestros términos clave importantes.

Resumen de la lección

Repasemos lo que hemos aprendido. Aprendimos que la teoría de grafos es el estudio de grafos. Los vértices son los puntos en nuestro gráfico. Un vértice aislado es un vértice sin líneas ni conexiones con él. Los vértices adyacentes son vértices conectados que están uno al lado del otro. El grado de un vértice te dice cuántas líneas conectan este vértice con otros vértices. Si el grado es impar, entonces podemos llamar al vértice un vértice impar . Si el grado es par, podemos llamarlo vértice par .

Nuestros bordes son nuestras líneas. Varias aristas son líneas que conectan los mismos vértices. Los bordes adyacentes son bordes que están uno al lado del otro. Un camino es una ruta de un vértice a otro. La longitud de la ruta es el número de aristas necesarias para pasar de un vértice a otro.

Si todos los vértices del gráfico están conectados, entonces tenemos un gráfico conectado . Esto significa que tenemos caminos que podemos tomar desde cualquier punto de este gráfico a cualquier otro punto del gráfico. Si no todos los vértices están conectados entre sí, entonces tenemos un gráfico desconectado . En un gráfico desconectado, los subgrafos se denominan componentes . Estos subgráficos son gráficos en sí mismos, pero no están conectados con el resto del gráfico. Un puente conecta dos componentes juntos. Quita el puente y tendremos dos componentes separados nuevamente.

Los resultados del aprendizaje

Después de esta lección, tendrá la capacidad de:

• Definir teoría de grafos
• Identificar los tipos de vértices y aristas utilizados en la teoría de grafos.
• Describir una ruta y la longitud de la ruta en teoría de grafos.
• Diferenciar entre gráficos conectados y desconectados
• Explica qué componentes y un puente son en teoría de grafos.

Rodrigo Ricardo Editor y fundador