Pfade auf einem Dodekaeder

Lassen$A$sei die Adjazenzmatrix. Dann$A^k$gibt Ihnen die Anzahl der Pfade der Länge$k$zwischen entsprechenden Scheitelpunkten. (Dies funktioniert für jeden Graphen.) Dies kann sehr schnell berechnet werden, und Sie können auch Asymptotiken usw. erhalten, indem Sie Eigenwerte berechnen.

Es gibt zum Beispiel

171619248

solche Pfade der Länge 20 (nicht zu weit von MJDs Vermutung entfernt) und

25768876036573921452762172776956776774411837488

solche Pfade der Länge 100.

Es ist nicht erforderlich, die vollständige Adjazenzmatrix des Dodekaeders aufzustellen. Zeichnen des Kantengraphen mit dem Startpunkt$v_0$in der Mitte und dem gegenüberliegenden Scheitelpunkt im Unendlichen erkennt man, dass es aufgrund der Symmetrie nur sechs Klassen gibt$C_i$ $(0\leq i\leq5)$von Scheiteln.

Es genügt also, die Zahlen zu betrachten$p_i(n)$, wobei$p_i(n)$bezeichnet die Anzahl der Wege, um einen Knoten der Klasse zu erreichen$C_i$in genau$n$Schritte, beginnend bei$v_0$. Wenn ich meine Zeichnung betrachte, erhalte ich dann die folgenden Gleichungen:

$${\bf p}(n+1)=\left[\matrix {0&3&0&0&0&0\cr 1&0&2&0&0&0\cr 0&1&1&1&0&0\cr 0&0&1&1&1&0\cr 0&0&0&2&0&1\cr 0&0&0&0&3&0\cr}\right]\>{\bf p}(n)\ ,$$ wodurch${\bf p}(n)$bezeichnet den Spaltenvektor der$p_i(n)$.

Da es bereits so viele Behandlungen des Problems gibt, höre ich hier auf.

Eine Möglichkeit, Pfade in einem Diagramm zu zählen$\Gamma$, sagen wir, mit Scheitelpunkten$v_i$, ist seine Adjazenzmatrix zu verwenden : Dies ist die quadratische Matrix$A_{\Gamma}$von Größe$|\Gamma|$wofür die$(i, j)$Eintrag$(A_{\Gamma})_{ij}$ist die Anzahl der Kanten mit Endpunkten an Scheitelpunkten$v_i$Und$v_j$. Ein intuitives induktives Argument zeigt dann, dass die Anzahl der Pfade der Länge entspricht$n$aus$v_i$Zu$v_j$ist genau$(A_{\Gamma}^n)_{ij}$.

Der SageMath- Code Delta = graphs.DodecahedralGraph(); Delta.plot()weist dem dodekaedrischen Graphen den Namen zu Deltaund gibt den folgenden beschrifteten Plot des Graphen zurück, den wir aufrufen$\Delta$. NB Sage beginnt mit der Indizierung bei$0$. Eine kleine Visualisierung zeigt das, zB der gegenüberliegende Scheitelpunkt$v_0$ist Scheitel$v_{15}$.

A = dodecahedral.adjacency_matrix()Als nächstes weist der Sage-Befehl Ader Adjazenzmatrix zu$A_{\Delta}$von$\Delta$; es hat größe$|\Delta| = 20$.

$$\small A_{\Delta} = \pmatrix{ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 } .$$

Unter Verwendung unserer obigen kombinatorischen Interpretation von$A_{\Delta}^n$gibt an, dass die Anzahl der Pfade der Länge$n$aus$v_0$zum gegenüberliegenden Scheitel$v_{15}$Ist

$$\boxed{p_n = (A_{\Delta}^n)_{0, 15}}.$$ Bitten Sie Sage, zu rechnen$p_1, \ldots, p_{12}$und fügen Sie sie hinzu, sagen wir, mit dem Code n = var('n'); sum([(A^n)[0, 15] for n in range(1,13)]), gibt das $$\color{#df0000}{\boxed{p_1 + \cdots + p_{12} = 34548}} ,$$ was mit MJDs Zählung übereinstimmt.

Das kann man auf einleuchtendere Weise herleiten. Berechnen$A_{\Gamma}^n$effizient ist es sinnvoll, die Jordan-Zerlegung zu verwenden$A_{\Gamma} = Q J Q^{-1}$. Dann,$A_{\Gamma}^n = (Q J Q^{-1})^n = Q J^n Q^{-1}$. Da eine Adjazenzmatrix (eines ungerichteten Graphen) symmetrisch ist,$A_{\Gamma}$ist diagonalisierbar und somit$J$ist diagonal, sagen wir,$J = \operatorname{diag}(\lambda_i)$, Und$J^n = \operatorname{diag}(\lambda_i^n)$.

Nun, die Anzahl der Pfade der Länge$n$aus$v_i$Zu$v_j$Ist

$$(A_{\Delta}^n)_{ij} = (Q J^n Q^{-1})_{ij} = \sum_{k, \ell} Q_{ik} (J^n)_{k \ell} Q^{-1}_{\ell j} ,$$ und da$J^n$ist diagonal mit Einträgen$\lambda_a^n$, Terme tragen nur dann zur Summe bei$\ell = k$, Verlassen $$(A_{\Delta}^n)_{ij} = \sum_k (Q_{ik} Q^{-1}_{kj}) \lambda_k^n .$$ Die Anzahl der Pfade von$v_i$Zu$v_j$der Länge$\leq m$ist dann die Teilsumme $$\sum_{n = 0}^m (A_{\Delta}^n)_{ij} =\sum_{n = 0}^m \sum_k (Q_{ik} Q^{-1}_{kj}) \lambda_k^n =\sum_k (Q_{ik} Q^{-1}_{kj}) \sum_{n = 0}^m \lambda_k^n =\sum_k (Q_{ik} Q^{-1}_{kj}) \frac{\lambda_k^{m + 1} - 1}{\lambda_k - 1},$$ wo wir interpretieren$\frac{\lambda_k^{m + 1} - 1}{\lambda_k - 1}$als$m + 1$Wenn$\lambda_k = 1$.

Für den Dodekaedergraphen$\Delta$, die Jordan-Zerlegung (erzeugt zum Beispiel mit A.change_ring(QQ[sqrt(5)]).jordan_form(transformation=True)), ist gegeben durch

$$J = \operatorname{diag}(3, \sqrt{5}, \sqrt{5}, \sqrt{5}, -\sqrt{5}, -\sqrt{5}, -\sqrt{5}, 0, 0, 0, 0, -2, -2, -2, -2, 1, 1, 1, 1, 1) ,$$ $$\begin{multline*}Q \\ = \scriptsize \pmatrix{ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & -\phi & \phi & 1 & \phi^{-1} & -\phi & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & \phi^{-1} & -2 & \phi & -\phi & -2 & -\phi & 1 & 1 & 0 & 1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 \\ 1 & -\phi & -\phi & 1 & \phi & \phi & 1 & -1 & 0 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & -1 & 1 & -1 & 1 \\ 1 & -1 & \phi^{-1} & \phi^{-1} & -1 & -\phi & -\phi & 0 & -1 & 0 & -1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 \\ 1 & -\phi & 2 & -\phi & \phi^{-1} & 2 & \phi & 1 & 0 & 0 & 1 & 1 & 2 & 2 & 1 & -1 & 0 & -1 & 0 & -1 \\ 1 & -1 & \sqrt{5} & -1 & -1 & -\sqrt{5} & -1 & -1 & 0 & -1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 & 0 \\ 1 & -\phi & 2 & -\phi & \phi & 2 & \phi^{-1} & -1 & -1 & 0 & -1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 \\ 1 & \phi^{-1} & \phi^{-1} & -1 & -\phi & -\phi & -1 & 1 & 0 & 1 & 1 & -1 & 0 & 1 & 1 & 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -\phi & -\phi & 1 & \phi & \phi & 0 & 1 & 0 & 1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 \\ 1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & -1 & \phi & -\phi & -1 & -\phi & \phi^{-1} & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & -\phi & \phi & -1 & \phi^{-1} & -\phi & -1 & 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 & 0 & 0 & -1 & 1 & -1 \\ 1 & -1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & -\sqrt{5} & 1 & 1 & \sqrt{5} & 1 & 1 & 0 & 1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 & 0 \\ 1 & \phi & -2 & \phi^{-1} & -\phi & -2 & -\phi & -1 & 0 & 0 & -1 & 1 & 2 & 2 & 1 & -1 & 0 & -1 & 0 & -1 \\ 1 & \phi & -\phi & 1 & -\phi & \phi^{-1} & 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 0 & -1 & 1 & -1} .\end{multline*}$$ Hier,$\phi := \frac{1}{2}(1 + \sqrt{5})$ist der Goldene Schnitt.

Nehmen$i = 0, j = 15$und das Ersetzen (oder nur das Ausführen von (A^n)[0, 15]) ergibt

$$\boxed{p_n = (A_{\Delta}^n)_{0, 15} = \frac{1}{20} \cdot 3^n - \frac{3}{20} (1 + (-1)^n) (\sqrt{5})^n + \frac{1}{5} \, \left(-2\right)^n + \frac{1}{4}}.$$ (Dies stimmt mit der Formel überein, die in OEIS A054883 angegeben ist , Anzahl der Spaziergänge der Länge n entlang der Kanten eines Dodekaeders zwischen zwei gegenüberliegenden Scheitelpunkten .) Dann die Anzahl solcher Längenpfade$\leq m$ist die Teilsumme$s_m = \sum_{n = 0}^m p_n$, und in der Tat,$s_{12} = 34548$wie behauptet.

Für groß$n$, die Formel für$p_n$dominiert der erste Term, also$p_n \sim \frac{1}{20} \cdot 3^n$; also für groß$m$,$s_m \sim \frac{1}{40} \cdot 3^{m + 1}$.

Bearbeiten Ein Christian Blatter hat in seiner Antwort festgestellt, dass die Ausnutzung der Symmetrie des Dodekaeders das Problem in ein Pfadzählproblem auf dem Digraphen übersetzt$\Delta'$von Klassen$C_0, \ldots, C_5$von Scheitelpunkten, wo$C_k$besteht aus den Eckpunkten der Entfernung$k$aus$v_0$. Dies ergibt die Adjazenzmatrix

$$A_{\Delta'} = \pmatrix{ 0&3&0&0&0&0\cr 1&0&2&0&0&0\cr 0&1&1&1&0&0\cr 0&0&1&1&1&0\cr 0&0&0&2&0&1\cr 0&0&0&0&3&0\cr}.$$ Die Anzahl der Längenpfade$n$aus$C_0$(die nur einen einzigen Scheitelpunkt enthält) zu$C_5$(das seinen Antipodenscheitel enthält) ist dann$(A_{\Delta'}^n)_{05}$. Wie zuvor können wir dies effizient mit der Jordan-Zerlegung berechnen$A_{\Delta'} = Q' J' (Q')^{-1}$, Wo $$J' = \operatorname{diag}(3, \sqrt{5}, 1, 0, -2, -\sqrt{5}), \qquad Q' = \pmatrix{ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \frac{1}{3} \sqrt{5} & \frac{1}{3} & 0 & -\frac{2}{3} & -\frac{1}{3} \sqrt{5} \\ 1 & \frac{1}{3} & -\frac{1}{3} & -\frac{1}{2} & \frac{1}{6} & \frac{1}{3} \\ 1 & -\frac{1}{3} & -\frac{1}{3} & \frac{1}{2} & \frac{1}{6} & -\frac{1}{3} \\ 1 & -\frac{1}{3} \sqrt{5} & \frac{1}{3} & 0 & -\frac{2}{3} & \frac{1}{3} \sqrt{5} \\ 1 & -1 & 1 & -1 & 1 & -1 . } .$$

Ich arbeite immer noch an einer kombinatorischen Methode zur Berechnung der Antwort, und ich bin möglicherweise nicht erfolgreich. In der Zwischenzeit sind hier die Ergebnisse einer Computeraufzählung aller Pfade:

$$\begin{array}{rrr} \text{Length} & \text{Simple paths} & \text{All paths} \\ 5 & 6 & 6 \\ 6 & 12 & 12 \\ 7 & 6 & 84 \\ 8 & 12 & 192 \\ 9 & 30 & 882 \\ 10 & 24 & 2\;220 \\ 11 & 42 & 8\;448 \\ 12 & 84 & 22\;704 \\ 13 & 96 & 78\;078 \\ 14 & 132 & 218\;988 \\ 15 & 150 & 710\;892 \\ 16 & 72 & 2\;048\;256 \\ 17 & 48 & 6\;430\;794 \\ 18 & 60 & 18\;837\;516\\ 19 & 6 & 58\;008\;216\\ \hline \text{Total} & 780 & 86\;367\;288 \end{array}$$

Die vollständige Aufzählung der Pfade dauerte auf meinem Laptop etwa eine halbe Stunde, und die Ausgabedatei ist 5,3 GB roh, 0,25 GB komprimiert. Aus theoretischen und empirischen Gründen können wir davon ausgehen, dass es ungefähr 180 Millionen Pfade der Länge 20 geben würde, deren Berechnung ungefähr 55 Minuten dauern würde. (Nach der Berechnung der$1\;042\;506$Pfade bis Länge 15, ich schätze es wären rund 81 mal so viele Pfade bis Länge 19, bzw$84\;442\;986$, was dem richtigen Ergebnis ziemlich nahe kommt.)