Cuando diseñamos un algoritmo, no basta con que funcione correctamente. También debemos preguntarnos: ¿es la mejor opción disponible? En muchos problemas, existen varias formas de llegar a una misma solución, pero no todas son igual de eficientes. Un buen algoritmo no es solo aquel que resuelve el problema, sino aquel que lo hace de la manera más rápida y utilizando la menor cantidad posible de recursos computacionales. Aquí es donde entra en juego el análisis de algoritmos.

El análisis de algoritmos nos permite estimar cuánto tiempo y cuánta memoria requiere un algoritmo antes incluso de ejecutarlo. Esto es esencial en contextos como la ciberseguridad, donde trabajar con grandes volúmenes de datos y buscar soluciones rápidas puede marcar la diferencia. Incluso si dos algoritmos devuelven exactamente el mismo resultado, uno puede demorar segundos y otro, minutos, dependiendo de su diseño interno.

En términos generales, existen dos aspectos principales que analizamos en un algoritmo: el tiempo de ejecución y el uso de espacio en memoria (White and Ray 2021).

• Tiempo de ejecución: mide cuánto tarda el algoritmo en completarse como función del tamaño de la entrada. Por ejemplo, si sumar dos bits toma c segundos, entonces sumar dos números de n bits tomará F(n)=n⋅c segundos. En este caso, el crecimiento es lineal. Esta medida es teórica: cuenta cuántos pasos se ejecutan, asumiendo que cada paso toma el mismo tiempo.
• Espacio requerido: se refiere a la cantidad de memoria que necesita el algoritmo durante su ejecución. Esta memoria puede dividirse en:
• Parte fija: espacio que no depende del tamaño de la entrada, como variables, constantes o el tamaño del propio programa.
• Parte variable: espacio que sí depende del tamaño de la entrada, como estructuras dinámicas, pilas de recursión o arreglos temporales.

Ejemplo 1. Supongamos que tienes una lista de 1.000.000 contraseñas y necesitas verificar si una en particular está en esa lista. Un algoritmo de búsqueda lineal comparará cada elemento uno por uno hasta encontrarlo (o no), lo que en el peor de los casos requiere un millón de comparaciones. En cambio, si las contraseñas están ordenadas y usamos búsqueda binaria, podemos encontrar la contraseña correcta (o confirmar su ausencia) en aproximadamente 20 pasos. Ambos algoritmos resuelven el mismo problema, pero de manera muy distinta.

Ejemplo 2. En ciberseguridad, cuando se analiza un tráfico de red en busca de patrones sospechosos, puede que un algoritmo simple evalúe cada paquete uno por uno, mientras que un algoritmo más sofisticado use estructuras como árboles de decisión o hash tables. El primero puede saturar el sistema ante ataques masivos; el segundo puede responder rápidamente, incluso bajo presión. Este tipo de decisiones no son triviales: exigen un análisis cuidadoso del comportamiento del algoritmo.

En la siguiente figura, presentamos cuatro algoritmos comparados gráficamente según el tiempo de ejecución y el espacio requerido. Por ejemplo, el Algoritmo 1 es costoso tanto en tiempo como en memoria, mientras que el Algoritmo 2 parece ser más equilibrado. Este tipo de análisis gráfico es útil para visualizar rápidamente qué algoritmos son más convenientes bajo restricciones específicas: algunos priorizan rapidez, otros, menor uso de memoria, y otros buscan un punto medio.

Figura 1

Comparación de requerimientos de tiempo y espacio en distintos algoritmos

Cuando medimos el tiempo que tarda un algoritmo en ejecutarse, podríamos pensar en segundos, minutos o días. Sin embargo, esta medida puede variar entre computadoras, dependiendo del procesador, la cantidad de memoria, el sistema operativo, la carga del sistema, o incluso procesos en segundo plano (White and Ray 2021). Por ello, medir el tiempo real no siempre es útil ni objetivo. En lugar de eso, se mide el número de operaciones fundamentales que realiza el algoritmo, que son independientes del hardware.

Las operaciones que se consideran elementales incluyen comparaciones, asignaciones, operaciones aritméticas (suma, multiplicación), llamadas a funciones, accesos a elementos de una estructura de datos, entre otras. Estas operaciones se cuentan como si tomaran el mismo tiempo, permitiéndonos estudiar el comportamiento del algoritmo de forma abstracta y general.

Definición 1.

Dado un algoritmo A, cuyo conjunto de datos es D, se define la función T:D→N, denominada tiempo de ejecución (o costo computacional), de tal forma que para un dato x∈D, T(x) es el número de operaciones elementales que realiza el algoritmo, con el dato x, hasta finalizar.

En muchos casos, nos interesa cómo cambia el tiempo de ejecución cuando cambia el tamaño de la entrada, más allá de los datos específicos. Por ejemplo, el tamaño puede medirse como:

• El número de elementos en una lista.
• La cantidad de vértices en un grafo.
• El número de bits necesarios para representar un número.

Definición 2.

Sea un algoritmo A cuyo conjunto de datos es D y, para x∈D tomemos n_x∈N una característica del dato x. Si para todo x,y∈D tal que n_x=n_y=n∈N se tiene que T(x)=T(y), se dice que el tiempo de ejecución no depende de la naturaleza de los datos sino únicamente del tamaño de la entrada n. Se redefine la función T:N→N de tal forma que para n∈N, T(n) es el número de operaciones elementales que realiza el algoritmo con datos de tamaño n, hasta finalizar.

Consideremos el siguiente ejemplo tomado de Johnsonbaugh (2018):

Ejemplo 3. Suponga que se tiene un conjunto X de n elementos, algunos etiquetados con «rojo» y otros con «negro», y se desea encontrar el número de subconjuntos que contienen al menos un elemento rojo. Si se construye un algoritmo que examina todos los subconjuntos de X y cuenta los que contienen al menos un rojo, entonces ese algoritmo generará los 2ⁿ subconjuntos posibles y verificará cada uno. El tiempo de ejecución, entonces, será proporcional a 2ⁿ, lo cual crece tan rápidamente que hace inviable su ejecución para valores grandes de n.

La siguiente tabla ilustra este fenómeno. Si asumimos que cada operación elemental toma 1 microsegundo (10^(-6) segundos), se muestra el tiempo total requerido para diferentes funciones de crecimiento, al variar el tamaño de la entrada n.

Como se observa en la tabla, algoritmos con número de pasos n o nlog(n) siguen siendo eficientes incluso para entradas grandes, mientras que algoritmos con número de pasos como 2_n, se vuelven imprácticos muy rápidamente. Por ejemplo, para n=1000, una función 2_n requeriría más tiempo que la edad del universo.

Veamos algunos ejemplos prácticos del cálculo del tiempo de ejecución de algunos algoritmos.

Ejemplo 4. Consideremos una función que accede al primer elemento de un arreglo.

• Tamaño de la entrada: Un arreglo A con n≥1 elementos.
• Análisis de la dependencia: El tiempo de ejecución no cambia, independientemente de los datos que tenga el arreglo. Podemos tomar como tamaño de los datos, el número de elementos del arreglo.

Código 1

Acceder al primer elemento de un arreglo

            
def primero(A):
    x = A[0]
    return x
            
          

Cálculo del costo:

• Línea 2: La operación de acceso al arreglo (A[1]) y la asignación a la variable x son dos operaciones elementales.
• Línea 3: El retorno de la función es una operación.

El número total de operaciones es 2+1=3. Como este valor es fijo y no depende de n, la función de tiempo es T(n)=3.

Ejemplo 5. Analicemos una función que copia todos los elementos de un arreglo a otro.

• Tamaño de la entrada: Un arreglo A de longitud n.
• Análisis de la dependencia: El algoritmo no depende de la naturaleza de los datos que contenga el arreglo, solo debe recorrer todos los elementos del arreglo una única vez, por lo que el número de operaciones dependerá del número de elementos de la entrada, n.

            
# Código 2: Copiar un arreglo
def copiar(A, n):
    B = []
    for i in range(n):
        B[i] = A[i]
    return B
            
          

Cálculo del costo:

• Línea 2: La creación de un nuevo arreglo y la asignación toman un tiempo constante. Contabilizamos una operación.
• Líneas 3-4 (Bucle): El bucle se repite n veces, una por cada elemento del arreglo. En cada iteración:
• Se accede a A[i] y B[i].
• Se realiza una asignación (B[i] = A[i]).

En total, cada iteración realiza 2 operaciones. Como el bucle se ejecuta n veces, las operaciones de este bloque son 2n.

• Línea 5: El retorno de la función es una operación.

Sumando todas las operaciones, obtenemos la función de tiempo: T(n)=1+2n+1=2n+2.

Ejemplo 6 Consideremos un algoritmo que cuenta los elementos positivos en una matriz cuadrada.

• Tamaño de la entrada: Una matriz M de n×n. El tamaño de la entrada se mide por n.
• Análisis de la dependencia: Para resolver el problema, no depende del tipo de datos que tenga la matriz ni de su distribución, solo debemos visitar cada una de las entradas, por lo que podemos considerar a n como el tamaño de los datos.

            
# Código 3: Contar elementos positivos en una matriz
def contar_positivos(M, n):
    c = 0
    for i in range(n):
        for j in range(n):
            if M[i, j] > 0:
                c = c + 1
            else:
                c = c + 0
    return c
            
          

Cálculo del costo:

• Línea 2: La asignación inicial de c es una operación.
• Líneas 3-8 (Bucles anidados): El bucle exterior se ejecuta n veces, y el bucle interior se ejecuta n veces para cada iteración del bucle exterior. En total, el bloque interior se ejecuta n⋅n=n^2 veces. En cada una de estas n^2 iteraciones:
  • La comparación (M[i,j]>0) es una operación. Esto se hace para las n^2 celdas, sumando n^2 operaciones.
  • Sin importar el resultado del condicional, la suma y la asignación (c=c+1 o c=c+0) son dos operaciones. Esto se hace para cada una de las n^2 celdas, sumando 2n^2 operaciones.
  • El costo de los bucles anidados es n^2+2n^2=3n^2.
• Línea 9: El retorno de la función es una operación.

La función de tiempo total es:

\[ T(n) = 1 + 3n^2 + 1 = 3n^2 + 2 \]

En este último ejercicio, notemos que se puede simplificar el código, eliminado la asignación c=c+0, la cual no es necesaria y es redundante, pero con esto, el número de operaciones que ejecuta el algoritmo dependería de la naturaleza de los datos, por ejemplo, si todas las entradas fueran negativas, el algoritmo dejaría de hacer 2n^{^2} operaciones, es decir, realizaría n^{^2}+2 operaciones en total. Esto lo analizaremos en la siguiente sección.

En el ejemplo anterior, observamos que al eliminar la operación redundante c=c+0, el número total de operaciones que realiza el algoritmo puede variar según la naturaleza de los datos. Si todos los elementos son negativos, se ejecutan menos operaciones que si hay elementos positivos. Esto nos lleva a la idea de que, para un mismo tamaño de entrada n, el tiempo de ejecución de un algoritmo puede no ser único, sino depender de los datos específicos que recibe como entrada.

Para formalizar esta idea, introducimos las siguientes tres nociones: el tiempo de ejecución en el mejor caso, en el peor caso y en el caso promedio.Para formalizar esta idea, introducimos las siguientes tres nociones: el tiempo de ejecución en el mejor caso, en el peor caso y en el caso promedio.

Definición 3.

Dado un algoritmo cuyo conjunto de datos es \(D\) y, para \(x \in D\) tomemos \(n_x \in \mathbb{N}\) una característica del dato \(x\). Para \(n \in \mathbb{N}\), se define:

• Tiempo del mejor caso:

\[ T_m(n) = \min \{ T(x) : n_x = n \} \]

representa la menor cantidad de operaciones que puede ejecutar el algoritmo para entradas de tamaño n.

• Tiempo del peor caso:

\[ T_M(n) = \max \{ T(x) : n_x = n \} \]

representa la mayor cantidad de operaciones que puede ejecutar el algoritmo para entradas de tamaño n.

• Tiempo esperado:

\[ T_e(n) = \mathbb{E}\big(T(x) \mid n_x = n\big) \]

representa el número promedio de operaciones que ejecuta el algoritmo para entradas de tamaño n, considerando alguna distribución de probabilidad sobre los datos.

Ejemplo 7 (Búsqueda de un dato en una lista). Supongamos que tenemos una lista L de n elementos y queremos buscar si el valor a se encuentra en ella. Consideremos el algoritmo de búsqueda lineal, que recorre la lista elemento por elemento hasta encontrar a o hasta agotar la lista.

• Mejor caso: el dato buscado a está en la primera posición. En este caso, basta con una comparación, por lo que T_m(n)=1.
• Peor caso: el dato a no está en la lista, o está en la última posición. En este caso, se deben realizar n comparaciones, por lo que T_M(n)=n.
• Caso promedio: si suponemos que a está presente en la lista con probabilidad uniforme y su posición es igualmente probable entre las n posibles, en promedio se necesitarán \((n+1)/2\) comparaciones. Si a no está en la lista, se requerirán n comparaciones. Considerando ambos escenarios, el valor esperado depende de la probabilidad asumida de que a esté o no en la lista.

Este ejemplo muestra que el análisis de algoritmos no se limita a una única medida de tiempo, sino que debemos considerar escenarios extremos (mejor y peor caso) y, cuando es posible, un escenario intermedio que refleje el comportamiento típico (caso promedio).

En las secciones anteriores vimos cómo calcular el número de operaciones que realiza un algoritmo en función del tamaño de la entrada. Sin embargo, no todas las funciones crecen de la misma manera. En la siguiente figura se muestra la comparación entre funciones como n, 3n, n², n²+2n y 2ⁿ. Al inicio, n²+2n parece crecer más rápido que 2ⁿ, pero al ampliar la vista se observa que 2ⁿ termina superando ampliamente a todas las demás.

Figura 2

Comparación de crecimiento de funciones

Para formalizar estas ideas, introducimos tres notaciones fundamentales que comparan el crecimiento de funciones, que se conoce como notación asintótica.

Definición 4.

Sean f y g funciones reales cuyos dominios son el mismo subconjunto de los reales no negativos. Decimos que:

• \( f \) es de orden al menos \( g \), que se escribe \( f(x) \) es \( \Omega(g(x)) \), si y sólo si existen \( A > 0 \) y \( a \ge 0 \) tales que, para todo \( x > a \):

\[ A \, |g(x)| \le |f(x)| \]

• \( f \) es de orden a lo más \( g \), que se escribe \( f(x) \) es \( O(g(x)) \), si y sólo si existen \( B > 0 \) y \( b \ge 0 \) tales que, para todo \( x > b \):

\[ |f(x)| \le B \, |g(x)| \]

• \( f \) es de orden \( g \), que se escribe \( f(x) \) es \( \Theta(g(x)) \), si y sólo si existen \( A, B > 0 \) y \( k \ge 0 \) tales que, para todo \( x > k \):

\[ A \, |g(x)| \le |f(x)| \le B \, |g(x)| \]

En la práctica, la notación que más se utiliza es la O-grande , ya que describe una cota superior del tiempo de ejecución en función del tamaño de la entrada. Esto nos permite comparar algoritmos de manera sencilla y anticipar su comportamiento cuando el tamaño de los datos crece.

• Por ejemplo, cualquier polinomio de grado n, como

\[ a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0 \]

es O(xⁿ), ya que el término de mayor grado domina el crecimiento.

• En los ejemplos anteriores: el acceso al primer elemento de un arreglo fue O(1), la copia de un arreglo fue O(n) y el conteo de elementos positivos en una matriz n×n fue O(n²).

Ejemplo 8 (Multiplicación de matrices). La multiplicación de matrices es una operación fundamental en áreas como gráficos por computadora o entrenamiento de redes neuronales.

• Con el algoritmo clásico, multiplicar dos matrices de tamaño n×n requiere \(O(n^3)\) operaciones.
• Con algoritmos más avanzados, como el de Strassen, se logra \(O(n^{2.81})\).
• Existen algoritmos aún más rápidos, pero complejos, que se utilizan en computación de alto rendimiento.

Esto ilustra que, incluso para el mismo problema, pueden existir algoritmos con distintas complejidades, lo que tiene un impacto directo en aplicaciones reales.

Finalmente, cabe señalar que, además del análisis matemático, también es posible estudiar el comportamiento de un algoritmo de forma experimental o simulada. Estos métodos de análisis estarán disponibles en los recursos de profundización.

La teoría de grafos es un área relativamente reciente dentro de las matemáticas, aunque sus orígenes se remontan a 1735, cuando el matemático Leonhard Euler planteó y resolvió el célebre problema de los siete puentes de Königsberg (Levin 2022). Desde entonces, esta teoría ha crecido hasta convertirse en una herramienta clave en la ciencia moderna, con aplicaciones que abarcan desde la informática y la biología hasta la ingeniería y la seguridad de redes. A pesar de su juventud como disciplina formal, la teoría de grafos combina una belleza sencilla con una sorprendente profundidad: muchos de sus conceptos básicos pueden entenderse con pocos conocimientos matemáticos, pero continúa siendo un campo de investigación activa que genera miles de trabajos científicos cada año.

El problema de los puentes de Königsberg marca el inicio de esta disciplina. La pregunta era aparentemente sencilla: ¿es posible recorrer todos los puentes de la ciudad cruzando cada uno una sola vez, sin levantar el lápiz del papel? La genialidad de Euler fue abstraer este problema en términos de regiones y conexiones, sentando así las bases de lo que hoy conocemos como grafos. La siguiente figura muestra esta evolución: a la izquierda, el mapa original de la ciudad con sus puentes; en el centro, una primera abstracción en regiones conectadas; y a la derecha, la representación como un grafo. Esta manera de pensar, transformando problemas reales en estructuras matemáticas, es la esencia de la teoría de grafos.

Figura 1

El problema de los siete puentes de Königsberg y su representación como grafo

Con el tiempo, se descubrió que este enfoque no solo servía para resolver un problema de puentes, sino que permitía abordar preguntas muy variadas: desde determinar si se puede dibujar una figura sin levantar el lápiz, hasta analizar la complejidad de resolver un cubo de Rubik. Más adelante exploraremos varias de estas aplicaciones, que muestran la versatilidad y potencia de los grafos como herramienta matemática y computacional.

Antes de abordar aplicaciones más complejas, es necesario dominar la terminología básica de los grafos. Estos conceptos son esenciales para modelar y analizar estructuras en diversas áreas del conocimiento, incluida la informática.

DEFINICIÓN 1: Grafo

Sean V un conjunto finito y A un subconjunto de pares no ordenados de elementos de V. Se dice que G=(V,A) es un grafo. Al conjunto V se lo denomina vértices (o nodos) y al conjunto A, aristas. Para cada arista e={u,v}∈A, se dice que e une los vértices u y v. De manera intuitiva, un grafo está compuesto por puntos (vértices) y líneas que los conectan (aristas). Esta estructura permite representar visualmente relaciones entre objetos.

Ejemplo 1. Consideremos una red local de computadoras en una oficina. Sea V={a,b,c,d} el conjunto de computadoras, y A={{a,b},{a,c},{b,d},{c,d}} las conexiones físi cas entre ellas. El grafo resultante modela la red de conectividad.

Figura 2

Ejemplo de grafo

Un caso particular se da cuando una arista conecta un vértice consigo mismo; esto se denomina un lazo. Si un grafo no contiene lazos ni aristas repetidas, se lo llama grafo simple. En nuestro ejemplo, no existen lazos ni repeticiones, por lo que se trata de un grafo simple.

Un caso particular se da cuando una arista conecta un vértice consigo mismo; esto se denomina un lazo. Si un grafo no contiene lazos ni aristas repetidas, se lo llama grafo simple. En nuestro ejemplo, no existen lazos ni repeticiones, por lo que se trata de un grafo simple.

DEFINICIÓN 2: Grado de un vértice.

Sea G=(V,A) un grafo. Para cada vértice u∈V, el grado de u, denotado grad(u), es el número de aristas en A que contienen a u como uno de sus extremos. Si u está conectado consigo mismo mediante un lazo, este cuenta como dos.

Aplicando esta definición al ejemplo anterior:

\[ \operatorname{grad}(a) = 1, \quad \operatorname{grad}(b) = 3, \quad \operatorname{grad}(c) = 2, \quad \operatorname{grad}(d) = 2. \]

Este concepto conduce a un resultado clásico en teoría de grafos:

TEOREMA 1: Teorema del apretón de manos.

Sea G=(V,A) un grafo. Entonces se cumple:

\[ \sum_{u \in V} \operatorname{grad}(u) = 2|A| \]

Este teorema se puede interpretar así: si en una reunión se cuentan todos los apretones de manos que realiza cada persona, la suma total siempre será el doble del número de apretones realizados.

En muchos contextos, los vértices o las aristas pueden tener información adicional, como etiquetas, nombres o valores numéricos. A estos se los denomina grafos etiquetados, y se utilizan para representar estructuras como redes de comunicación, topologías de sistemas o relaciones con peso (por ejemplo, el ancho de banda entre nodos).

Figura 3

Ejemplo de grafo etiquetado

14.1.1. Grafos dirigidos

En ciertas aplicaciones, no solo importa que exista una conexión entre dos elementos, sino también la dirección de dicha conexión. Por ejemplo, en una red de servidores donde los datos fluyen de un nodo a otro, es fundamental conocer el sentido del envío.

DEFINICIÓN 3: Grafo dirigido.

Sean V un conjunto finito y A un subconjunto de pares ordenados de elementos de V. Se dice que G=(V,A) es un grafo dirigido o dígrafo. Al conjunto V se lo denomina vértices (o nodos) y al conjunto A, arcos. Cada arco (u,v)∈A indica una conexión que inicia en u y finaliza en v.

Ejemplo 2. Sea V={a,b,c,d} un conjunto de servidores y A={(a,b),(b,c),(d,b),(d,c)} los canales de comunicación unidireccional entre ellos. El grafo dirigido resultante representa cómo fluye la información entre los servidores.

Figura 4

ejemplo de grafo dirigido

En este contexto, si (u,v)∈A, decimos que v es un sucesor de u y que existe un flujo dirigido desde u hacia v.

DEFINICIÓN 4: Grados en un grafo dirigido.

Sea G=(V,A) un grafo dirigido. Para cada u∈V:

• El grado de salida, denotado (u), es el número de arcos que parten desde u.
• El grado de entrada, denotado (u), es el número de arcos que llegan a u.

Un vértice con grado de salida cero se llama sumidero, pues no transmite información. Por el contrario, un vértice con grado de entrada cero se llama fuente, ya que únicamente envía datos.

Finalmente, se verifica la siguiente propiedad:

\[ |A| = \frac{1}{2} \sum_{u \in V} \operatorname{grad}(u) \]

Esto implica que el número total de arcos es igual tanto a la suma de los grados de salida como a la suma de los grados de entrada.

Muchos sistemas que usamos en la vida diaria pueden representarse mediante grafos. Por ejemplo, la telefonía, la energía eléctrica, las tuberías de gas o incluso los sistemas de transporte aéreo pueden modelarse como grafos. De manera similar, las redes de computadoras, desde una pequeña red de área local hasta el sistema mundial de Internet que conecta millones de dispositivos, pueden describirse como grafos.

En todos estos casos, los vértices representan los puntos principales del sistema: estaciones de telefonía, generadores eléctricos, depósitos de gas, aeropuertos o servidores de Internet. Las aristas representan las conexiones entre ellos: cables telefónicos, tendidos eléctricos, tuberías de distribución, rutas aéreas o enlaces de red. El grado de un vértice indicaría cuántas conexiones tiene cada estación o nodo, y la adyacencia señala qué elementos están directamente conectados entre sí.

En el diseño de este tipo de sistemas suelen aparecer preguntas clave: ¿qué aristas se deben elegir para minimizar los costos?, ¿cómo garantizar que todos los vértices estén conectados?, ¿cuál es la mejor ruta para optimizar un servicio?

Una vez comprendida la definición general de grafo, es importante reconocer que existen diferentes tipos de grafos que se adaptan a necesidades y problemas específicos. Cada uno de ellos tiene propiedades particulares y se emplea en distintas aplicaciones, desde la organización de redes hasta la resolución de problemas lógicos o de optimización.

Un primer caso es el de los grafos simples, que ya mencionamos previamente. Estos son grafos que no tienen lazos ni aristas paralelas, es decir, no se permite que un vértice se conecte consigo mismo ni que existan varias aristas que unan al mismo par de vértices.

Otro tipo de grafo importante son los grafos bipartitos. En este caso, los vértices se dividen en dos conjuntos disjuntos, de manera que todas las aristas conectan un vértice de un conjunto con un vértice del otro. Nunca hay aristas entre vértices del mismo conjunto. Una aplicación clásica de los grafos bipartitos es la asignación de tareas: un conjunto representa a los trabajadores y el otro conjunto a las tareas, y las aristas muestran qué trabajador puede realizar cada tarea.

Figura 5

Ejemplo de un grafo bipartito con dos conjuntos de vértices

También encontramos los grafos completos, que se denotan por K_n. Un grafo completo con n vértices es un grafo simple en el que cada par de vértices distintos está conectado por una arista. Esto significa que no falta ninguna conexión posible. Por ejemplo, el grafo K_4 tiene cuatro vértices y seis aristas, y puede usarse para modelar una red en la que todos los elementos se comunican directamente entre sí.

Figura 6

El grafo completo K_4 y K_5

Podemos calcular fácilmente cuántas aristas tiene un grafo completo K_n. Como cada arista conecta a dos vértices distintos, basta contar cuántas formas hay de elegir un par de vértices entre los n disponibles. Esto corresponde a la combinación C(n,2), es decir,

\[ |A| = C(n,2) = \frac{n(n-1)}{2} \]

Por ejemplo, K_5 tiene C(5,2)=10 aristas, y K_10 tiene C(10,2)=45 aristas.

Otro concepto importante es el de camino, que corresponde a una sucesión de vértices en la que cada vértice consecutivo está conectado por una arista. Por ejemplo, en un grafo que representa una ciudad, un camino puede ser la ruta que conecta a distintos barrios pasando por calles consecutivas. En la siguiente figura se muestra un ejemplo de un camino entre los vértices a y d pasando por b y c.

Figura 7

Ejemplo de un camino en un grafo

Finalmente, un grafo se dice conexo si para cualquier par de vértices existe un camino que los une. En otras palabras, es posible desplazarse de un vértice a cualquier otro siguiendo una secuencia de aristas. Si un grafo no es conexo, se descompone en componentes conexas, que son los subgrafos en los que sí existe conexión entre todos sus vértices. Este concepto es clave, por ejemplo, en el análisis de redes de comunicación, donde queremos asegurarnos de que todos los nodos puedan intercambiar información entre sí.

Figura 8

Ejemplo de un grafo conexo y un grafo no conexo

Un último concepto que veremos en esta clase, es la distancia entre dos vértices. La distancia entre u y v en un grafo conexo G se define como el número mínimo de aristas que se deben recorrer para ir desde u hasta v siguiendo un camino dentro del grafo.

Ejemplo 3. Consideremos el grafo conexo de la figura anterior, con vértices a,b,c,d. En este caso:

\[ d(a,b) = 1, \quad d(a,c) = 2, \quad d(a,d) = 2, \quad d(c,d) = 1 \]

Por ejemplo, la distancia entre a y d es 2, pues el camino más corto es a→b→d.

La teoría de grafos no solo es una construcción matemática abstracta, sino que encuentra aplicaciones en numerosos contextos reales. A continuación presentamos algunos ejemplos ilustrativos.

Un caso famoso dentro de la matemática es el llamado número de Erdős. Paul Erdős fue un prolífico matemático húngaro que escribió más de 1,500 artículos en colaboración con cientos de colegas. Se define que Erdős tiene número 0, sus colaboradores directos tienen número 1, los colaboradores de estos (que no trabajaron directamente con Erdős) tienen número 2, y así sucesivamente. Este concepto se modela mediante un grafo en el que los vértices son investigadores y las aristas representan trabajos conjuntos. De esta manera, el número de Erdős es simplemente la distancia en este grafo de colaboración hasta el vértice que representa a Erdős.

Otro ejemplo aparece en ecología: las redes planta–polinizador. Estas redes pueden representarse como grafos bipartitos, donde un conjunto de vértices corresponde a las plantas y el otro a los polinizadores (como abejas o aves). Una arista conecta a una planta con un polinizador si existe una interacción entre ellos. Este tipo de grafos permite analizar la estabilidad de los ecosistemas y entender qué especies son clave para mantener el equilibrio de la red.

En el ámbito tecnológico, las redes de computación se representan de forma natural mediante grafos. Los vértices corresponden a dispositivos (computadores, servidores, enrutadores) y las aristas a las conexiones físicas o inalámbricas que permiten la transmisión de datos. A través de los grafos se puede analizar la conectividad de la red, optimizar rutas de comunicación y detectar vulnerabilidades en la seguridad.

En las redes sociales, cada usuario se representa como un vértice y las conexiones de amistad, seguimiento o interacción corresponden a las aristas. En el caso de amistad, sería un grafo no dirigido y en el caso de seguimiento, sería un grafo no dirigido (¿por qué?). El grado de un vértice nos indica cuántos amigos o contactos tiene un usuario, mientras que la distancia entre dos vértices refleja cuántos pasos (amistades intermedias) se necesitan para conectar a dos personas. Esto nos lleva a conceptos como los «seis grados de separación», que sugieren que cualquier persona en el mundo puede conectarse con otra a través de una cadena muy corta de conocidos, es decir, que, en el grafo de «conocidos», la sitancia entre cualqueir par de vértices es menor o iguala a 6.

Otro ejemplo lo constituyen las redes viales. Aquí los vértices representan ciudades o intersecciones y las aristas representan carreteras que las conectan. Si además asignamos un peso a cada arista, como la longitud de la carretera o el tiempo estimado de viaje, obtenemos un grafo ponderado. Este tipo de grafo permite aplicar algoritmos para encontrar la ruta más corta entre dos ciudades, identificar caminos alternativos en caso de cortes de tráfico o diseñar rutas óptimas de transporte de mercancías.

Finalmente, un ejemplo cotidiano son las redes de aeropuertos. En este caso, los vértices son los aeropuertos y las aristas representan los vuelos directos entre ellos. El concepto de grado adquiere aquí un significado muy útil: el grado de un aeropuerto corresponde al número de conexiones directas que ofrece. Aeropuertos con un grado muy alto, como Atlanta o Dubái, funcionan como hubs internacionales que permiten la conexión rápida entre distintas partes del mundo. Analizar estos grafos es clave para optimizar rutas de vuelo, gestionar tráfico aéreo y evaluar la vulnerabilidad frente a interrupciones en aeropuertos estratégicos.