Teoria de grafos:

Estructura matemática utilizada para representar y analizar relaciones entre un conjunto de

elementos. El estudio de los grafos comenzó en 1736, cuando Leonhard Euler resolvió el
famoso problema de los puentes de Königsberg.

Está formado por dos componentes fundamentales:

• Nodos: Representan unidades del dominio: personas, ciudades, proteínas, servicios,

documentos, etc. Pueden llevar atributos (tipo, categoría, etiquetas, tiempo) y roles (por
ejemplo, en grafos bipartitos).

• Aristas: son las conexiones o relaciones que vinculan pares de vértices.

Clasificación Básica de Grafos:

• No dirigidos: Las aristas son conexiones bidireccionales, sin sentido específico. Relación
simétrica. Matriz simétrica.

➢ Redes sociales basadas en amistad: la conexión implica reciprocidad.

• Dirigido: Las aristas tienen un sentido definido que va de un vértice a otro. Relaciones
asimétricas. Matriz Asimétrica.

➢ Twitter: seguir a un usuario no implica reciprocidad.

• Ponderados: Cada arista lleva un peso (costo, distancia, etc.).

➢ Transporte: trayecto más corto o barato.

• Simple: No admiten lazos ni aristas múltiples. Conviene cuando el dominio prohíbe

relaciones redundantes o auto-relaciones y cuando interesa estudiar estructura más que
multiplicidad.

➢ Redes eléctricas básicas con mínima redundancia.

• Multigrafos: Permiten múltiples aristas entre los mismos vértices y también lazos. Útil para
modelar paralelismo y redundancia.

➢ Finanzas: múltiples transacciones entre las mismas cuentas.

• Completos: Cada par de nodos distintos está conectado por una arista.

➢ Comparaciones de pares: todos evalúan a todos.

• Bipartitos: Los vértices se dividen en dos grupos; las aristas solo conectan vértices de
grupos distintos.
 ➢ Mercado laboral: empresas ↔ candidatos.

Importancia y Aplicaciones:

• Sistemas de transporte y logística: Representan carreteras, líneas de tren, rutas aéreas o

marítimas. Permiten optimizar recorridos mediante algoritmos como Dijkstra o A*.

• Química: Representación de moléculas, donde los átomos son vértices y los enlaces son
aristas.

• Análisis de datos y motores de búsqueda: Algoritmos como PageRank modelan la web

como un grafo dirigido de páginas y enlaces.

• Inteligencia artificial y teoría de juegos: Modelan espacios de estados, problemas de

planificación y estrategias.

Las “V” del Big Data vistas desde grafos:

• Cuando el número de vértices y aristas de un grafo es enorme (piensa en toda la red de

Facebook o el grafo de la web completa), incluso leer el grafo completo ya consume mucho
tiempo y recursos. Si un algoritmo tiene que procesar cada vértice y cada arista, puede
volverse demasiado lento. Por eso, se buscan algoritmos sublineales (que miren solo una
parte del grafo) o casi lineales (que no crezcan mucho más rápido que el tamaño del grafo).

Aquí entran técnicas como:

➢ Muestreo: mirar solo una muestra representativa del grafo.

➢ Sketching: comprimir información clave del grafo en una estructura más pequeña
para procesarla rápido.
➢ Sparsificación: crear una versión “más ligera” del grafo conservando sus
propiedades importantes.

• En muchos casos el grafo cambia en tiempo real — por ejemplo, las conexiones entre
usuarios en Twitter minuto a minuto. Esto es un flujo de aristas (edge stream): nuevas
aristas aparecen y otras desaparecen constantemente. No podemos guardar todo ni
procesarlo de cero cada vez que cambia. Por eso, se necesitan algoritmos que:

➢ Hagan una sola pasada o muy pocas sobre los datos que llegan.
➢ Usen memoria sublineal (mucho menor que el tamaño total del grafo).
➢ Mantengan estadísticas aproximadas, como el número estimado de triángulos o la
información de conectividad.
 • No todos los grafos son simples. Pueden ser multigrafos (varias aristas entre dos
vértices), grafos dirigidos (con flechas) o atribuidos (nodos y aristas con información extra).
Un caso especial son los hipergrafos, donde una “arista” puede conectar a más de dos
vértices a la vez. Esto es útil para modelar relaciones grupales complejas (ej. autores de un
artículo, miembros de un equipo). En estos casos se usan ideas de teoría
de homomorfismos y herramientas de tensores, que permiten representar y procesar
relaciones entre más de dos elementos a la vez, facilitando consultas complejas sin perder
la estructura original.

Modelos Aleatorios

• Erdős–Rényi (ER): Cada par de nodos se conecta de forma independiente con la misma
probabilidad. Es el “modelo nulo” más simple y permite calcular umbrales precisos para la
aparición de propiedades.

• Modelo de Configuración: Genera grafos que conservan exactamente la secuencia de

grados dada (o su distribución), uniendo “medios-enlaces” al azar. Sirve para
capturar colas pesadas (muchos nodos con pocos enlaces y unos pocos con muchísimos),
una característica muy frecuente en datos del mundo real que ER no captura.

• Preferential Attachment: Los nodos nuevos que se añaden al grafo se conectan con mayor
probabilidad a nodos que ya son populares (tienen un grado alto). Es un mecanismo de "el
rico se hace más rico". Como concecuencia produce de forma natural grafos con leyes de
potencia en su distribución de grados, donde aparecen unos pocos "hubs" con muchísimas
conexiones.

Límites de Grafos

• Graphons (Régimen Denso): Representar una secuencia de grafos densos por un objeto
límite continuo

• Graphex (Régimen Escaso): Muchos grafos reales son escasos (pocas aristas por nodo) y
sus grados no están acotados (tienen hubs). Los graphons no funcionan bien en este
régimen.
Big Data introducción:

Definición: Datos que dado su volumen, velocidad y variedad requieren de nuevas formas de
procesamiento. Es como un paradigma. Surge con la posibilidad de internet que trae una
gran cantidad de datos (volumen, velocidad y variedad), algoritmos para trabajarlos,
hardware nuevo para procesarlos, etc.

En la primera época de internet no había interacción entre usuarios, solo con el server,
luego aparece wpp y la interacción si surge y por ultimo algunos dicen que esta la etapa de
blockchain.

GNN: Redes neuronales especializadas en manejar datos estructurados en forma de

grafos. Los nodos representan entidades tipo usuarios y videos mientras que las aristas
capturan relaciones. Las GNN aprenden representaciones mediante la agregación iterativa
de información desde los nodos vecinos.

Ley de potencia: se da cuando tenemos relaciones asimétricas. Se aplica a internet.

Primero relación usuario-server, después entre usuarios y aparecen las plataformas esto
trajo una gran concentración de información y un gran aumento.

Si modelizamos con la ley de potencia, habrá pocos elementos que acaparan mucho en
este caso pocos con múltiples conexiones.
Se empieza a descentralizar, para estudiarlo aparece el sistema CAP:

• Consistencia: Hago transacción A->B (a A le resto a B le sumo).

• Partición: Si una parte puede dejar de funcionar y el resto funciona.
• Disponibilidad: La información está disponible todo el tiempo.

No se pueden dar las 3 a la vez. Se aplica a sistemas distribuidos (estos aparecieron con
BigData).

Sharding: Dividir una base de datos para solventar caídas.

Los puentes de Königsberg y la teoría del apretón de manos:

Había 7 puentes que conectaban 4 masas de tierra. Lo que se preguntaban era si se podía
recorrer todos y volver al principio sin repetir los caminos.

Euler introdujo la idea de grafos intentando resolver ese problema (el de Hamilton es sin
repetir nodos, estas aristas).

Es una de las primeras ideas de grafos.

Acá dejamos de lado la parte geométrica, se ve la estructura topológica. Grafo equivalente
(tiene la misma cantidad de nodos, aristas y grado) y plano. Es una manera de dibujar el de
Königsberg.

Todos los nodos tienen grado impar, por ende, nunca se podrá recorrer todos los puentes
sin repetir.

A su vez la suma de los grados da par.

Este serio grafo no dirigido, puedo ir de c-a y a-c.

Este Grafo a su vez es conexo→ de un punto puedo ir a cualquier otro.

Teorema de apretón de manos:

La sumatoria de los grados es el doble del número de aristas.

Por ejemplo, (Suma de grados) /2 =aristas.

La sumatoria de los grados debe ser para siempre.

Para cumplir el handshake la cantidad de impares debe ser par.

Según Euler:

Si todos los nodos tienen por ejemplo grado par (una entrada y una salida) tenemos un
ciclo. De esta manera podemos recorrer el sistema entero sin repetir aristas y volver al
nodo origen. Si tenemos 2 pares y 2 impares tenemos un camino, uno de entrada y uno de
salida, para que sea un ciclo podemos armar un grafo equivalente agregando una arista
entre los dos impares.

Se define un rango(0<=x/y<=2) y defino mis 9 conjuntos→

El 00, 01 y 02 serían validos

El 10 11 12 serían validos

El 20 21 22 serían validos

Cada conjunto será un nodo y con esta fórmula determino la distancia eucidiana entre
nodos, luego realizo el grafo:

Grafo de cuadricula: No dirigido. Simula una malla, y no hay conexiones diagonales.

Tenemos n filas y m columnas.

Cantidad de nodos = N*M

Cantidad de aristas= (n-1) m+(m-1) n

Distancia de manhattan→ Representa el camino más corto en cantidad de aristas dentro

de la cuadrícula, cuando solo se permiten movimientos arriba, abajo, izquierda y derecha.

Distancia=∣x1−x2∣+∣y1−y2∣

Gemelos digitales: Replica virtual de un sistema físico complejo, se actualiza con datos en
tiempo real de sensores. Un grafo de malla puede ser la estructura de datos subyacente
para un gemelo digital de por ejemplo una ciudad entera.

Un análisis sobre este grafo me permite predecir fallos, optimizar operaciones, etc.

Explorador DFS con Back tracking:

Árbol de exploración (Camino Euleriano): Detecta patrones en grafos, detecto caminos y ciclo.

Va de nodo a nodo en profundidad, si cumple todas las aristas es un camino, otra posibilidad toma
otro camino. Va siempre para adelante hasta chocarse con una pared, si no tiene salida vuelve
para atrás y sigue por otro.

Push agrega a la pila, Pop (Se usa método LIFO) saca el ultimo elemento.

No toma paralelas en multigrafos por ende en teoría hay más resultados de los marcados.

Grafos Regulares:

Todos los Nodos tienen igual grado ejemplo un triángulo, un cuadrado. Me dan pautas muy
predecibles que las puedo utilizar.

Grafos Irregulares:

Todos los Nodos no tienen igual grado. Ejemplo en redes sociales, no todos tienen las mismas
conexiones. Me permiten ver situaciones de peligro.
¿Puede haber un grafo Totalmente Irregular?

0 1 2 3 4 → CINCO NODOS N-1 GRAFO SIMPLE (no Loop)

Si esta 0 no puede estar N-1 y N-1 no puede tener 0

Entonces

1 2 3 → Grado 6 se cumple el handshake

0 1 2 3 4 5 6 → 6 no se puede, y el 0 no existe, por ende, el HS me da 15 por ende no se puede

construir.

Sumatoria de números enteros:

(N*(N-1)) /2 → Si ponemos N=5 nodos → 10 al ser par se puede como vimos arriba

Si pongo 6 me da 15, es impar por ende no se puede el grafo completamente irregular con 6).

Grafo simple no dirigido se lo conoce como k-regular si todos tienen mismo grado. (siendo k el
grado común). Lo fácil es multiplicar la K por la cantidad de nodos.
Todos los regulares siguen el teorema de apretón de manos.

Grafo Bipartito Regular:

Si el grafo es bipartito con particiones UUU y VVV:

Todos los vértices de UUU tienen grado kkk.

Todos los vértices de VVV también tienen grado kkk.

Esto implica que ambos conjuntos deben tener el mismo tamaño.

Principio del palomar

Tengo N, cada uno debe tener un grado distinto ósea entre 1 y N-1 por ende tengo menos, esto
quiere decir que tengo más vértices que nodos. Esto quiere decir que no existe un grafo totalmente
irregular. Lo mínimo es que 1 se repita ya que es N-1
Esto se aplica a grafos simples, En multigrafos puedo tener multigrafo irregular. Con los
ponderados, al asignar diferentes valores también podre tener uno completamente
irregular.

Con el de apretón de manos solo, me falta algo, por eso introduzco el principio del
palomar, eso me lleva a que no es posible construir un grafo completamente irregular.

Teorema: La pareja complementaria Única:

Grafo casi irregular.

Únicamente dos irregulares y el resto regulares. Estos son complementarios entre si

El complementario misma cantidad de nodos, pero se le agrega una conexión más.

Miramos la cantidad de nodos hago (N-1) - (Grado del nodo) → esto me dará el grado del
nodo en el grafo complemento y lo que obtenemos es lo más irregular que podemos tener.
Cuando hablan de familia 1 y familia 2, lo que se quiere remarcar es cómo se transforman
los vértices extremos (los que tienen grado máximo o grado mínimo) al pasar al
complemento.

Aplicación practica:

Tenemos (3,3,2,2) Grados de nodos

Para construir teorema de HH

Verificamos que se cumpla el apretón de manos.

Ordenamos de mayor a menor, sacamos el 3(habrá uno de ese grado)

Nos queda (3,2,2)→ Reordenamos ya que como sacamos a ese a todos les resta un grado

(2,1,1) → Los sacamos y pasa lo mismo (1,1) ahora nos queda (0,0) esto quiere decir que
podemos construir el grafo. No nos queda nada sin conectar.

No estamos demostrando nada, con este construimos un grafo)

De secuencias a redes:

Teorema de HH para tecnología Blockchain.

Primero construimos. Tenemos 40nodos k6.

Se demostró que quedo todo en 0 como hicimos antes. Va nodo por nodo.

Para hacer una red descentralizada uso el GOSSIP (método de comunicación en redes
descentralizadas que imita cómo se esparce un rumor), hay diferentes tipos por ejemplo
anillo, sunflower, etc.

Apache cassndra utiliza un sistema gossip de anillo.

Si tengo

4,4,3,3,2,2,2,2
Decimos que esta balanceado.

3,3,3,1

Se ve que falla ya que hay un grado no tuvo ningún nodo (da negativo), por ende, no se
puede construir. Hay inconsistencia en la construcción del grafo.

¿Qué aplicamos acá?

¿Como puedo optimizar las redes P2P para que sean rápidas y seguras?

Esos nodos (3,3,2,2) me determinan la demanda.

Dependiendo la estructura que elija puedo ver que me sirve más.

Grafos de Cayley

Sirve para estudiar grafos regulares. Es un grafo cíclico.

Tenemos dos ideas:

Grupo: En los grafos de Cayley, la idea de "grupo" se refiere a una estructura algebraica en
matemáticas. No es un grupo de personas, sino un conjunto de elementos junto con una
operación que cumple cuatro propiedades específicas.

1. Cerradura: Si tomas dos elementos cualesquiera del conjunto, a y b, y los operas

(a∗b), el resultado también debe estar en el conjunto G.

2. Asociatividad: El orden en que se agrupan los elementos no afecta el resultado. Es

decir, (a∗b)∗c=a∗(b∗c) para cualquier a,b,c en G.

3. Elemento Neutro (o identidad): Existe un elemento, digamos e, en el conjunto G,

tal que al operarlo con cualquier otro elemento, el resultado es ese mismo
elemento. Es decir, a∗e=e∗a=a para todo a en G.

4. Elemento Inverso: Para cada elemento a en G, existe un elemento inverso,

digamos a−1, también en G, tal que al operarlos, el resultado es el elemento neutro:
a∗a−1=a−1∗a=e.

Conjunto generador (genera todas las aristas)

Tenemos Z4 nodos (0,1, 2, 3)

Conjunto generador X+-=1

1-1=0

M4=1,3 → 1+3=4

4=0
 cuando me paso de 4 hago la división y pongo el resto

3+1=4=0

2+2=4=0

0-dezplazo un lugar> 1

0-+3>3

1-+1>2

1-+3>4 que en modulo 4=0

2+1=3

2+3=1(5-4)

3+1=0

3+3=2(6-4)

Tendremos 4 pares de nodos(al ser no dirigido no importa si voy de 0-1 o 1-0, nos
quedamos con 1 de cada uno y tenemos)

0-3

1-0

1-2

2-3

Conjunto generador simétrico es que cada nodo tenga el mismo grado, por eso se aplica a
regulares.
Conjunto ciclico 4→( 0,1,2,3) como es de caley tendrá conjunto generador para obtener
las aristas.

Según HandShake.

Sharding:

Shard físico: El hardward.

Shard lógico: Este es a partir del físico.

Tenemos la bace centralizada. Y distribuimos esa base, donde cada una tendrá su propio
server. Los datos estarán distribuidos.

Para asignar estos shards hay ciertos criterios que nos aseguren el balanceo de cargas:

Tengo 4 servers, por ejemplo.

Aritmetica modular (el resto será 0;(el numero anterior al total)

13(dato)/4(cantidad de servers) → 4X3+1(asigno a server 1)

Si tenemos modulo 2 cada impar ira al server 1, y podemos sobrecargar.

Funciones Hash -> me da balanceo de carga

ID (dato)→ le aplico hash → me da binarios → lo transformo a entero→ uso AM

Esto es estático, si arranco a agregar bases ya me da problemas ya que tengo que mover
datos.

Tenemos de vuelta 2→

10/2 → 0

11/2 → 1

13/2 → 1

Ahora quiero agregar otro server entonces tengo 3

10/2 → 1

11/2 → 2

13/2 → 1

Al 10 y al 11 lo tuve que mover.

Hay un problema ya que, al hacer cambios de datos, si estamos hablando de millones de

datos es muy costoso.

Usar modulo es solo para estático (no voy a cambiar la cantidad de servers)

Sistemas distribuidos y CAP: Cassandra:

Divido nodos en forma de anillos, cada uno tiene un rango.

Establezco rangos de responsabilidad.

Donde caiga, afecta solo a ese.

Dejamos de lado a Aritmetica modular.

Apache Cassandra es un sistema de base de datos NoSql.

Gossip → Cuando tenemos muchos nodos es importante. Propagación de información,

cada uno le informa a algún otro nodo, y así se distribuye. Del punto de vista de los grafos
si todos están conectados entre si se llama grafo completo, es decir si bien

En apache Cassandra usamos un anillo donde cada nodo tiene tokens(rango) y al hacerlo
así se distribuye. No afecta si quitamos o agregamos nodos. En cuanto a la comunicación
es mediante gossip (grafo completo).

Algoritmo de Havel–Hakimi

El algoritmo de Havel-Hakimi es un procedimiento recursivo que permite determinar si una

secuencia de grados puede corresponder a algún grafo simple (es decir, si es gráfica). La
idea central es satisfacer primero al vértice con mayor grado y verificar si esto puede
realizarse consistentemente.

Pasos del algoritmo

1. Ordenar:
La secuencia se ordena en orden no creciente:

𝑑1 ≥ 𝑑2 ≥ ⋯ ≥ 𝑑𝑛

2. Reducir:

o Se elimina el primer grado 𝑑1 de la secuencia.

 o Luego se resta 1 a los siguientes 𝑑1 elementos de la lista.

3. Verificar:
Si en algún momento un grado se vuelve negativo, la secuencia no es gráfica y el
algoritmo se detiene.

4. Repetir:
Se vuelve a aplicar el proceso desde el paso 1 con la secuencia reducida.

5. Condición de Éxito:
Si finalmente todos los grados llegan a 0, la secuencia es gráfica.

Idea intuitiva

Si existe un grafo posible para una secuencia, entonces el vértice con mayor grado debe
poder conectarse a los vértices con los grados inmediatamente más altos. El algoritmo
verifica justamente si esa estructura es posible.
Regularidad en los Grafos de Cayley

Un Grafo de Cayley Cay(𝐺, 𝑋)es siempre regular debido a su forma de construcción.

caylRazón de la regularidad

• Para cualquier vértice 𝑔del grafo, sus vecinos son los elementos de la forma:

𝑔 ∗ 𝑥para cada 𝑥 ∈ 𝑋

• Como el conjunto de generadores 𝑋no contiene el elemento neutro y todos sus

elementos son distintos:

o Cada generador 𝑥produce un vecino distinto.

o Entonces cada vértice 𝑔tiene exactamente ∣ 𝑋 ∣vecinos.

Conclusión

El grafo es ∣ 𝑋 ∣-regular, es decir, cada vértice tiene el mismo número de vecinos, igual a la
cantidad de generadores en 𝑋.

Algoritmo de Dijkstra
Para ponderados (positivos) se usa este algoritmo para calcular un camino más corto
desde un nodo a todos los demás.

Su objetivo es encontrar el camino de menor costo.

A medida que este algoritmo avanza es un árbol de caminos mínimos.

Tiene múltiples aplicaciones logísticas.

Nos puede ayudar por ejemplo a encontrar la forma más barato de transferir bitcoin.

Algo actual seria a un problema de optimización en tecnología blockchain.

Tiene una estrategia voraz:

1) Inicialización: Se asigna una distancia de 0 al nodo de origen. Las distancias a los

demás nodos son desconocidas.
2) Expansión y actualización de distancias:
• Desde el origen se va al nodo más cercano no conocido.
 •Desde ese se evalúan los vecinos (por cada uno se calcula una distancia
potencial, Suma de distancia al actual y el peso del vecino)
• Si es menor, se actualiza la distancia del vecino y se guarda el nodo actual
como predecesor.
3) Repetición.

Lightning Network
Surge como un problema de escalabilidad de Bitcoin.

Su propósito es habilitar pagos casi al instante y con comisiones muy bajas.

Tenemos 2 capas

• Capa 1 es el protocolo.
• Capa 2 es donde se hacen las transacciones, se generan canales.

Ejemplo, quiero hacer una transferencia: le doy a A, A le da a B y así hasta llegar a quien
quiero. Se forma una cadena.

Ventaja: Bajo costo y escalabilidad.

Limitaciones: Liquidez, complejidad de uso y ruteo.

Árbol
Grafo acíclico y conexo.

Puedo definirse como un grafo no dirigido.

Por ejemplo, un organigrama.

Grafo de Merkel
Es una estructura de datos en forma de árbol binario usada para verificar datos de manera
segura.

Cada nodo hoja representa un bloque de datos y cada nodo intermedio guarda el hash de
sus hijos.

La raíz representa el hash global.

Se usa en BLOCKCHAIN, BITCOIN, SISTEMAS DISTRIBUIDOS, ETC.

No es un grafo hamiltoniano.

ZKP
Protocolo que permite a un “probador” convencer a un “verificador” de que una afirmación
es verdadera, sin revelar información adicional. --> Pruebas de conocimiento 0

El hilo conductor es el principio de la revelación mínima de datos → proteger la privacidad

y optimizar la eficiencia.

No resuelven problemas difíciles, sino que aprovechan la brecha de dificultad de

encontrar una solución y la facilidad de verificarlo. (Elementos No p).

Isomorfismo de grafos
Dos grafos son isomorfos si sus estructuralmente idénticas. Existe una correspondencia
uno a uno entre sus vértices que preserva perfectamente todas las conexiones. Es
biyectivo. Si o si Misma cantidad de vértices, aristas y grado.
Problemas P y no P (tiempo polinómico y tiempo no polinómico)
El Tiempo polinómico es algo que podemos resolver y probar la solución rápidamente.
Ejemplo tengo una llave y veo si abre la puerta.

Lo contrario es por ejemplo el problema del viajante, que tiene la solución, pero es casi
imposible llegar a esta, por ejemplo, tengo un millón de llaves.

Euleriano problemas p, hamiltoniano no p.

Los isomorfos están entre p y no p ya que determinar un grafo isomorfo puede ser
rapidísimo, pero llegar a construirlo puede tardar mucho (da seguridad).

P → Asociado a N y N^2

NP→ Asociado a 2^n y factoriales → cada vez que los nodos aumentan la complejidad
también lo hace.

Tiempo polinomio: Se puede manejar por la computadora.

Tiempo exponencial: crece demasiado, ya no puede ser manejado.

Teoría de la complejidad.
En la teoría de la complejidad, "eficiente" es un término técnico que se refiere a un
algoritmo cuyo tiempo de ejecución escala de manera razonable a medida que aumenta el
tamaño de la entrada. La línea que la comunidad científica ha trazado para "razonable" es
el tiempo polinómico.

El enigma del millón de dólares

No podemos transformar un problema no p en p.

Grafos hamiltonianos
Ahora veremos si es posible recorrer todos los nodos de un grafo (problema del viajante
busca el ciclo hamiltoniano).

Los algoritmos genéticos se pueden aplicar al camino hamiltoniano.

Un Grafo completo siempre es hamiltoniano. La cantidad de caminos hamiltonianos será

de n! /2.
Un grafo conexo no es obligatoriamente hamiltoniano, por ejemplo:

Camino hamiltoniano: Cada vértice se recorre una vez. La longitud del camino será n-1.
Linealización. Planificación de rutas de inspección.

Ciclo hamiltoniano: No repite vértices, pero termina en el mismo. Secuencia de v1 a Vn.

Hay una arista que conecta el inicio con el final. Tiene longitud n. Problema del Viajante
(TSP), Planificación de rutas de transporte público.

Grafo hamiltoniano: Si posee un ciclo. (si al ciclo le quito una arista forma el camino, pero
si tengo camino no me aseguro ciclo).

Determinar que un grafo arbitrario es hamiltoniano es un problema np completo (No se

conoce algoritmo que pueda determinar si es o no es en tiempo polinomial, no tenemos
condiciones necesarias y suficientes como si en Euler) → por esto se busca condiciones
suficientes.

En Hamilton: La propiedad de ser hamiltoniano depende de la estructura global del grafo

de una manera más sutil. El grado de los vértices no es tan relevante. La conectividad
global entre vértices y no solo la local de cada uno es lo que prima.

Dado el Np-completo se centra en:

Condición suficiente: Teorema de Dirac o Bondy–Chvátal, que garantizan que un grafo es

hamiltoniano si se cumplen ciertos umbrales de grado mínimo o condiciones sobre el

Condición necesaria: Propiedad que todo grafo hamiltoniano debe satisfacer. Ej: un grafo
no puede tener vértices de corte; en un grafo bipartito, para ser hamiltoniano, los
conjuntos de la partición deben tener igual tamaño (𝑥 = 𝑦).
Podemos decir que el problema de los hamiltonianos (basado en nodos): No hay teorema
local (ver cada nodo por separado) para determinar si hay un camino o ciclo, por ende,
puede ser fácil de verificar, pero muy difícil saber si hay una solución (Np completo, y el del
viajante np hard).

En estos lo global no puede simplificarse a lo local como si en Euler.

Los teoremas son suficientes, si se da se da, pero puede no cumplir y que sea
hamiltoniano igualmente. Necesitamos métodos heurísticos.

Desarrollo de condiciones suficientes

Teorema de Dirac: Un grafo simple con 𝑛 ≥ 3 vértices es hamiltoniano si el grado de cada
vértice es al menos 𝑛/2.

Teorema de Ore: Un grafo simple con 𝑛 ≥ 3vértices es hamiltoniano si para todo par de
vértices no adyacentes 𝑢, 𝑣, se cumple que 𝑑𝑒𝑔(𝑢) + 𝑑𝑒𝑔(𝑣) ≥ 𝑛.

Teorema de Bondy–Chvátal (cierre de un grafo): Un grafo es hamiltoniano si y solo si su

cierre (grafo resultante de unir pares de vértices no adyacentes cuya suma de grados ≥ n)
es hamiltoniano.

Grafo trazable
Se puede graficar.

El problema del viajante de comercio (TSP)

Problema de optimización combinatoria.

Dado x ciudades, sus distancias entre ellas y todas conectadas con todas (grafo
ponderado completo y np hard), TSP consiste en encontrar el recorrido más corto (mínimo
costo) que visita cada ciudad una vez y volver a la ciudad de partida.

Este sería un circuito hamiltoniano.

Resumen:

• Grafo Completo Ponderado:

- Ciudades → vértices.
- Se asume posible viajar entre cualquier par de ciudades → grafo completo Kn
- Arista {vi, vj} representa la ruta directa entre ciudad i y j.
 • Pesos en las Aristas:
- Cada arista tiene un peso (costo) → distancia, tiempo o costo monetario.
• Ciclo Hamiltoniano:
- Tour que visita cada ciudad exactamente una vez y regresa al inicio.
- Es un ciclo Hamiltoniano en teoría de grafos.
• Objetivo del TSP:
- Encontrar el ciclo Hamiltoniano de peso (costo) total mínimo en el grafo
completo ponderado.

Dificultad de TSP (np completo):

(𝑛−1)!
El número posible de tours en un grafo d n ciudades = 2

Porque cada ciudad se conecta con todo el resto. Esto lleva a que haya muchísimas
posibilidades, esto hace inviable la fuerza bruta.

La ruta más optima será np difícil→ es tan difícil de encontrar como un np completo, y no
se conoce un algoritmo que lo resuelva en tiempo polinomial.

Con 10 nodos hay 9! Combinaciones posibles y entre ellas el de menor costo. Tenemos un
problema de optimización, en este caso es no hard.

Puede haber muchos ciclos hamiltonianos, pero uno será más barato que el resto,
entonces los pondero, y ahora de esos tengo que encontrar el de menor costo es ahí donde
se agrega la optimización.

NP Completo y Hard
NP-Completo: Son los problemas más difíciles dentro de NP. Un problema es NP-
Completo si:

1. Está en NP (verificable rápidamente)

2. Todo otro problema en NP se puede reducir a él en tiempo polinómico. Son las
"Joyas de la Corona" de la dificultad en NP. Si resuelves uno eficientemente, los
resuelves todos.
NP-Difícil (NP-Hard): Son problemas al menos tan difíciles como los NP-Completos, pero
no necesariamente están en NP. Esto puede ser porque no son problemas de decisión (ej.
TSP de optimización) o porque son indecidibles (ej. Problema de la Parada).

“Si solucionamos nph solucionamos → npc y si solucionamos este, cualquiera → np”

Tour en el TSP
Un tour en el TSP es un recorrido cerrado que comienza en una ciudad de origen, visita
cada una de las otras ciudades exactamente una vez, y finalmente regresa a la ciudad de
origen.

Si se fija la ciudad θ como origen, un tour se representa como una secuencia o

permutación de ciudades: (𝜃, 𝜋(1), 𝜋(2), … , 𝜋(𝑛 − 1), 𝜃) →

donde n es el número total de ciudades y (π (1), …, π(n−1)) es una permutación de las

ciudades restantes.

Costo de un Tour

El costo total de un tour, denotado como L (𝜋), es la suma de las distancias de cada tramo
recorrido. Este costo se descompone en tres componentes:
 • Primer Salto: La distancia desde el origen (θ) hasta la primera ciudad visitada (π (1)).
• Saltos Intermedios: La suma de las distancias entre las ciudades intermedias,
desde π(k) hasta π(k+1), para k desde 1 hasta n−2.
• Último Salto: La distancia desde la penúltima ciudad visitada (π(n−1)) de vuelta al
origen (𝜃).

Método de fuerza bruta

El método de fuerza bruta es la estrategia más directa para resolver el TSP. Consiste en
enumerar sistemáticamente todas las permutaciones posibles de las ciudades, calcular el
costo de cada tour correspondiente, y seleccionar aquel que tenga el costo mínimo.

Flujo Operativo del Algoritmo:

1. Fijar Origen: Se elige una ciudad (ej. '0') y se fija como punto de partida y llegada (𝜃).
Esto se hace para evitar contar las rotaciones del mismo ciclo como tours distintos.

2. Generar Permutaciones: Se crean todas las secuencias posibles de las n-1

ciudades restantes (las que no son el origen fijo).

3. Calcular Costos: Para cada permutación generada, se calcula el costo del tour
completo L(π), sumando la distancia de todos los tramos.

4. Elegir Mínimo: Se mantiene un registro del mejor tour encontrado hasta el momento
(el de costo mínimo), y se actualiza cada vez que se halla un tour con un costo
inferior.

La búsqueda por fuerza bruta intenta probar todas las posibles permutaciones de vértices.

Si el grafo tiene 𝑛 vértices el número de permutaciones posibles es 𝑛! , lo que lleva a que

sea muchas veces computacionalmente inviable de resolver en tiempo polinómico con un
método exacto como este. Recordemos que el tsp es un problema npHard.

Optimización convexa vs no
La optimización convexa es en tiempo polinómico. En los modelos convexos (como la
regresión lineal, SVM lineal o la regresión logística) las funciones de pérdida son convexas,
lo que garantiza la convergencia a un único óptimo global de forma eficiente. Si es convexo
no hay problema: tenemos condiciones necesarias y suficientes.
En la optimización no convexa tenemos múltiples mínimos, por eso estos están asociados
a problemas NP y hasta NP-difíciles. En este tipo de problemas, como ocurre en el Deep
Learning, encontrar el mínimo global es NP-hard, por lo que la meta práctica es hallar un
mínimo local que generalice bien. Es acá donde uso métodos heurísticos.

Propiedad convexa no convexa

Único mínimo global sí no

garantía de sí (con métodos de no (puede quedar en óptimo

convergencia gradiente) local)

complejidad típica clase p (eficiente) np-hard (intratable)

Algoritmo Heurístico vs Exacto

El heurístico es un algoritmo diseñado para resolver un problema de una manera más
rápida y eficiente que los exactos, especialmente cuando estos últimos son
computacionalmente inviables. Busca la eficiencia.

Su característica fundamental es que opera bajo un compromiso (trade-off) entre dos

factores clave:

• Optimalidad: garantía de encontrar la mejor solución. En los métodos heurísticos

no se asegura hallar la solución óptima global; en su lugar, se busca una solución
“suficientemente buena” o aceptable.

• Eficiencia: velocidad y uso razonable de recursos. Prioriza obtener una solución en

un tiempo y con recursos computacionales razonables.

Los métodos heurísticos son indispensables para abordar problemas de optimización

combinatoria clasificados como NP-difíciles (NP-hard), como el Problema del Viajante
(TSP). Para instancias de gran tamaño de estos problemas, los algoritmos exactos que
garantizan la optimalidad global requieren un tiempo de ejecución que crece
exponencialmente, haciéndolos impracticables. La heurística, por tanto, sacrifica la
garantía de optimalidad a cambio de viabilidad práctica.

Fuerza Bruta es exacto, por ejemplo.

Un método heurístico puede ser reducir el espacio de estrategia al algoritmo.

 Característica Algoritmos Exactos Algoritmos Heuristicos

Encontrar la solución Encontrar una solución

Objetivo Principal
óptima (la mejor posible). buena (cercana al óptimo).

Sí la garantiza, al probar No garantiza la solución

Garantía
todas las opciones. óptima.

Reglas Empíricas o "Atajos"

Estrategia Búsqueda Exhaustiva.
para guiar la búsqueda.

Espacio de Explora TODO el conjunto Explora solo una fracción

Búsqueda de posibles soluciones. prometedora del espacio.

Rápido. Se utiliza para

Lento. El tiempo de
resolver problemas
Velocidad/Eficiencia cálculo es a menudo
complejos de manera
exponencial o factorial.
eficiente.

Problemas pequeños o Problemas grandes (NP-

Uso Común como base de hard) como el TSP con
comparación. muchas variables.

Constructivo: EXISTE Y TE DIGO CÓMO ENCONTRARLO.

No constructivo: EXISTE, PERO NO TE DIGO CÓMO

El teorema de ZERMELO
Dado cualquier conjunto de conjuntos no vacíos, existe una función que elije un elemento
de cada uno de ellos.

Es no constructivo porque el teorema afirma que existe esa función de elección, pero no te
dice como construirla.

Ejemplo:
IMAGINÁ UN CONJUNTO INFINITO DE CAJAS,
Y SABÉS QUE EN CADA CAJA HAY AL MENOS UNA BOLA.
EL AXIOMA DE ELECCIÓN TE DICE:

“PODÉS ELEGIR UNA BOLA DE CADA CAJA.”

PERO... NO TE DICE CÓMO HACERLO,

NI TE DA UNA FUNCIÓN O ALGORORITMO PARA SELECCIONARLAS UNA POR UNA.
ESA ES LA ESENCIA DE QUE SEA NO CONSTRUCTIVO.

2-OPT
Método local heurístico.

Dos aristas no adyacentes las desconecta y las vuelve a conectar. Comparan el camino
nuevo con el viejo, si es más corto abandonan el camino nuevo. Compara aristas
adyacentes con la que estoy viendo.

Ejemplo:

IMAGINÁ TODAS LAS POSIBLES RUTAS (PERMUTACIONES DE CIUDADES) COMO UN

TERRENO LLENO DE:

• MONTAÑAS = RUTAS MALAS (COSTE ALTO)

 • VALLES = RUTAS BUENAS (COSTE BAJO)

EL MÉTODO EXACTO

• RECORRE TODO EL TERRENO SISTEMÁTICAMENTE HASTA ENCONTRAR EL VALLE

MÁS PROFUNDO (ÓPTIMO GLOBAL).

• EJEMPLO: EL ALGORITMO HELD-KARP (PROGRAMACIÓN DINÁMICA) O UNA

BÚSQUEDA COMPLETA.

• PERO EL PROBLEMA ES QUE EL TERRENO CRECE EXPLOSIVAMENTE: EL NÚMERO

DE POSIBLES RUTAS = 𝑛!/2.

ES DECIR: IMPOSIBLE DE CALCULAR PARA MUCHAS.

EL MÉTODO HEURÍSTICO (VECINO + 2-OPT)

• ACTÚA COMO UN “EXCURSIONISTA PRAGMÁTICO”:

VA AL PUNTO MÁS CERCANO, ARMA UNA RUTA RAZONABLE,
Y LUEGO HACE PEQUEÑOS AJUSTES (LOS “INTERCAMBIOS 2-OPT”)
PARA INTENTAR “BAJAR” A UN VALLE MÁS PROFUNDO (MEJORAR LA SOLUCIÓN).

LLEGA RÁPIDO A UN VALLE CERCANO (ÓPTIMO LOCAL),

PERO NO HAY GARANTÍA DE QUE SEA EL MÁS PROFUNDO (ÓPTIMO GLOBAL).

“EL EXACTO BUSCA EL MEJOR VALLE DEL MUNDO, PERO TARDA UNA ETERNIDAD.
EL HEURÍSTICO BAJA RÁPIDO A UN VALLE CERCANO Y SE CONFORMA CON ESO.”

Optimización
Todo problema de optimización puede ser encapsulado en un triplete fundamental:
P = (S, f, Ω)

El Triplete de la Optimización

• S: Espacio de búsqueda→Universo de todas las soluciones posibles.

• f: Función objetivo→Métrica de calidad a optimizar (minimizar/maximizar).

• Ω: Restricciones→Reglas que definen una solución “factible”.

Clasificación de problemas de optimización:

• Determinista vs. Estocástica: ¿Hay incertidumbre en los datos?

• Unimodal vs. Multimodal: ¿Hay un solo óptimo o múltiples?

• Con vs. Sin restricciones: ¿Existen reglas que limiten las soluciones?

• Mono-objetivo vs. Multi-objetivo: ¿Se optimiza un criterio o varios en conflicto?

Algoritmo evolutivo
Método heurístico.

Imaginamos alguien que quiere mejorar el cultivo de tomate, tengo cosecha veo algunos
que son mejores y eso reproduzco. Tengo cierto criterio de mejora e incentivo esa mejora.

Se usa para que computadoras mejoren su propio código, por ejemplo.

Función objetivo, no convexa, tenemos la población que es de individuos al azar este es mi

área de búsqueda cada uno es una posible solución. Puede estar representado por
binarios enteros etc (serian cromosomas).

A diferencia de los métodos tradicionales que trabajan con un solo punto de búsqueda (y
pueden quedarse atrapados en óptimos locales), los algoritmos genéticos operan sobre
una población de soluciones candidatas (cromosomas). esto les permite explorar
múltiples regiones del espacio de búsqueda simultáneamente, aumentando la
probabilidad de encontrar el óptimo global, incluso en problemas no convexos,
multimodales y no diferenciables.

La analogía biológica es directa:

• Los individuos del entorno corresponden a soluciones candidatas.

• La selección natural equivale a la selección por aptitud, donde los más aptos son
elegidos.
• La reproducción y mutación corresponden a los operadores genéticos (crossover y
mutación).
Primero codifico:

Genotipo→ genes.

Fenotipo→ expresión física de ese gen.

Fitness→ fenotipo al cuadrado.

Una mala codificación puede limitar la capacidad del algoritmo para explorar el espacio de
soluciones, afectando su convergencia.

Selección:

Encontrar la solución óptima.

Ruleta imaginamos que cada uno tiene una solución y la paso a decimales. Tenemos
ruleta donde cada porción es el ancho de fitness. Mas fitness más probabilidad que salga
esa parte de la ruleta. Si no tengo variedad en mi espacio de búsqueda converge a un
óptimo que no sería el mejor, acá cada tanda busca variedad, claramente favorece al de
más fitness, pero sigue habiendo probabilidad de que salgan lo de menos. El que se
selecciona por ejemplo podrá ser padre para cruzarse con otro cromosoma y dar una
solución.

El espacio de búsqueda es fundamental.

Torneo por otro lado bolillero selección k y agarro el mejor, así sucesivamente. Reduzco la
variabilidad ya que no agarro toda la población, así doy diversidad.

Cruce:

Creo hijo a partir de material genético de dos padres.

En cruce de un punto selecciono un punto de corte en cada padre y un hijo se agarra la

(cabeza1 ; cola 2) y el otro (cola1 ; cabeza2).

En algoritmos genéticos, el cruce aritmético es un tipo de cruce que se usa cuando los
genes son valores numéricos reales (no binarios) y se busca combinar los valores de los
padres de forma ponderada para generar hijos intermedios.

Definición formal

Sean dos padres 𝑃1y 𝑃2 , representados como vectores de genes:

𝑃1 = (𝑥1 , 𝑥2 , . . . , 𝑥𝑛 )
 𝑃2 = (𝑦1 , 𝑦2 , . . . , 𝑦𝑛 )

Entonces, el cruce aritmético genera dos hijos 𝐻1 y 𝐻2 como:

𝐻1 = 𝛼𝑃1 + (1 − 𝛼)𝑃2
𝐻2 = (1 − 𝛼)𝑃1 + 𝛼𝑃2

donde 𝛼 ∈ [0,1]es un coeficiente aleatorio (o fijo) que determina el “peso” de cada padre
en el hijo.

Mutación:

Cambio al azar, la mayoría no mejora.

Actúa como un mecanismo de variación aleatoria que garantiza la persistencia de

diversidad genética en la población

Esta operación evita que la población se vuelva demasiado homogénea, un fenómeno

conocido como convergencia prematura, que puede conducir a óptimos locales sin
alcanzar la mejor solución global.
Parámetros clave:

Tamaño de población mayor amplía la diversidad genética y aumenta la posibilidad de

escapar de óptimos locales, aunque a costa de un mayor costo computacional. En
cambio, una población pequeña acelera la convergencia pero puede conducir al
estancamiento. La tasa de cruce regula cuánta información se combina entre individuos,
mientras que la tasa de mutación introduce variabilidad que evita la homogeneización
prematura.

Elitismo: Los mejores individuos de una generación se copian directamente a la siguiente

sin modificarse. La elite la sacamos antes de hacer el método de selección.

Resumen del proceso:

Formas de codificar una solución:

Espacio de búsqueda: es el conjunto n-dimensional que contiene todas las soluciones

posibles de un problema, donde cada punto representa una solución candidata. Al asignar
un valor de aptitud (fitness) a cada punto, se genera un paisaje de aptitud (fitness
landscape), en el cual:

• las cimas indican soluciones de alta calidad (óptimos),

• los valles representan soluciones de baja calidad,

• el pico más alto corresponde al óptimo global,

• y los picos menores son óptimos locales.

Diversidad:

Cuanto más heterogénea sea la población, mayor será la probabilidad de descubrir

regiones inexploradas del espacio de soluciones. Una pérdida temprana de diversidad
conduce a la convergencia prematura, en la cual el algoritmo se estabiliza en soluciones
subóptimas. Por el contrario, mantener un nivel adecuado de diversidad asegura un
balance entre la explotación de las mejores soluciones y la exploración de nuevas
combinaciones. Existen diversas estrategias para preservar la diversidad: incrementar la
tasa de mutación, aplicar reinicios parciales de población.

El algoritmo genético es una heurística de búsqueda y optimización.

El AG utiliza la incertidumbre como herramienta de descubrimiento. Esta propiedad le

otorga robustez frente a entornos no lineales, discontinuos o con múltiples óptimos
locales, en los cuales los métodos analíticos tradicionales fracasan.

Fortalezas:

• Robustez: Funciona bien para muchos problemas.

 • Búsqueda global: Menos susceptible a óptimos locales.
• Paralelismo inherente: Población se puede evaluar en paralelo.

Debilidades:

• Costo computacional: Lento para poblaciones grandes.

• No garantizan optimalidad: Son estocásticos, no hay garantía de encontrar el
óptimo.

Proceso estocástico: variables aleatorias indexadas en el tiempo.

Hay muchos, el genético depende del instante anterior y el anterior del anterior → Seria de
Márkov de orden 1, que este refleja un proceso estocástico.

Modelo de Markov
Los algoritmos genéticos pueden modelarse como cadenas de Markov de primer orden,
donde cada estado representa una población de soluciones y la probabilidad de transición
depende únicamente de la población actual.
Sea 𝑃𝑡 la población en la generación 𝑡.
El algoritmo genético define una función de transición estocástica 𝑇 tal que:

Esto implica que el proceso evolutivo del algoritmo es finito e irreversible, y bajo ciertas
condiciones (como diversidad suficiente o probabilidades de mutación no nulas) se puede
demostrar que el algoritmo converge en probabilidad hacia un conjunto de soluciones
óptimas, aunque no necesariamente al óptimo global.

Para analizar esta convergencia, se utiliza el Teorema del Esquema de Holland,

representado en las siguientes imágenes:
En términos simples el teorema muestra cómo los esquemas con alta aptitud, cortos y con
pocos bits definidos tienden a sobrevivir y multiplicarse en el proceso evolutivo —esto se
conoce como la “supervivencia del más apto y compacto”.

Por lo tanto, el Teorema del Esquema de Holland complementa el modelo de Markov al

demostrar que, aunque el algoritmo genético es un proceso estocástico, tiende a
conservar y propagar estructuras favorables (esquemas).
Esto asegura que el algoritmo mantenga una búsqueda dirigida hacia óptimos,
garantizando al menos un óptimo local.

Definicion de esquema: Plantilla de genes que especifica valores fijos en ciertas

posiciones y * (comodines) en otras.
Esa característica que hace a un cromosoma que sea mejor se puede demostrar y se va
manteniendo, así se puede lograr al optimo.

Algoritmo genético aplicado al problema del viajante

El Problema del Viajante de Comercio (TSP) es un problema clásico NP-hard de
optimización combinatoria. Consiste en encontrar la ruta más corta que recorra un
conjunto de ciudades exactamente una vez y regrese a la ciudad de origen.

Dado que no se conoce un algoritmo exacto que lo resuelva eficientemente para un gran
número de ciudades (debido a su complejidad exponencial), los algoritmos genéticos
(AG) se presentan como una poderosa alternativa heurística para encontrar soluciones
aproximadas de alta calidad.

Justificación de la Aplicabilidad de AG al TSP

Los Algoritmos Genéticos son muy adecuados para resolver el TSP por las siguientes
razones clave:

1. Estructura del problema adecuada para codificación genética:

• Una solución del TSP se representa naturalmente como una permutación de

nodos (ciudades), lo que encaja perfectamente en el esquema de un
individuo en un AG.

• Genotipo: La permutación de nodos.

• Fenotipo: La ruta resultante.

• Fitness: La distancia total del recorrido (a minimizar).

2. Los operadores genéticos pueden preservar características útiles:

 • Operadores como el Crossover de orden (OX), Crossover de ciclo
(CX) y Mutación (por inserción, intercambio o inversión) están diseñados
para preservar subrutas eficientes, mejorar gradualmente la calidad de las
soluciones y evitar soluciones inválidas (como rutas con ciudades repetidas
o faltantes).

3. El espacio de búsqueda es inmenso y no estructurado:

• Con ciudades, el número de rutas posibles es , lo que hace la búsqueda

exhaustiva inviable.

• Los AG, como técnicas de búsqueda estocástica guiadas por fitness, son
capaces de explorar eficazmente grandes espacios de búsqueda sin requerir
derivadas ni continuidad.

4. Robustez ante óptimos locales:

• Al incorporar variación genética (mutación) y diversidad poblacional, los AG

tienen mayor capacidad de escapar de óptimos locales en comparación con
métodos deterministas que podrían estancarse fácilmente.

5. Adaptabilidad y flexibilidad:

• Los AG pueden adaptarse fácilmente a variantes del TSP, como el TSP

asimétrico, TSP con ventanas de tiempo, Multi-TSP o TSP con múltiples
criterios (multiobjetivo: distancia, riesgo, costo).

• Esto convierte al AG en una herramienta muy versátil para problemas reales

de ruteo y logística.

TEMAS AVANZADOS Y APLICACIONES PRÁCTICAS

Optimización multiobjetivo: encuentra un conjunto de soluciones de compromiso (frente
de Pareto) para objetivos en conflicto.

Manejo de restricciones: usa funciones de penalización para guiar la búsqueda hacia

soluciones factibles.

Algoritmos híbridos: combina la exploración global del algoritmo genético con la

explotación local de otros métodos (ej. hill climbing).

Algoritmos meméticos: una forma de algoritmo híbrido donde el aprendizaje individual

(búsqueda local) se incorpora al proceso. el término memético viene de meme,
relacionado con la selección de ideas en vez de genes. Puede verse como un algoritmo
genético en el que cada paso se optimiza localmente.

La barrera de la escalabilidad: complejidad

Complejidad computacional: ¿cuánto tiempo y memoria se necesitan para entrenar el
modelo?

Complejidad muestral: ¿cuántos datos se necesitan para que el modelo generalice bien?

Laberinto:
Difícil de verificar y fácil de solucionar→ Problema npHard

El desafío consiste en que un agente encuentre una ruta óptima desde un punto de inicio
hasta una meta, sorteando obstáculos y, a menudo, minimizando la longitud del camino o
el tiempo empleado. Este tipo de problema se vuelve particularmente complejo en
entornos de gran escala, con múltiples caminos sin salida por ejemplo.

Los algoritmos genéticos ofrecen un enfoque robusto y adaptable para abordar estos
desafíos. Permiten explorar un vasto espacio de posibles soluciones (caminos) de manera
paralela y heurística.

El entorno del laberinto se modela comúnmente como una matriz o cuadrícula

bidimensional.

• 0 (o un valor similar): Representa una celda transitable, es decir, un pasillo o

camino por donde el agente puede moverse.
• 1 (o un valor diferente): Representa un obstáculo, como una pared, que el agente no
puede atravesar.

Dentro de esta matriz, se definen claramente una posición de inicio (start) y una posición
objetivo (end). La navegación válida se restringe, por lo general, a movimientos en las
cuatro direcciones cardinales: arriba, abajo, izquierda y derecha, desde una celda
transitable a otra adyacente y también transitable.

En el contexto de los AG, cada individuo representa una solución candidata al problema.
Para la navegación en laberintos, un individuo es un camino potencial desde el inicio hasta
(idealmente) el final.
Una codificación efectiva y natural para este problema es representar al individuo como
una secuencia ordenada de posiciones (coordenadas (fila, columna)) en el laberinto. Por
ejemplo:

Individuo A: [(0,0), (0,1), (1,1), (1,2), (2,2)] // Un camino potencial

La función de fitness es el componente crítico que guía el proceso evolutivo. Cuantifica la

"calidad" de cada individuo (camino) en la población. Una función de fitness bien diseñada
es crucial para dirigir la búsqueda hacia soluciones deseables.

Para el problema de laberintos, una función de fitness robusta podría incorporar varios
criterios, ponderados adecuadamente:

• Alcance del Objetivo: Se otorga una recompensa significativamente alta (o una

penalización muy baja) a los individuos que logran alcanzar la celda objetivo (end).
Este es, usualmente, el componente más importante.
• Longitud del Camino: Se penaliza la longitud excesiva del camino. Caminos más
cortos, si alcanzan el objetivo, son preferibles. Esto se puede implementar como
una penalización proporcional al número de pasos.
• Penalización por Bucles o Redundancia: Visitar repetidamente las mismas celdas o
segmentos del laberinto es ineficiente. Se pueden introducir penalizaciones si un
individuo contiene bucles o revisita celdas innecesariamente.
• Distancia al Objetivo (si no se alcanza): Para los individuos que no llegan al final, se
puede usar una heurística como la distancia de Manhattan (Tengo dos distancias
(3;4) y (5;5) → mi distancia manhattan 5-3 + 5-4) o Euclidiana desde la última celda
alcanzada por el individuo hasta la celda objetivo. Una menor distancia resulta en
una menor penalización (o mayor fitness relativo).
• Validez del Camino: Implícitamente, los caminos deben ser válidos (o no atravesar
paredes). Si se permiten caminos inválidos durante la evolución (para luego
repararlos), deben ser fuertemente penalizados.

Ya tenemos todo el laberinto

Primero cada nodo estará conectado con otro, por ende, de la entrada a la salida puedo
llegar, en conclusión, mi grilla es conexa. Si no lo fuera talvez no tengo un camino optimo
hacia la salida.

El camino optimo en un laberinto tendrá forma de árbol (no tendré bucles y es conexo). La
condición necesaria es que sea un árbol.
Subgrafo, porción de grafo, que es tomar todo el laberinto y este sería su solución optimo
es acíclico y conexo por ende árbol.

Dado nuestro espacio de búsqueda tenemos múltiples caminos.

Topología (estudia las formas fijándose sólo en sus propiedades esenciales)

Königsberg dio origen a Grafos y también dio topología (Si tengo una esfera y un cubo, son
topológicamente equivalentes, no tienen agujeros por ende un cubo lo puedo transformar
en una esfera. Me sirve para clasificar objetos, armar grafos, etc).

Solidos platónicos icosaedros son topológicamente equivalentes a una esfera.

Tengo cubo de 3D, Está formado por polígonos (cada polígono es un cuadrado)

Lo veo en función de sus vértices, aristas y caras.

Vértices: (a, b, c) cada uno podrá estar como 1-0 por ende tendré 2^3 →8

Aristas: Distancia haming de 1. Cada nodo tendrá 3 artistas. Por ende, si tengo 8 nodos
→24 pero por teorema de apretón de manos serán 24/2 = 12

Caras: 24/8 →6

Ahora según Euler tenemos:

X (constante de Euler para cuadrado) =V-A+C =2

Lo que realmente revela es que, por más que un cuerpo cambie de tamaño, forma o
proporciones, la conectividad entre sus partes —el modo en que las aristas enlazan
vértices y delimitan caras— permanece invariable mientras no haya rupturas topológicas.

Globo terráqueo, polo norte y polo sur → tendríamos 2 vértices, 1 arista y 1 caras

X=2

Ahora Corto como gajo → Tendre 2 caras, 2 aristas y 2 vertices

X=2
Al ser el mismo valor de X de uno se puede transformar a otro, por ende, son equivalentes
topológicos.

Homeomorfo (función biyectiva, un punto del cubo pertenece a uno de las esferas)

Todo poliedro convexo x=2

Todo esto que tiene que ver con el laberinto

X= (V-A+C)-2g (por el número de agujero)

Un camino

Para grafo se reduce a X=V-A

En un árbol, por ejemplo

X= 2-1=1

X=3-2=1
En estos ejemplos hay una relación la cantidad aristas = V-1 por ende X=1

¿Qué es (realmente) un espacio topológico?

Un espacio topológico es un par (X, t), donde X es un conjunto de puntos y t es una

colección de subconjuntos de X, llamados conjuntos abiertos, que deben satisfacer tres
axiomas fundamentales:

• Axioma 1: El conjunto vacío (∅) y el total (X) están en t.

• Axioma 2: La unión (finita o infinita) de abiertos está en t.
• Axioma 3: La intersección FINITA de abiertos está en 099t.

El primer problema era como recorrer los distintos puentes sin repetir, aquí surge la
respuesta de Euler el cual representa a lada espacio de tierra como un nodo y de puente
como arista.

Los puentes de Königsberg dieron origen a dos grandes áreas: Los grafos y la topología.

Dado esos nodos la respuesta fue que si el número de nodos es par contamos con un ciclo
euleriano. En caso de tener impares, deben ser dos una entrada y una salida y estaríamos
hablando de un camino. implícitamente. Detrás de esto estaba el teorema de del apretón
de manos, es decir que la suma de los grados tiene que ser 2 veces el número de aristas (si
o si la suma de los grados debe dar un numero par).

Este era un problema fácil de resolver, al que se denomina P →uno cuenta los nodos ve
qué grados tiene ya está condición necesaria y suficiente para saber si es un ciclo o un
camino.

A partir de esto, n problema más difícil en el sentido de cálculo no es centrarnos en las

aristas, sino en los nodos. Surge la idea de ciclo o camino hamiltoniano y es un problema
más difícil ya que no hay teorema necesario y suficiente, solo suficiente.

Es un problema np, en el que me dan la respuesta y lo puedo verificar rápidamente pero

encontrarla es lo difícil, es un problema permutatorio. Si agregamos el problema del
viajante, el cual trata minimizar distancias es npHard, al menos tan difícil de solucionar
que los np completos porque estamos tratando con un problema de optimización
combinatoria.
Para solucionarlos los exactos no son muy útiles, se usan heurísticos, como por ejemplo el
algoritmo y programación genética

Diferencias entre algoritmo genético y programación genética

En los AG tenemos estructuras fijas que puede ser en números enteros, binarios o reales
que representarían a los cromosomas (soluciones candidatas).

En cambio en PG tenemos de longitud variable, por ende son mucho más complejos.

Programación genética
Su objetivo es evolucionar automáticamente programas ( en vez de estructuras fijas) que
resuelvan problemas complejos sin intervención humana directa en la codificación de la
solución.

Por ejemplo un programa Python tiene una sintaxis con distintas longitudes, las soluciones
en estos casos no serán de longitud fijas, sino que dependerán del problema que estamos
solucionando.

La estructura de solución varia.

La idea es transformar el proceso de programación en una a búsqueda evolutiva, donde

estos se generan y evalúan y refinan iterativamente hasta aproximarse a una solución.
Ese ejemplo muestra →

Tengo serie de datos e intentara de descubrir la función subyacente, el problema es que

hay múltiples funciones que pueden ser.

En el evolutivo tenemos ya la función y queremos saber el mínimo y máximo, acá no

tenemos nada, la estructura no puede ser fija por los distintos tipos de posibles funciones.

Al ser variada una estructura muy usada son los árboles que al fin y al cabo son grafos. En
este caso un árbol de sintaxis abstracta.

En este caso los operadores son el divisor y el mas y se va subdividiendo.

En nodos terminales tenemos variables y constantes y en intermedios funciones y

operadores.
Se puede ver como el flujo es prácticamente igual entre AG y PG, la gran diferencia es el
espacio de búsqueda.

Cruce en este caso combinamos partes de árboles.

Mutación sería una pequeña modificación dentro de un árbol.

Elitismo seria los mejores árboles.

Bloat → El crecimiento descontrolado está acompañado de una no mejora de fitness.
Metáfora para objetivo principal:

Tengo edificio y AG quiero encontrar dado la instalación eléctrica que lámparas conviene
utilizar, en PG se refiere a cual es la mejor instalación eléctrica.

Si tengo un problema de parámetros, pocas features, las funciones son convexas.

Si tengo múltiples óptimos locales es no convexas.

Si no tengo derivadas AG (el tsp está estructurado por ejemplo).

Si el problema no esta bien estructura es PG (un lenguaje de programación no está

estructurado).

Ejemplo hipercubo

Digamos que tenemos los valores entre

(0;15)→ En binario 2^4 →(x0, x1, x2, x3)

Con esto tengo distintas combinaciones.

(0,0,0,0) → Nodo 0

(0,1,0,0) → Nodo 1

Faltarían las aristas, para eso hay que definir una métrica (distancia de un nodo a otro).

Para esto se usa la distancia de haming que es la que cumple con los requisitos necesarios
(por ejemplo dist>=0, verifica desigualdad triangular, etc).

(0,0,0,0)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)
Cada nodo en este caso se comunica con 3 nodos, ya que es con todos con los que tenga
una distancia de haming de 1.

Por ende si tengo 16 nodos y cada uno se comunica con 3 según el teorema de apretón de
16𝑋3
manos → = 24 aristas
2

Cada nodo es una posible solución

(0,0,0,0) y tengo (0,1,0,0) → esto implica un desplazamiento cambiar un 0 por un 1 y en AG

se lo conoce como mutación.

Combinación de nodos será cruzamiento.

En el caso este del hipercubo la figura es regular, esto lleva a poder trabajar con algoritmos
genéticos debido a que son estructurados.

La fórmula será 2^n por eso estamos hablando de un espacio de búsqueda muy complejo
(NP)
Espacio de Búsqueda
AG: Fijo

PG: Explosivo

Es el conjunto de todos los programas posibles que puede generarse por funciones (cos,
sen,e) y terminales (variables x, y o número).

Tengo árbol, llego al final, reemplazo por números, va a la raíz y hago calculo.

La búsqueda modifica la estructura de los árboles.

El árbol es jerárquico, combinatorio y potencialmente infinito, no finito y lineal como AG.

En el genético como vimos antes con el hipercubo, el espacio de búsqueda era N^L → 2^4.

F: Programa cualquiera de computación.

(N(d-1) ^K): Profundidad del árbol donde k es el número de argumentos (sen(x) 1 arg), d es
la profundidad del árbol. Esto es peor que el carácter exponencial del AG, se crece mucho
más rápido y el crecimiento depende del numero de capas, cuanto mas mas complejo y
exponencial se vuelve el espacio de búsqueda.

Es muy difícil encontrar el programa optimo.

Espacio se divide en Funciones y terminales. También tenemos parámetros como el de
anidad que hace referencia a las variables por función, por ejemplo Sen(xy) tiene anidad 2.

A su vez definimos la profundidad del árbol, cuanto mayor es, más complejo.

En PG tenemos infinitos programas posibles, va haber algunos que no sean ejecutables

por error sintáctico y otros que sí.

Dentro de los ejecutables hay validos (dan un resultado) y dentro de estos están los de
comportamiento razonable (se acerca la solución pero no es muy útil), por ultimo dentro
de eso están los útiles (logran solucionar el problema).

No existe método exacto para encontrar el programa optimo.

AG longitud fija, espacio de búsqueda muy estructurado puede ser representado por una
figura geométrica como el hipercubo (N dimensiones, cada punto una solución y las
aristas me llevan de una a otra, lo que hace el AG es recorrer las distintas aristas, recorro
todas las soluciones por eso es ergódico, un AG se puede representar como un proceso
marcobiano de orden 1 donde el estado de ahora depende del presente y no del pasado)

El árbol por ejemplo tiene una estructura fractal donde cada nodo se divide en mas
pequeños y así sucesivamente.

Ergódico: Irreductible (recorre todos los espacios posibles) y aperiódico (no se queda en
un ciclo una y otra vez). Se pueden estudiar partes del pasado para conocer el futuro.

No Ergódico: No recorre todo el espacio de solución y puede tener ciclos donde se queda
fijo.

Problema en si mimo no bien definido PG.

Métodos heurísticos cuando no tenemos ni derivadas.

En la base de datos los programas no se eliminan, quedan en el stock genético para
conservar diversidad.

Generan prompts, estos generan códigos, estos se evalúan y el que mejor resuelve el
problema es el ganador.

Darwin Gödel Machine: Muestra una forma distinta de cómo van modificándose los
códigos.

Una máquina de Gödel es para generar pruebas lógicas en forma evolutiva. Genera
códigos evolutivos. Acá se reemplazan los teoremas matemáticos por cruzamiento y
mutación para generar códigos.

Google lo que hace es generar un programa para solucionar distintos problemas.

La nasa, en vez de aplicar llms aplicó estrictamente programación genética, era para
solucionar conseguir una antena mucho más eficiente.

Acá es un código para mejorar el propio código. Un tipo de agente computacional capaz de
reescribir su propio código, creando nuevas versiones funcionales.

Lo que emergen no es una solución perfecta, sino un archivo evolutivo.

Un sistema IA que evoluciona y se mejora a si mismo de forma abierta y continua.

La clave es no reducir la diversidad, si se reduce va a haber soluciones que no se pueden

explorar.

Quiero explorar todas las soluciones posibles.

El agente recibe la instrucción de mejorarse a sí mismo. El objetivo del programa es

mejorarse su propio funcionamiento sí.
esto genera nuevo agente empírico y hay una relación empírica para tratar de solucionarlo,
que es la tercera parte.
El alphaEvolve usa LLM para hacer las mutaciones, transicionar, acelerar nuevos códigos
que después se evalúan.
Si tenemos un espacio de búsqueda que no podemos aplicar problemas exactos,
necesitamos heurísticas. El gradiente desciende, por ejemplo, no sirve porque no son
funciones continuas.

Algoritmos genéticos y lo establecí como un espacio de búsqueda fijo, puede ser

representado mediante un hiper cubo, es decir, un cubo de n dimensiones. Cada punto es
una solución y las aristas me indican mutaciones, cruzamientos.

Cuando pasamos a programas no estructurados no se puede aplicar AG, sino PG.

El espacio crece exponencialmente y relacionado con esto está el alphaEvolve y Darwin

Gödel Machine.

¿Sumar X más X es lo mismo que hacer 2 por X, sí o no?

Son diferente sintácticamente porque su estructura es distinta, pero el resultado será

igual.

Por lo tanto, hay dos formas de medir como se van desempeñando los árboles, una es la
sintaxis (ves la forma del árbol) y otra la semántica (ver el resultado).

Sintácticamente, son distintos semánticamente, son iguales.

Lo mejor uno diría que es evaluarlo semánticamente, donde lo que me interesa es el

resultado, pero muchas veces el costo computacional es muy bajo. Por eso, para estudiar
estos árboles se utiliza muchas veces distancias sintácticas donde la idea a distancia
sintáctica es darme la diferencia entre un árbol y otro.

Autómata celular
Mecanismo down top

En vez de digitar todo desde arriba, se establecen unas pequeñas reglas y a partir de estas
se generan estructuras enormemente complejas.
Maquina Touring completa: Nuestras computadoras.
Lo que ve el autómata celular, que se denomina regla de Moore son los vecinos.
El autómata del centro y el de arriba está vivo y los demás están muertos ( no hay nodo), en
este caso el autómata se transforma en muerto.

Este por ejemplo sobrevive.

Uno que tenga 3 vivos se reproduce.

Si tiene menos de 2 vecinos vivos muere por soledad y tiene 2 sobrevive, si tiene 3 se
reproduce y si tiene 4 muere por sobreproducción.

El vecindario seria esas 3 celdas que rodean al autómata ( Arriba, costado, abajo)

Componenetes clave en el juego de la vida

¿qué es lo que hace un un lenguaje que sea touring completo? que pueda ejecutar
cualquier programa.

Para una máquina de Turing que es el modelo de computación se necesita un mecanismo

de memoria y tablas de verdad.
Regla 30 y 110?
 PREGUNTAS FINAL:
PREGUNTA 1: ¿QUÉ ES SHARDING Y POR QUÉ SE USA EN BASES DE DATOS
DISTRIBUIDAS?
RESPUESTA: EL SHARDING ES UNA TÉCNICA QUE SE USA PARA DIVIDIR UNA BASE DE
DATOS GRANDE EN PARTES MÁS PEQUEÑAS, LLAMADAS SHARDS, QUE SE DISTRIBUYEN
EN EL SISTEMA, PERO TRABAJAN DE MANERA INDEPENDIENTE. SE USA EN BASES DE
DATOS DISTRIBUIDAS PORQUE PERMITE ESCALAR HORIZONTALMENTE Y MANEJAR
MAYOR VOLUMEN DE DATOS.

PREGUNTA 2: ¿CÓMO AFECTA EL TEOREMA CAP A BITCOIN Y A LAS REDES SOCIALES?

RESPUESTA: EL TEOREMA CAP ES AQUEL QUE DICE QUE SOLO SE PUEDEN SATISFACER
DOS DE TRES CARACTERÍSTICAS: CONSISTENCIA, DISPONIBILIDAD Y TOLERANCIA A
PARTICIONES. LOS BITCOINS Y LAS REDES SOCIALES PRIORIZAN PARTICIONES Y
DISPONIBILIDAD, SACRIFICANDO LA CONSISTENCIA.

PREGUNTA 3: ¿CUÁLES SON LAS PRINCIPALES CARACTERÍSTICAS DE BIG DATA?

RESPUESTA: LAS TRES PRINCIPALES CARACTERÍSTICAS DE BIG DATA SON VOLUMEN
(GRAN CANTIDAD DE DATOS), VELOCIDAD (SE GENERAN CONSTANTEMENTE) Y
VARIEDAD (DIFERENTES FORMATOS Y TIPOS DE DATOS).

PREGUNTA 4: ¿QUÉ ESTABLECE EL TEOREMA CAP EN BASES DE DATOS DISTRIBUIDAS?

RESPUESTA: EL TEOREMA CAP ESTABLECE QUE SOLO SE PUEDE GARANTIZAR DOS DE
TRES CARACTERÍSTICAS: CONSISTENCIA, DISPONIBILIDAD Y TOLERANCIA A
PARTICIONES. EN BASES DE DATOS DISTRIBUIDAS, HAY QUE ELEGIR CUÁLES DOS SE VAN
A PRIORIZAR.

PREGUNTA 5: ¿CUÁL ES LA DIFERENCIA ENTRE LOS SISTEMAS DE RECOMENDACIÓN

BASADOS EN FILTRADO COLABORATIVO Y EN CONTENIDO?
RESPUESTA: EL FILTRADO COLABORATIVO RECOMIENDA SEGÚN LOS GUSTOS DE OTROS
USUARIOS SIMILARES. POR OTRO LADO, EL FILTRADO EN CONTENIDO USA LAS
CARACTERÍSTICAS DEL CONTENIDO PARA HACER LAS RECOMENDACIONES.

PREGUNTA 6: ¿QUÉ REPRESENTA EL TEOREMA DEL APRETÓN DE MANOS?

RESPUESTA: ESTE TEOREMA DICE QUE EN CUALQUIER GRAFO NO DIRIGIDO, LA SUMA
DE LOS GRADOS DE TODOS LOS VÉRTICES ES IGUAL AL DOBLE DEL NÚMERO DE
ARISTAS.

PREGUNTA 7: ¿QUÉ ES EL NAVEGANTE ALEATORIO EN PAGERANK?

RESPUESTA: ES UN MODELO QUE SIMULA UN USUARIO QUE NAVEGA EN LA WEB
HACIENDO CLICKS AL AZAR. ESTO PERMITE CALCULAR LA IMPORTANCIA DE UNA
PÁGINA.

PREGUNTA 8: ¿QUÉ ES UN GRAFO CUBO (HYPERCUBE GRAPH) Y CÓMO SE CONSTRUYE?

RESPUESTA: UN GRAFO CUBO (HIPERCUBO) ES UNA ESTRUCTURA DONDE LOS
VÉRTICES REPRESENTAN TODAS LAS CADENAS BINARIAS DE LONGITUD N, Y HAY UNA
ARISTA ENTRE DOS VÉRTICES SI SUS CADENAS BINARIAS DIFIEREN EN UN SOLO BIT.

PREGUNTA 9: ¿POR QUÉ LOS BANCOS PRIORIZAN CONSISTENCIA Y DISPONIBILIDAD

(CA) SOBRE TOLERANCIA A PARTICIONES?
RESPUESTA: LOS BANCOS GARANTIZAN LA CONSISTENCIA PORQUE NECESITAN QUE
LOS DATOS SEAN CORRECTOS, Y LA DISPONIBILIDAD PORQUE NECESITAN QUE LOS
SISTEMAS ESTÉN SIEMPRE ACTIVOS. POR EJEMPLO, EN UNA TRANSFERENCIA, EN
TIEMPO REAL LA CUENTA ORIGEN DEBE DEBITARSE Y LA DESTINO ACREDITARSE.

PREGUNTA 10: ¿QUÉ DIFERENCIA HAY ENTRE UN GRAFO DIRIGIDO Y UNO NO DIRIGIDO?
RESPUESTA: EN UN GRAFO DIRIGIDO, LAS ARISTAS TIENEN FLECHAS QUE INDICAN UNA
DIRECCIÓN. EN UN GRAFO NO DIRIGIDO, LAS ARISTAS NO TIENEN FLECHAS.