Paths in vollständigen Graphen

Question

ich einen Freund habe, der die folgenden zu berechnen braucht:

Im vollständigen Graphen Kn (k < = 13), gibt es k * (k-1)/2 Kanten. Jede Kante kann auf 2 Arten gerichtet sein, also 2^[(k ​​* (k-1))/2] verschiedene Fälle.

Sie braucht P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X berechnen -> Y bedeutet: "Es gibt keinen Weg von X nach Y" und P [] ist die Wahrscheinlichkeit. Der Bruteforce-Algorithmus untersucht also jeden der 2^[(k ​​* (k-1))/2] verschiedenen Graphen, und da sie vollständig sind, muss man in jedem Graphen nur einen Satz von betrachten A, B, C, D wegen der Symmetrie.

P [A! -> B] wird dann berechnet als "Anzahl der Graphen ohne Pfad zwischen Knoten 1 und 2" dividiert durch die Gesamtzahl der Graphen, dh 2^[(k ​​* (k-1))/2].

Die Bruteforce-Methode funktioniert in Mathematica bis K8, aber sie benötigt K9, K10 ... bis K13.

Wir müssen natürlich nicht den kürzesten Weg in den Fällen finden, nur wollen, ob es einen gibt.

Wer hat Optimierungsvorschläge? (Dies klingt wie ein typisches Project Euler Problem).

Beispiel:

Die minimale Graph K4 haben 4 Ecken, Kanten 6 geben. Daher gibt es 2^6 = 64 mögliche Wege, um den Kanten Richtungen zuzuweisen, wenn wir die 4 Ecken A, B, C und D beschriften.

In einigen Graphen gibt es KEINEN Weg von A nach B (sagen wir X von ihnen) und in einigen anderen gibt es keinen Weg von C nach D (sagen wir Y). Aber in einigen Graphen, gibt es keinen Weg von A nach B, und zur gleichen Zeit kein Pfad von C nach D ist diese W.

So P[A !-> B]=X/64, P[C !-> D]=Y/64 und P[A !-> B && C !-> D] = W/64.

Update:

• A, B, C und D sind 4 verschiedene vertives, daher müssen wir mindestens K4.
• Beachten Sie, dass es sich um DIRECTED-Graphen handelt, daher reicht eine normale Darstellung mit UT-Matrizen nicht aus.
• Es gibt eine Funktion in Mathematica, die die Entfernung zwischen den Knoten in einem gerichteten Graphen findet (wenn sie unendlich zurückgibt, gibt es keinen Pfad), aber das ist ein bisschen übertrieben, da wir die Entfernung nicht brauchen ein Pfad oder nicht.

Answer 1

Ich habe eine Theorie, aber ich habe keine Mathematik, um es zu testen, also hier geht. (Und bitte entschuldigen Sie meine Fehler in der Terminologie, ich bin mit der Graphentheorie nicht wirklich vertraut.)

Ich stimme zu, dass es 2^(n * (n-1)/2) verschiedene gerichtete Kn-Graphen gibt. Die Frage ist, wie viele davon einen Pfad A-> B enthalten. Nenne diese Nummer S (n).

Angenommen, wir kennen S (n) für einige n, und wir wollen einen weiteren Knoten X hinzufügen und S (n + 1) berechnen. Wir werden nach Pfaden X-> A suchen.

Es gibt 2^n Wege X an die bereits existierenden Graph zu verbinden.

Der Rand X-A in der "richtigen" Richtung (x-> A) hindeuten könnte; Es gibt 2^(n-1) Wege, X auf diese Weise zu verbinden, und es wird zu einem Pfad für jedes der 2^(n * (n-1)/2) verschiedenen Kn-Graphen führen.

Wenn X-A zeigt auf X, versuchen die Kante X-B. Wenn X-B auf B zeigt (und es gibt 2^(n-2) solche Wege, X zu verbinden), dann geben einige Kn-Graphen tatsächlich einen Pfad B-> A, S (n) von ihnen.

Wenn X-B auf X zeigt, versuchen Sie X-C; Es gibt 2^(n-3) S (n) erfolgreiche Graphen dort. Wenn meine Mathematik korrekt ist, S (n + 1) = 2^((n + 2) (n-1)/2) + (2^(n-1) -1) S (n)

So ergibt dies folgendes:

 
S(2) = 1 
S(3) = 5 
S(4) = 47 
S(5) = 841 
S(6) = 28999 

Kann das jemand überprüfen? Oder geben Sie eine geschlossene Form für S (n)?

EDIT:
Ich sehe jetzt, dass der schwierige Teil ist das P [A -> B & & C -> D!]. Aber ich denke, der Rekursionsansatz wird immer noch funktionieren: Beginnen Sie mit {A, B, C, D}, fügen Sie dann Punkte hinzu und verfolgen Sie die Anzahl der Graphen, in denen A -> (a Punkte), (b Punkte) -> B, C -> (c Punkte) und (d Punkte) -> D, unter Beibehaltung der gewünschten Einschränkung. Hässlich, aber handlich.

Answer 2

Ich denke, dass Grafik mit Matrix darzustellen sehr hilfreich sein wird.

Wenn A!->B setzen in a-ten Zeile und der B-te Spalte.

Put überall sonst.

Count nicht von 0s = Z.

dann P[A!->B] = 1/2^Z

=>P[A!->B && C!->B] - P[A!-B].P[C!-D] = 1/2^2 - 1/ 2^(X-2) // Somthing falsch ich hier fixin es whereX = k(k-1)/2

 
    A B C D 
A . 0 1 1 
B . . 1 1 
C . . . 1 
D . . . . 

HINWEIS: Wir obere Dreieck ohne Beschränkung der Allgemeinheit nutzen können.

Answer 3

Die Brute-Force-Ansatz aller Graphen unter Berücksichtigung werden Sie nicht viel weiter kommen, werden Sie mehr als ein Diagramm zu einer Zeit, betrachten haben.

Für 8 haben Sie 2^28 ~ 256 Millionen Grafiken.

9: 2^36 ~ 64 Milliarden

10: 2^45 ~ 32 Billionen

11: 2^55> 10

12: 2^66> 10

13: 2^78> 10

Fo Zum Zweck der Suche nach Wegen ist der interessante Teil die partielle Ordnung auf den stark verbundenen Komponenten des Graphen. Eigentlich muss die Reihenfolge total sein, da zwischen zwei Knoten eine Kante liegt.

So können Sie versuchen, Gesamtbestellungen in Betracht zu ziehen, es gibt sicherlich viel weniger als Diagramme.