Frage:
Zeigen Sie das k-Clique für festes k in P
Ansatz:
Im ungerichteten Graphen G gibt es n Knoten, ein naiver Algorithmus müsste $$n\choose k$$ mögliche Lösungen prüfen. Unter der Annahme das n ≥ k, eine Clique größer als der Graph würde sofort terminieren, ist kann ich folgendes verwenden.
$${n \choose k}=\frac{n!}{k!+(n-k!)}$$
Woraus resultiert:
$${n \choose k}=\frac{n*(n-1)*(n-2)*...*(n-k)!}{k!+(n-k)!}$$
Durch kürzen müsste dafür resultieren:
$${n \choose k}=\frac{n*(n-1)*(n-2)*...*(n-(k-1))}{k!}$$
Da durch festes k im Nenner eh eine feste Zahl steht, kann ich jetzt nur den Zähler betrachten, der ausmultipliziert zu einem Polynom wird. Also ist die Laufzeit in diesem Fall \(\mathcal{O}(n^{n-1})\)
Ist das so korrekt?