Durchschnittliche Länge von st (einfachen) Pfaden in einem gerichteten Graphen

In Anbetracht der Tatsache , dass - Pfad Aufzählung a # P-vollständigen Problem ist, könnte es effiziente Methoden sein , dass Compute (oder zumindest ungefähr) die durchschnittliche Länge - Weg ohne sie aufzählt? ~~Was ist, wenn Pfade Scheitelpunkte erneut besuchen dürfen?~~ $s$ $t$ $s$ $t$

Relevante Ergebnisse in speziellen Diagrammen könnten ebenfalls hilfreich sein.

algorithms complexity-theory graphs approximation enumeration liuyu
quelle

Wenn Pfade Scheitelpunkte erneut besuchen dürfen, impliziert ein nicht einfacher

Pfad, dass es keine durchschnittliche Länge gibt, da die Länge gegen unendlich tendiert.

s - t

$s-t$

Shaull

@Shaull, du hast recht. Ich dachte an die Schlagzeit eines zufälligen Spaziergangs von

nach

. Die durchschnittliche Länge tendiert jedoch ohne weitere Einschränkungen zur Unendlichkeit.

s

$s$

t

$t$

Liuyu

Dies scheint sehr weit fortgeschritten zu sein. Empfehlen Sie die Migration zu cstheory

vzn

Wenn ich richtig verstehe, könnte diese Frage für Sie für ein spezielles Diagramm von Interesse sein.

Juho

scheint dies mit dem maximalen Netzwerkfluss zu tun zu haben? Beachten Sie auch, dass kleine Weltgraphen und verschiedene andere Graphen mit einer gewissen Symmetrie zur durchschnittlichen Pfadlänge tendieren . Ein ziemlich natürlicher Algorithmus könnte darin bestehen, die kürzesten

- Pfade zufällig abzutasten und die Standardabweichung der Ergebnisse zu betrachten.

s

$s$

t

$t$

vzn

Antworten: