Grafos: nodos, aristas y caminos
Vértices y aristas
Un grafo tiene un conjunto de vértices (nodos) y un conjunto de aristas (conexiones entre pares de nodos). Las aristas pueden ser sin dirección, como una amistad mutua, o dirigidas, como un seguimiento en una red social.
Vecinos y grado
- Dos vértices son adyacentes si una arista los une.
- El grado de un vértice es cuántas aristas tocan en él.
- En grafos dirigidos se distinguen grado de entrada y de salida.
Caminos y conectividad
Un camino es una sucesión de aristas que enlaza un vértice con otro. Un grafo es conexo si hay camino entre cualquier par de vértices; si no, se descompone en componentes conexas.
Ciclos
- Un ciclo es un camino que vuelve a su vértice de origen.
- Su presencia o ausencia distingue grafos con bucles de los que no.
- Los grafos sin ciclos son, precisamente, los árboles de la próxima lección.
Grafos ponderados
Cuando cada arista lleva un número —una distancia, un coste, una afinidad— el grafo es ponderado. Ahí cobran sentido las rutas de coste mínimo, el pan de cada día de la navegación y la logística.
Representar un grafo
- Lista de adyacencia: compacta cuando hay pocas aristas.
- Matriz de adyacencia: acceso rápido a si dos nodos están unidos.
- La elección afecta a memoria y velocidad de los recorridos.
Grafos famosos
- Completo: todas las aristas posibles presentes.
- Bipartito: dos conjuntos con aristas solo entre ellos, nunca internas.
- Estrella, camino, ciclo: formas elementales que reaparecen por doquier.
Recorrer y buscar rutas
Los algoritmos de recorrido (amplitud y profundidad) y de ruta mínima navegan el grafo para responder a preguntas de alcanzabilidad y de coste. Aquí empieza la algoritmia sobre redes.
Modelar con grafos
- Identificar qué son los nodos y qué las aristas en tu problema.
- Decidir dirección y peso según la naturaleza de la relación.
- Un buen modelo convierte una pregunta difusa en un cálculo sobre el grafo.
Grafos en datos
- Redes de recomendación y de coocurrencia entre productos.
- Grafos de dependencias entre tareas o paquetes.
- Análisis de redes: centralidad, comunidades y cuellos de botella.
Errores frecuentes
- Confundir grado de entrada y de salida en grafos dirigidos.
- Suponer que un grafo es conexo cuando tiene componentes separadas.
- Elegir mal la representación y pagar de más en memoria o en tiempo.
Ejemplo resuelto: leer un grafo
Imagina cinco ciudades enlazadas por ciertas carreteras. Decide si puedes ir de cualquiera a cualquiera y halla el grado de una ciudad concreta.
- Identifica las ciudades como vértices y las carreteras como aristas.
- Recorre desde un vértice para ver cuáles alcanza: eso prueba conectividad.
- Si algún vértice queda aislado, el grafo no es conexo.
- Cuenta las aristas que tocan en la ciudad elegida: ese es su grado.
- Interpreta un grado alto como un nodo céntrico o de tránsito.
¿Para qué sirve en la realidad?
Los grafos sostienen el ruteo de redes, las recomendaciones y el análisis de redes sociales: identificar nodos centrales o comunidades en un grafo de datos revela cuellos de botella e influencias ocultas.
Un grafo se llama conexo cuando:
En un grafo dirigido, el grado de entrada de un vértice siempre coincide con su grado de salida.
Grafos
Empareja cada término de grafos con su definición.
Adyacentes
Conexo
Bipartito
Ponderado
Grafo (matemática discreta)
Estructura de vértices y aristas para modelar relaciones.
Une cada término de grafos con su definición:
Puntos y líneas que relacionan
# Grafos ## Piezas ### vértices ### aristas con o sin dirección ## Medidas ### grado ### caminos y ciclos ## Tipos ### conexo ### bipartito ### ponderado
Camino en teoría de grafos
Sucesión de aristas que conecta vértices y base de la conectividad.
Modela como grafo una red de estaciones de metro y sus transbordos. Define qué son los nodos, qué las aristas, y si te interesa un camino corto o uno con pocos transbordos.