Introducción a la Teoría de Grafos

¿Qué es la Teoría de Grafos?

La Teoría de Grafos (también llamada Teoría de Gráficas) estudia cómo están conectadas las cosas, a través de una red de puntos y líneas.

Un grafo se ve así:

Un grafo simple
Un Ejemplo de Grafo

Sí, se llama "grafo"... pero NO es este tipo de gráfica:

no es un gráfico de líneas

Ambos se llaman "grafos" o "gráficas". Pero son cosas diferentes. Así son las cosas.

Este tema explora cómo estos puntos y líneas se relacionan entre sí, y cómo es mejor moverse a través de ellos.

mapa del metro

Puedes pensar en ellos como lugares y caminos, o como estaciones y trenes ... o como un mapa de amistades donde cada persona es un nodo y cada amistad es una arista.

¡Hay muchas maneras de pensar en los grafos!

Los grafos tienen aplicaciones en muchas áreas, como la informática, la biología, las ciencias sociales, el transporte y más.

Vamos a aprender algunas palabras especiales:

  • Un punto se llama vértice (plural vértices)
  • Una línea se llama arista.
  • El diagrama completo se llama un grafo.
  grafo vértice y arista
grafo grado 3 y 2
camino simple y camino de Euler

Un Camino Simple es como encontrar una forma de visitar la casa de cada amigo exactamente una vez.

Un Camino de Euler es como la ruta de un cartero que recorre cada calle una vez.

Algunos ejemplos:

ejemplo de grafo 2

Este Grafo tiene:

  • 5 vértices: A, B, C, D y E
  • 8 aristas: AB, BC, CD, DA, AE, BE, AC y BD
  • Los vértices A y B tienen grado 4
  • Los vértices C y D tienen grado 3
  • El vértice E tiene grado 2
ejemplo de grafo 3

Este Grafo tiene:

  • 6 vértices: A, B, C, D, E y F
  • 10 aristas: AB, BC, CD, DA, AF, BF, CF, DF, AE y BE
  • Los vértices A, B y F tienen grado 4
  • Los vértices C y D tienen grado 3
  • El vértice E tiene grado 2
Prueba la actividad de Los siete puentes de Königsberg.

Usos en el mundo real

En el mundo real, podemos encontrar muchas situaciones que se pueden representar utilizando la teoría de grafos:

La teoría de grafos puede ayudar a planificar las rutas de transporte público más eficientes o a gestionar el tráfico en redes de internet.

Tipos

Existen muchos tipos de grafos, como grafos dirigidos y no dirigidos, grafos ponderados, y algoritmos que pueden resolver problemas fascinantes como encontrar el camino más corto entre dos puntos.