Aufgabe:
Distanzen spielen in der Graphentheorie eine sehr große Rolle. In dieser Aufgabe wollen wir einen Algorithmus entwerfen, der den Durchmesser eines Graphen bestimmt, d.h. die maximale kürzeste Distanz zwischen zwei Knoten. Dazu definieren wir folgendes.
• Die Distanz dist(v, w) zwischen zwei Knoten v, w ∈ V im einem Graphen G ist die Anzahl an Kanten auf einem kürzesten Weg zwischen v und w in G. Gibt es keinen Weg zwischen v und w, so ist dist (v, w) = ∞.
• Die Erzentrizität ex(v) eines Knotens v E V bezeichnet die Länge eines kürzesten Pfades zu dem am weitesten entfernten Knoten, d.h. ex(v) := maxw∈v (dist (v, w).
• Der Durchnesser eines Graphen G entspricht dem Maximum über die Exzentrizitäten, d.h. diam(G):= maxv∈V (ex(v)).
Entwirf einen Algorithmus EXZENTRIZITÄT in Pseudocode (maximal 10 Zeilen') mit Laufzeit O(n + m), der für einen gegebenen Graphen G und Knoten v ∈ V den Wert ex(v) bestimmt. Begründe kurz, warum die Laufzeit eingehalten wird.
Text erkannt:
Abbildung 1: Darstellung des Graphen \( H \).
Problem/Ansatz:
Hallo! Ich muss folgende Algorithmen und Datenstruktur Aufgabe bekommen, aber habe Probleme Sie zu lösen. Ich hoffe es kann mir jemand helfen!
