Średnia długość ścieżek st (prostych) na skierowanym wykresie


11

Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?t s tstst

Pomocne mogą być również odpowiednie wyniki na specjalnych wykresach.


1
Jeśli dozwolone jest ponowne odwiedzanie wierzchołków przez ścieżki, wówczas nie prosta ścieżka sugeruje, że nie ma średniej długości, ponieważ długość będzie miała tendencję do nieskończoności. st
Shaull

@Shaull, masz rację. Myślałem o czasie uderzenia przypadkowego spaceru od do . Ale średnia długość ma tendencję do nieskończoności bez dalszych ograniczeń. tst
liuyu

wydaje się to bardzo zaawansowane, zalecamy migrację do cstheory
dniu

Jeśli dobrze rozumiem, to pytanie może zainteresować Cię w przypadku specjalnego wykresu.
Juho,

1
wygląda na to, że może to być związane z maksymalnym przepływem sieci? zwróć również uwagę na małe wykresy świata i różne inne wykresy z pewną symetrią, będzie dążyć do średniej długości ścieżki . dość naturalnym algorytmem może być losowe próbkowanie najkrótszych ścieżek - i spojrzenie na odchylenie standardowe wyników. tst
dniu

Odpowiedzi:


3

obliczanie / szacowanie / przybliżanie średniej długości ścieżki zostało zbadane dla niektórych modeli grafów losowych, w tym modelu Erdosa-Renyi i sieci wolnych w skali Barabasi-Alberta, a także małych wykresów światowych Strogatz, które mogą być odpowiednie jako przybliżenia dla twoich wykresów. [byłoby lepiej, gdybyś mógł zawęzić / uszczegółowić niektóre cechy charakterystyczne / wykresów, które studiujesz.]


Dzięki za komentarz i referencje. Z tym problemem wpadłem, próbując modelować obciążenie systemu przetwarzania zapytań za pomocą grafu probabilistycznego. Model graficzny ma pewne unikalne właściwości, które pozwalają mi sądzić, że może istnieć przybliżenie średniej długości ścieżek - . Jak zasugerowano w twoim komentarzu, losowe próbkowanie daje przybliżenie. Problem polega na tym, że nie podaje ona gwarantowanej górnej granicy aproksymacji, z wyjątkiem długości najdłuższej ścieżki - . Co gorsza, obliczenie samej najdłuższej ścieżki - jest problemem NP-zupełnym. t s t s tststst
liuyu,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.