Graphen Isomorphie - Laufzeit
Im ersten Teil des Textes zeige ich, dass die best case Laufzeit, um zwei Graphen auf Isomorphie zu prüfen $\mathcal O(1)$ ist. Dabei werden die Knoten nach ihrem Knotengrad sortiert und diese jeweils permutiert. Im zweiten Teil sind anfängliche Überlegungen, wie man die mittlere Laufzeit des Algorithmus bestimmen könnte.
Nehme ohne Einschränkung an, dass der Graph zusammenhängend ist. Sei $$D_n = \{ v \in V : dg(v) = n \}$$ die Menge aller Knoten mit Grad $n$. Für einen Graphen $G=(V,E)$ gilt für den Knotengrad, dass $dg(v) < |V|$. (Ein Knoten kann maximal mit allen anderen $|V|-1$ Knoten verbunden sein) Damit sind alle Mengen $D_n$ mit $n=0$ oder $n >= |V|$ leer und die Menge $$P=\{D_n : 0 < n < |V| \}$$ bildet eine Partition von $V$. Enthält nun jedes $D_n$ (für $0<n<|V|$) mindestens ein Element, so folgt, dass es ein $n'$ gibt, so dass $|D_{n'}|=2$ und für alle $0<\tilde n<|V|$, $\tilde n \neq n'$ gilt $|D_{\tilde n}|=1$. Das ist der oben genannte best case, da es nur zwei Knoten mit demselben Grad gibt. Eine Laufzeit von $\mathcal O(1)$ erhält man, wenn man die Berechnung der Grade o.ä. vernachlässigt (sonst wäre es $\mathcal O(|V| \cdot |E|)$).
Ich habe versucht eine mittlere Laufzeit (über die Stochastik) zu finden, sehe da aber noch keine Ende. Mein Ansatz:
Die Laufzeit hängt sicherlich direkt von der Anzahl der nichtleeren Mengen $D_n$ und die Verteilung der Knoten in diesen ab. Um da irgendwo anzufangen, betrachte ich für eine Knotenmenge $V$ alle möglichen Partitionen in Abhängigkeit von der Anzahl der nichtleeren Mengen $D_n$. $P_k$ gibt die Anzahl der möglichen Verbindungen ($E$) zurück, so dass genau $k$ nichtleere Mengen $D_n$ existieren: $$P_k = {n-1 \choose k} S(n,k) \cdot k!$$ Kommentar: $n=|V|$ und $S(n,k)$ ist hier die Stirling Zahl zweiten Grades, welche die Anzahl der möglichen $k$-Partitionen einer $n$-elementigen Menge angibt. Diese Formel habe ich kombinatorisch hergeleitet und scheint zu stimmen, da folgendes gelten muss: $$\sum_{k=1}^{n-1} P_k = (n-1)^n$$ (Beweis durch Bespiel :P)
Wieso das gelten muss: Wenn man sich überlegt, wie viele Möglichkeiten es gibt, $n$ Knoten auf $n-1$ Mengen zu verteilen, dann entspricht das $(n-1)^n$. Für ein festes $k$ gibt $P_k$ ja an, wie viele Möglichkeiten es gibt, $n$ Elemente auf $k$ aus $n-1$ Mengen zu verteilen. Zusammen summiert muss das genau der Anzahl aller Möglichkeiten entsprechen. Vielleicht hat jemand anderes mehr Ahnung in Stochastik, als ich es habe und kann sich hier was denken.
Nehme ohne Einschränkung an, dass der Graph zusammenhängend ist. Sei $$D_n = \{ v \in V : dg(v) = n \}$$ die Menge aller Knoten mit Grad $n$. Für einen Graphen $G=(V,E)$ gilt für den Knotengrad, dass $dg(v) < |V|$. (Ein Knoten kann maximal mit allen anderen $|V|-1$ Knoten verbunden sein) Damit sind alle Mengen $D_n$ mit $n=0$ oder $n >= |V|$ leer und die Menge $$P=\{D_n : 0 < n < |V| \}$$ bildet eine Partition von $V$. Enthält nun jedes $D_n$ (für $0<n<|V|$) mindestens ein Element, so folgt, dass es ein $n'$ gibt, so dass $|D_{n'}|=2$ und für alle $0<\tilde n<|V|$, $\tilde n \neq n'$ gilt $|D_{\tilde n}|=1$. Das ist der oben genannte best case, da es nur zwei Knoten mit demselben Grad gibt. Eine Laufzeit von $\mathcal O(1)$ erhält man, wenn man die Berechnung der Grade o.ä. vernachlässigt (sonst wäre es $\mathcal O(|V| \cdot |E|)$).
Ich habe versucht eine mittlere Laufzeit (über die Stochastik) zu finden, sehe da aber noch keine Ende. Mein Ansatz:
Die Laufzeit hängt sicherlich direkt von der Anzahl der nichtleeren Mengen $D_n$ und die Verteilung der Knoten in diesen ab. Um da irgendwo anzufangen, betrachte ich für eine Knotenmenge $V$ alle möglichen Partitionen in Abhängigkeit von der Anzahl der nichtleeren Mengen $D_n$. $P_k$ gibt die Anzahl der möglichen Verbindungen ($E$) zurück, so dass genau $k$ nichtleere Mengen $D_n$ existieren: $$P_k = {n-1 \choose k} S(n,k) \cdot k!$$ Kommentar: $n=|V|$ und $S(n,k)$ ist hier die Stirling Zahl zweiten Grades, welche die Anzahl der möglichen $k$-Partitionen einer $n$-elementigen Menge angibt. Diese Formel habe ich kombinatorisch hergeleitet und scheint zu stimmen, da folgendes gelten muss: $$\sum_{k=1}^{n-1} P_k = (n-1)^n$$ (Beweis durch Bespiel :P)
Wieso das gelten muss: Wenn man sich überlegt, wie viele Möglichkeiten es gibt, $n$ Knoten auf $n-1$ Mengen zu verteilen, dann entspricht das $(n-1)^n$. Für ein festes $k$ gibt $P_k$ ja an, wie viele Möglichkeiten es gibt, $n$ Elemente auf $k$ aus $n-1$ Mengen zu verteilen. Zusammen summiert muss das genau der Anzahl aller Möglichkeiten entsprechen. Vielleicht hat jemand anderes mehr Ahnung in Stochastik, als ich es habe und kann sich hier was denken.