Do czego służą wykresy nieskończone?

Właśnie przeczytałem na niemieckiej Wikipedii, że nieskończony wykres to wykres z nieskończoną liczbą węzłów lub nieskończoną liczbą krawędzi. Znam tylko aplikacje i algorytmy dla grafów skończonych.

Do czego służą wykresy nieskończone?

Jakie są ich zastosowania? Nie wyobrażam sobie algorytmów, które działałyby na nieskończonych grafach, ponieważ nie można przechowywać nieskończonego wykresu. Więc nie możesz na tym operować.

Wiele problemów z wyszukiwaniem w sztucznej inteligencji (takich jak przeszukiwanie drzewa gry w szachy lub szukanie rozwiązań zagadek, takich jak kostka Rubika, lub bardziej ogólnie wyszukiwanie sekwencji działań do wykonania w celu osiągnięcia pożądanego celu) polega na: efekt, algorytmy na nieskończonych grafach, mimo że pożądana odpowiedź jest skończoną ścieżką. Z pewnością możliwe jest wykonywanie algorytmów na takich grafach, jeśli są one reprezentowane w sposób dorozumiany .

Ale prawdą jest również, że matematyka może być użyteczna, nawet jeśli nie jest to matematyka problemów, które można rozwiązać za pomocą algorytmów. Nieskończone wykresy mogą być wykorzystane do modelowania procesów narodzin i śmierci (np. W jaki sposób nasze zasady dziedziczenia nazwisk oraz tempo narodzin i śmierci ludzi prowadzą do nierównomiernego rozkładu nazwisk rodzinnych między różnymi kulturami ludzkimi?), Aby uzyskać ramy do podchodzenia do pytań o symetrie matematyczne (za pomocą często nieskończonych grafów Cayleya ) w celu dostarczenia modeli do wnioskowania o systemach logiki (patrz wykres Rado i model nasycony ) itp.

W obszarze antyferromagnetycznym modelu Isinga złożoność obliczeń przybliżania zliczania zależy od miary Gibbsa względem nieskończonych drzew nieregularnych. Miara Gibbsa na tych nieskończonych drzewach nieregularnych przechodzi fazę na linii zwanej progiem wyjątkowości.$d$$d$

Po jednej stronie progu model Isinga jest trudny do przybliżenia. Po drugiej stronie progu model Isinga jest łatwy do przybliżenia. Złożoność modelu Isinga wzdłuż progu unikatowości jest obecnie otwartym problemem, ale można przypuszczać, że jest on wykonalny.

Najnowszym rezultatem tej linii pracy jest Sly an Sun. Zobacz odniesienia do innych powiązanych prac.

Aby dać ci konkretną aplikację, w której warto pomyśleć o nieskończonych grafach, zastanów się nad siecią rozproszonych węzłów, z których każdy uruchamia algorytm rozproszony, który przebiega w rundach. W każdej rundzie węzeł może aktualizować swój stan, wykonując lokalne obliczenia i komunikować się, wysyłając / odbierając wiadomości do / od swoich sąsiadów. Wyjście takiego algorytmu jest połączonym wyjściem wszystkich węzłów. Na przykład każdy węzeł może lokalnie decydować, czy jest częścią niezależnego zestawu.

Niektóre problemy przetwarzania rozproszonego można rozwiązać w stałym czasie (tj. Stała liczba rund do momentu zakończenia wszystkich węzłów), bez względu na liczbę węzłów w sieci. W szczególności dowolny taki algorytm będzie działał na nieskończonym (ale lokalnie skończonym) wykresie. Mimo to, wiele klasycznych problemów (jak MIS) podlegają dolna granica z , a zatem nie mogą być obliczane na nieskończonej sieci.$\Omega(\log^* n)$

Dalszą dyskusję na ten temat można znaleźć tutaj .

uniwersalne wykresy są nieskończone i uogólnienie losowego wykresu Rado wspomnianego przez DE. ostatnie badania w tym obszarze zmierzają do identyfikacji uniwersalnych grafów dla rodziny grafów F: tzn. grafu nieskończonego należącego do F, który zawiera wszystkie grafy skończone w F jako indukowane podgrafy.