Aufgabe:
Ein gerichteter Graph G = (V, E) kann durch eine Adjazenzliste, eine Adjazenzmatrix oder eine
Inzidenzmatrix repräsentiert werden. Finden Sie für jede der Darstellungen mit Hilfe der Big-O-
Notation geeignete Abschätzungen für die folgenden Aufgaben:
Problem/Ansatz:
1.1 Überprüfung, ob für u, v ∈ V eine Kante von v nach u existiert
1.2 Bestimmung des Innengrades d- (v) für einen Knoten v ∈ V
1.3 Überprüfung, ob es einen Knoten v ∈ V mit Außengrad d+ (v) = 0 gibt