Для чего нужны бесконечные графики?

Я только что прочитал в немецкой Википедии, что бесконечный граф - это граф с бесконечным числом узлов или бесконечным числом ребер. Я знаю только приложения и алгоритмы для конечных графов.

Для чего нужны бесконечные графики?

Каковы приложения тех? Я не могу представить алгоритмы, которые будут работать на бесконечных графах, так как вы не можете хранить бесконечный граф. Таким образом, вы не можете оперировать этим.

Многие проблемы поиска в искусственном интеллекте (такие как поиск по дереву игры в шахматы или поиск решений головоломок, таких как кубик Рубика, или, в более общем случае, поиск последовательностей действий, которые необходимо выполнить для достижения некоторой желаемой цели), в эффект, алгоритмы на бесконечных графах, хотя желаемый ответ является конечным путем. Конечно, можно выполнять алгоритмы на таких графах, если они представлены неявно .

Но верно и то, что математика может быть полезной, даже если это не математика проблем, которые могут быть решены с помощью алгоритмов. Бесконечные графики могут использоваться для моделирования процессов рождения и смерти (например, как наши правила наследования имен и скорости, с которой люди рождаются и умирают, приводят к неравномерному распределению фамилий между различными человеческими культурами?), Чтобы дать основа для подхода к вопросам о математических симметриях (с помощью графов Кэли , которые часто бывают бесконечными), для предоставления моделей для рассуждений о системах логики (см. граф Радо и насыщенная модель ) и т. д.

$d$$d$

С одной стороны порога модель Изинга трудно аппроксимировать. С другой стороны порога модель Изинга легко аппроксимировать. Сложность модели Изинга вдоль порога уникальности в настоящее время является открытой проблемой, но гипотеза заключается в том, что она поддается решению.

Самый последний результат в этой области - Sly a Sun. Смотрите их ссылки на другие связанные работы.

Чтобы дать вам конкретное приложение, в котором полезно думать о бесконечных графах, рассмотрим сеть распределенных узлов, каждый из которых запускает распределенный алгоритм, который выполняется в раундах. В каждом раунде узел может обновлять свое состояние, выполняя локальные вычисления и связываться, отправляя / получая сообщения своим соседям. Результатом такого алгоритма является объединенный вывод всех узлов. Например, каждый узел может локально решить, является ли он частью независимого набора.

$\Omega(\log^* n)$

Дальнейшее обсуждение этого вопроса можно найти здесь .

универсальные графы бесконечны - обобщение случайного графа Радо, упомянутое DE. Недавние исследования в этой области направлены на выявление универсальных графов для семейства графов F, т. е. бесконечного графа, принадлежащего F, который содержит все конечные графы в F в качестве индуцированных подграфов.