ich sitz schon seit einer geraumer zeit an der aufgabe 2.4.
und irgendwie rall ich einfach nicht wie ich aufzeigen kann, dass das problem in NP ist.
der zweite beweisschritt ist ja einleuchtend, aber der erste…
HILFE Dx kann mit jemand nen tipp geben oder kennt jemand ne nützliche seite, wo anhand eines beispiels die NP-vollständigkeit bewiesen wird?

Aufgabe:
Beweisen Sie, dass das folgende Problem NP-vollständig ist:
Gegeben: Zwei Graphen G1 = (V1,E1) und G2 = (V2,E2).
Frage: Gibt es Teilmengen V (teilmenge) V1 und E (teilmenge) E1 derart, dass |V | = |V2| und |E| = |E2| gilt und eine bijektive Abbildung f : V2 -> V existiert mit {u, v} 2 E2 genau
dann, wenn {f(u), f(v)} 2 E.

Frage:
Gibt es Teilmengen [latex]V \subseteq V_1[/latex] und [latex]E \subseteq E_1[/latex] derart,
dass [latex]|V| = |V_2|[/latex] und [latex]|E| = |E_2|[/latex] gelten und eine bijektive
Abbildung [latex]f: V_2 \to V[/latex] existiert mit [latex]\{u,v\} \in E_2[/latex] genau dann,
wenn [latex]\{f(u),f(v)\} \in E[/latex].

/fixed

Im Prinzip geht das immer so: Kannst du alle Möglichkeiten (hier: Bijektionen) in polynomieller Zeit auf einer NTM bilden? Kann eine NTM für eine konkrete Möglichkeit in polynomieller Zeit entscheiden, ob sie "gültig" ist? Dann ist das Problem in NP entscheidbar.

Es handelt sich um das SUBGRAPH-ISOMORPHISM-Problem. Das lässt sich dann googeln.