Wozu sind unendliche Graphen gut?

Ich habe gerade in der deutschen Wikipedia gelesen, dass ein unendlicher Graph ein Graph mit einer unendlichen Anzahl von Knoten oder einer unendlichen Anzahl von Kanten ist. Ich kenne nur Anwendungen und Algorithmen für endliche Graphen.

Wozu sind unendliche Graphen gut?

Was sind Anwendungen davon? Ich kann mir keine Algorithmen vorstellen, die auf unendlichen Graphen funktionieren würden, da Sie keine unendlichen Graphen speichern können. Sie können es also nicht bearbeiten.

Viele Suchprobleme in der künstlichen Intelligenz (wie das Durchsuchen des Spielbaums eines Schachspiels oder das Suchen nach Lösungen für Rätsel wie den Zauberwürfel oder allgemeiner das Suchen nach Abfolgen von Aktionen, die ausgeführt werden müssen, um ein gewünschtes Ziel zu erreichen) Effekt, Algorithmen auf unendlichen Graphen, obwohl die gewünschte Antwort ein endlicher Pfad ist. Es ist sicherlich möglich, Algorithmen für solche Graphen auszuführen, wenn sie dargestellt werden implizit dargestellt werden .

Es ist aber auch wahr, dass Mathematik nützlich sein kann, auch wenn es nicht die Mathematik von Problemen ist, die durch Algorithmen gelöst werden können. Unendliche Graphen können verwendet werden, um Geburts- und Todesvorgänge zu modellieren (z. B. wie führen unsere Regeln für die Vererbung von Namen und die Rate, mit der Menschen geboren werden und sterben, zu einer ungleichmäßigen Verteilung von Familiennamen zwischen verschiedenen menschlichen Kulturen?), Um a Rahmen für die Beantwortung von Fragen zu mathematischen Symmetrien (über Cayley-Graphen , die häufig unendlich sind), um Modelle für die Argumentation über Logiksysteme bereitzustellen (siehe Rado-Graph und gesättigtes Modell ) usw.

Im antiferromagnetischen Bereich des Ising-Modells hängt der Rechenaufwand für die Approximation der Zählung vom Gibbs-Maß über unendlich ab$d$-regelmäßige Bäume. Die Gibbs messen an diesen unendlich$d$-regelmäßige Bäume durchlaufen einen Phasenübergang auf einer Linie, die als Eindeutigkeitsschwelle bezeichnet wird.

Auf einer Seite der Schwelle ist das Ising-Modell schwer zu approximieren. Auf der anderen Seite der Schwelle ist das Ising-Modell leicht zu approximieren. Die Komplexität des Ising-Modells entlang der Eindeutigkeitsschwelle ist derzeit ein offenes Problem, aber die Vermutung ist, dass es handhabbar ist.

Das jüngste Ergebnis dieser Arbeit stammt von Sly an Sun. Siehe ihre Referenzen für andere verwandte Werke.

Stellen Sie sich ein Netzwerk von verteilten Knoten vor, von denen jeder einen verteilten Algorithmus ausführt, der in Runden abläuft, um eine bestimmte Anwendung zu erhalten, bei der es nützlich ist, über unendliche Graphen nachzudenken. In jeder Runde kann ein Knoten seinen Status durch Ausführen einer lokalen Berechnung aktualisieren und durch Senden / Empfangen von Nachrichten an / von seinen Nachbarn kommunizieren. Die Ausgabe eines solchen Algorithmus ist die kombinierte Ausgabe aller Knoten. Beispielsweise könnte jeder Knoten lokal entscheiden, ob er Teil einer unabhängigen Menge ist.

Bestimmte verteilte Computerprobleme können in konstanter Zeit (dh konstanter Anzahl von Runden, bis alle Knoten enden) gelöst werden, unabhängig davon, wie viele Knoten sich im Netzwerk befinden. Insbesondere arbeitet jeder solche Algorithmus mit einem unendlichen (aber lokal endlichen) Graphen. Das heißt, viele klassische Probleme (wie MIS) unterliegen einer Untergrenze von$\Omega(\log^* n)$ und kann daher nicht in einem unendlichen Netzwerk berechnet werden.

Weitere Diskussionen zu diesem Punkt finden Sie hier .

Universelle Graphen sind unendlich und eine Verallgemeinerung des von DE erwähnten Rado-Zufallsgraphen. Neuere Forschungen in diesem Bereich haben zum Ziel, universelle Graphen für eine Graphenfamilie F zu identifizieren: dh einen unendlichen Graphen, der zu F gehört und alle endlichen Graphen in F als induzierte Teilgraphen enthält.