Aufgabe:
Wie jedes Jahr verläuft sich Rudolf im Wald hinter dem Haus des Weiluachtsmanns (siehe Abbildung 1). Nun sucht er einen Weg zurück und entscheidet dies mit Hilfe einer Tiefensuchen zu tun.
(a) Stellen Sie den Wald, in dem sich Rudolf befindet, als Graph G dar. Nutzeu Sie dazu die markierten Kreuzumgen als Knoten \( (V=\{1,2, \ldots, 14, R, H\}) \) und verbinden Sie zwei Knoten, wem es einen direkten Weg zwischen zwei Kreuzungen gibt, (d.h. es liegt keine dritte Kreuzung daxwischen).
(b) Führen Sie von Rudolfs Position aus die Tiefensuche auf dem Graph \( G \) aus. Kann eine Kreuzung aus mehreren gewählt werdea, dann wähle die Kreuzung mit der gröstea Markierung. Dabei sel \( 14<R< \) \( \mathrm{H} . \)
Nun ist Rudolf endlich wieder zurick und möchte sicher gehen, dass er sich nie wieder in diesem Wald verläuft, Darum zeichnet er sich eine Karte, die einen Weg vam Haus zu jeder Kreuzung im Wald enthält.
(c) Helfen Sie Rudolf ein Karte zuzeichnen, die möglichst kurze Rūckwege enthält. Bestimmen Sie dazu deu Breitensuchebaum \( T \), der am Haus beginnt. Notieren Sie an jedem Knoten, in welchen Schritt der Knoten in den Baum aufgenommen wurde.
(d) Bestimmen Sie die Adjazeuzmatrix und Adjazenzlisten für den induzierten Teilgraphen \( G\left[V^{\prime} \mid\right. \) mit der Knotenmenge \( V^{t}=\{1,2, \ldots, 10\} \)
