Fragen zur A32 a)

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Fragen zur A32 a)
Mitschrift zur A32
a)
https://www.dropbox.com/s/8j2p7xg9uhu7yhl/P32%20a.jpg?dl=0

Habe ich Folgendes richtig verstanden?

Der Verifizierer vom Independent Set Problem: M_ent_IS
liest die Kodierung eines Graphen mit k € IN: <G,k>
sowie die zu verifizierende Knotenauswahl mit den jeweiligen Indizes zu den Knoten binär kodiert: bin(i_1)# bin(i_2)# … # bin(i_k)
als Eingabe ein.

Danach wird in (4) und (5) überprüft, ob die Knotenauswahl gültig ist.
In (6) bis (7) werden für alle Knotenpaare k_1und k_2 , die in G durch eine Kante verbunden sind, mit der Knotenauswahl verglichen. Falls nun in der Knotenauswahl ein Knotenpaar vorkommt, welches in G eine Kantenverbindung hat, wird nicht akzeptierend gehalten, sonst wird akzeptierend gehalten.

Es müsste doch in M_ent_IS, um zu verifizieren, ob ein Independent Set für <G,k> existiert, alle möglichen Knotenkombinationen für die Knotenauswahl überprüft werden, oder?