¿Para qué sirven los gráficos infinitos?

Acabo de leer en la Wikipedia alemana que un gráfico infinito es un gráfico con un número infinito de nodos o un número infinito de bordes. Solo conozco aplicaciones y algoritmos para gráficos finitos.

¿Para qué sirven los gráficos infinitos?

¿Cuáles son las aplicaciones de esos? No puedo imaginar algoritmos que funcionen en gráficos infinitos, ya que no se puede almacenar un gráfico infinito. Entonces no puedes operarlo.

Muchos problemas de búsqueda en inteligencia artificial (como buscar en el árbol de juego de un juego de ajedrez, o buscar soluciones a acertijos como el cubo de Rubik, o buscar en general secuencias de acciones para realizar con el fin de lograr algún objetivo deseado) son, en efecto, algoritmos en gráficos infinitos, a pesar de que la respuesta deseada es un camino finito. Ciertamente es posible realizar algoritmos en tales gráficos, si están representados implícitamente .

Pero también es cierto que las matemáticas pueden ser útiles incluso si no son las matemáticas de los problemas que pueden resolverse mediante algoritmos. Se pueden usar gráficos infinitos para modelar los procesos de nacimiento y muerte (por ejemplo, ¿cómo nuestras reglas para la herencia de nombres y las tasas a las que las personas nacen y mueren, conducen a distribuciones no uniformes de los apellidos entre diferentes culturas humanas?), Para dar un marco para abordar preguntas sobre simetrías matemáticas (a través de gráficos de Cayley , que a menudo son infinitos), para proporcionar modelos para razonar sobre sistemas de lógica (ver gráfico de Rado y modelo saturado ), etc.

$d$$d$

En un lado del umbral, el modelo Ising es difícil de aproximar. En el otro lado del umbral, el modelo Ising es fácil de aproximar. La complejidad del modelo de Ising a lo largo del umbral de unicidad es actualmente un problema abierto, pero la conjetura es que es manejable.

El resultado más reciente en esta línea de trabajo es de Sly an Sun. Ver sus referencias para otros trabajos relacionados.

Para darle una aplicación particular donde es útil pensar en gráficos infinitos, considere una red de nodos distribuidos, cada uno de los cuales ejecuta un algoritmo distribuido que procede en rondas. En cada ronda, un nodo puede actualizar su estado realizando cálculos locales y comunicarse enviando / recibiendo mensajes a / desde sus vecinos. La salida de dicho algoritmo es la salida combinada de todos los nodos. Por ejemplo, cada nodo podría decidir localmente si es parte de un conjunto independiente.

$\Omega(\log^* n)$

Más discusión sobre este punto se puede encontrar aquí .

los gráficos universales son infinitos y una generalización del gráfico aleatorio de Rado mencionado por DE. La investigación reciente en el área está en la dirección de identificar gráficos universales para una familia de gráficos F: es decir, un gráfico infinito perteneciente a F que contiene todos los gráficos finitos en F como subgráficos inducidos.