À quoi servent les graphiques infinis?

Je viens de lire sur Wikipedia allemand qu'un graphe infini est un graphe avec un nombre infini de nœuds ou un nombre infini d'arêtes. Je ne connais que les applications et les algorithmes pour les graphes finis.

À quoi servent les graphiques infinis?

Quelles sont leurs applications? Je ne peux pas imaginer des algorithmes qui fonctionneraient sur des graphiques infinis, car vous ne pouvez pas stocker un graphique infini. Vous ne pouvez donc pas opérer dessus.

De nombreux problèmes de recherche dans l'intelligence artificielle (tels que la recherche dans l'arbre de jeu d'un jeu d'échecs, ou la recherche de solutions à des énigmes comme le Rubik's cube, ou plus généralement la recherche de séquences d'actions à effectuer pour atteindre un objectif souhaité) sont, dans effet, des algorithmes sur des graphes infinis, même si la réponse souhaitée est un chemin fini. Il est certainement possible de réaliser des algorithmes sur de tels graphes, s'ils sont représentés implicitement .

Mais il est également vrai que les mathématiques peuvent être utiles même si ce ne sont pas les mathématiques des problèmes qui peuvent être résolus par des algorithmes. Des graphiques infinis peuvent être utilisés pour modéliser les processus de naissance et de décès (par exemple, comment nos règles d'hérédité des noms et les taux de naissance et de décès des personnes conduisent-ils à des distributions non uniformes des noms de famille entre les différentes cultures humaines?), Pour donner une cadre pour aborder les questions de symétrie mathématique (via les graphes de Cayley , souvent infinis), pour fournir des modèles de raisonnement sur les systèmes de logique (voir graphe Rado et modèle saturé ), etc.

$d$$d$

D'un côté du seuil, le modèle d'Ising est difficile à estimer. De l'autre côté du seuil, le modèle d'Ising est facile à estimer. La complexité du modèle d'Ising le long du seuil d'unicité est actuellement un problème ouvert, mais la conjecture est qu'il est traitable.

Le résultat le plus récent dans cette ligne de travail est par Sly an Sun. Voir leurs références pour d'autres travaux connexes.

Pour vous donner une application particulière où il est utile de penser à des graphiques infinis, considérez un réseau de nœuds distribués, chacun exécutant un algorithme distribué qui se déroule en rondes. À chaque tour, un nœud peut mettre à jour son état en effectuant un calcul local et communiquer en envoyant / recevant des messages vers / depuis ses voisins. La sortie d'un tel algorithme est la sortie combinée de tous les nœuds. Par exemple, chaque nœud pourrait décider localement s'il fait partie d'un ensemble indépendant.

$\Omega(\log^* n)$ et ne peuvent donc pas être calculés sur un réseau infini.

Pour plus de détails sur ce point, cliquez ici .

les graphes universels sont infinis et une généralisation du graphe aléatoire Rado mentionné par DE. des recherches récentes dans ce domaine visent à identifier des graphes universels pour une famille de graphes F: c'est-à-dire un graphe infini appartenant à F qui contient tous les graphes finis de F comme sous-graphes induits.