0 Daumen
445 Aufrufe

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?

von

Upps, da ist mir glaube ich ein Fehler unterlaufen.

Die Laufzeit ist ja nicht \(\mathcal{O}(n^{n-1})\) sondern \(n^{k}\)

Ah, beim binominalkoeffizient hat sich auch ein Fehler eingeschlichen. Es müsste

\({n \choose k}=\frac{n*(n-1)*(n-2)*...*(n-k)!}{k!(n-k)!}\)

sein

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community