Adjazenzmatrix

Melvin · Anmeldungsdatum: 24.05.2005 Beiträge: 5

Hallo,
ich habe eine Aufgabe, wo ich nicht genau weiß wie ich an dieser Aufgabe vorgehen soll.
Kann einer mit bitte dabei helfen?

Ich weiß, was ein gerichterer Graph, eine Senke und ein Adjazenzmatrix ist, aber verstehe nicht, was sie mit kleinergleich 3n Einträgen von A und mit 0(1) zusätzlichen Speicherplätzen meinen.

Ich würde mich sehr freuen, wenn mir einer bei dieser Aufgabe helfen könnte.

Es sei G=(V,E) ein gerichteter Graph mit n>1 Knoten. A sei die Adjazenzmatrix von G. Zeigen Sie: Es gibt einen Algorithmus, der durch Betrachtung von kleinergleich 3n Einträgen
Von A und mit O(1) zusätzlichen Speicherplätzen entscheidet, ob eine Senke in G existiert und diese, falls ja, ausgibt.

Gruß
Melvin

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Gegeben sind ein Graph mit n Knoten. n ist also die Eingabegröße. Die Adjazenzmatirx hat

Einträge. Wenn du jeden Eintrag anschauen müsstest, würdest du also n*n Einträge durchgehen müssen. Jetzt sollst du aber einen Algorithmus entwerfen, der nur maximal 3*n Einträge betrachtet. Du darfst dir also nicht alle anschauen. Zusätzlich darf dein Programm nur konstant viel Speicherbedarf haben. Das wird mit dem O-Kalkül ausgedrückt: O(1) bedeutet konstant viel. Du darfst also nur eine endliche anzahl von Speicher-Variablen und Arrays verwenden, und der benötigte Platz muss vollkommen unabhängig von der EIngabegröße n sein.

Melvin · Anmeldungsdatum: 24.05.2005 Beiträge: 5

Danke für die Erklärung, aber ich weiß immer noch nicht, wie ich es mit der Senke noch in die Aufgabe rein bringen soll.

Gruß
Melvin

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Dann mach dir erstmal klar, wie eine Senke definiert ist und wie sich das in der Matrix bemerkbar macht.