Gráficos en matemáticas discretas: definición, tipos y usos

Gráficos en matemáticas discretas

Mary está planeando un viaje por carretera desde su ciudad hasta la casa de un amigo en algunas ciudades. Hay algunas rutas diferentes entre las que tiene que elegir, cada una de las cuales pasa por diferentes ciudades vecinas.

Decide crear un mapa. Ella representa las ciudades como puntos, y pone líneas entre ellas que representan la ruta para ir de una a otra. También incluye cuántas millas tiene cada ruta al etiquetar los bordes con su distancia.

En matemáticas discretas, llamamos a este mapa a lo que Mary creó un gráfico. Un gráfico es una colección de puntos, llamados vértices , y líneas entre esos puntos, llamados bordes . Hay muchos tipos diferentes de gráficos en matemáticas discretas. Exploremos algunos de estos.

Tipos de gráficos

Aunque hay muchos tipos diferentes de gráficos en matemáticas discretas, hay algunos que son extremadamente comunes. Algunos de ellos son los siguientes:

• Gráfico nulo : también llamado gráfico vacío, un gráfico nulo es un gráfico en el que no hay bordes entre ninguno de sus vértices.
• Gráfico conectado : un gráfico en el que hay una ruta de aristas entre cada par de vértices del gráfico. La gráfica de Mary es una gráfica conectada, ya que hay una manera de ir de cada ciudad en el mapa a cualquier otra ciudad.
• Gráfico desconectado : un gráfico en el que la ruta de las aristas no siempre conecta todos los vértices.
• Gráfico bipartito : un gráfico que se puede dividir en dos conjuntos de vértices, de modo que los bordes solo van entre conjuntos, no dentro de ellos.
• Gráfico ponderado : gráfico en el que se asignan pesos o valores numéricos a cada uno de los bordes. El gráfico de Mary es un gráfico ponderado, donde las distancias entre las ciudades son los pesos de los bordes.
• Gráfico dirigido : Un gráfico en el que los bordes están dirigidos por flechas, lo que indica que la relación, representada por el borde, solo se aplica de un vértice al otro, pero no al revés. En otras palabras, si un borde dirigido tiene una flecha de A a B, A está relacionado con B, pero B no está relacionado con A.
• Gráfico no dirigido : un gráfico cuyos bordes no están dirigidos. El gráfico de Mary es un gráfico no dirigido, porque las rutas entre ciudades van en ambos sentidos.
• Gráfico simple : un gráfico no dirigido en el que hay como máximo un borde entre cada par de vértices y no hay bucles , que es un borde de un vértice a sí mismo.
• Multi-graph : Un gráfico en el que hay múltiples aristas entre cualquier par de vértices o aristas desde un vértice a sí mismo, también llamado bucle.
• Gráfico plano : un gráfico que se puede dibujar de modo que todos los bordes del gráfico no se crucen entre sí.
• Gráfico no plano : un gráfico que no es un gráfico plano. En otras palabras, un gráfico que no se puede dibujar sin que al menos un par de sus bordes se crucen.

¡Uf! Son bastantes tipos diferentes de gráficos y, lo crea o no, hay muchos más. La variedad muestra cuán grande es este concepto y por qué hay una rama de las matemáticas, llamada teoría de grafos, que está específicamente orientada al estudio de estos gráficos y sus usos. Hablando de los usos de estos gráficos, ¡echemos un vistazo a un par de ejemplos de eso!

Usos de gráficos: ejemplo 1

Todos los gráficos que acabamos de ver son extremadamente útiles en matemáticas discretas y en aplicaciones del mundo real. Por ejemplo, considere nuevamente el viaje por carretera de Mary. Suponga que quiere encontrar la ruta más corta de su casa a la casa de su amiga. Primero, enumeramos todas las rutas diferentes, luego simplemente sumamos los pesos de los bordes en cada ruta para obtener el número total de millas en cada ruta. La que es menor que las demás es la ruta más corta.

Vemos que la ruta más corta va de la ciudad de Mary a la ciudad D a la ciudad C y termina en la ciudad del amigo de Mary, y el kilometraje total de ese viaje es de 90 millas. ¡Increíble! ¡Estos gráficos son realmente útiles!

Este fue un ejemplo simple de un problema bien conocido en la teoría de grafos llamado problema del viajante. Los gráficos son una parte integral para encontrar los caminos más cortos y más largos en escenarios del mundo real.

Ejemplo 2

Consideremos un uso más de una gráfica. Suponga que un gerente de un centro de asesoramiento ha utilizado un gráfico para organizar buenas coincidencias para clientes y asesores en función de las diferentes características de los clientes y los asesores. Para hacer esto, representa a los clientes con un conjunto de vértices y a los consejeros con otro conjunto, y luego dibuja una ventaja entre los clientes y los consejeros que hacen una buena combinación.

Vemos que este gráfico es un gráfico simple, porque no está dirigido y no hay múltiples aristas o bucles. También es un gráfico bipartito, porque está dividido en dos conjuntos de vértices (los clientes y los asesores), y los únicos bordes están entre los clientes y los asesores. En otras palabras, no existen fronteras entre dos clientes o entre dos consejeros.

Supongamos que Gabriel está trabajando actualmente con George como su consejero, pero ambos sienten que no están haciendo el progreso que les gustaría, por lo que deciden poner a Gabriel con otro consejero. Afortunadamente, decidir con qué consejero poner a Gabriel es muy fácil usando nuestro gráfico.

Vemos que hay una ventaja entre Gabriel y George, y la única otra ventaja que involucra a Gabriel es entre Gabriel y Lucy. Colocarán a Gabriel con Lucy, ya que saben que es una buena pareja. ¡Ordenado! ¡Imagina todos los escenarios en los que puedes usar gráficos!

Resumen de la lección

En matemáticas discretas, una gráfica es una colección de puntos, llamados vértices , y líneas entre esos puntos, llamados bordes . Hay muchos tipos diferentes de gráficos, como gráficos conectados y desconectados, gráficos bipartitos, gráficos ponderados, gráficos dirigidos y no dirigidos y gráficos simples.

• Gráfico conectado : los bordes conectan cada par de vértices.
• Gráfico desconectado : las aristas no siempre conectan todos los vértices.
• Gráfico bipartito : las aristas van solo entre conjuntos de vértices.
• Gráfico ponderado : se asignan pesos , o valores numéricos, a cada uno de los bordes.
• Gráfico dirigido : los bordes están dirigidos por flechas, lo que indica que la relación se aplica de un vértice al otro y no al revés.
• Gráfico no dirigido : un gráfico cuyos bordes no están dirigidos.
• Gráfico simple : un gráfico no dirigido en el que hay como máximo un borde entre cada par de vértices y no hay bucles , un borde desde un vértice hacia sí mismo.

Los gráficos se pueden utilizar para representar o responder preguntas sobre diferentes situaciones del mundo real.