Begründe kurz, warum die Laufzeit eingehalten wird.

Question

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) := max_w∈v  (dist (v, w).

• Der Durchnesser eines Graphen G entspricht dem Maximum über die Exzentrizitäten, d.h. diam(G):= max_v∈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!

Answer 1

Hm,

ich steck nicht so dick drin im Thema, aber sollte eine BFS nicht ausreichen.

Ausführlich mitgeschrieben Start bei v12

Removing node 12 from the queue ...,
Visiting node 3, setting its distance to 1 and adding it to the queue,
Visiting node 11, setting its distance to 1 and adding it to the queue,
Removing node 3 from the queue ...,
Visiting node 1, setting its distance to 2 and adding it to the queue,
Visiting node 2, setting its distance to 2 and adding it to the queue,
Visiting node 4, setting its distance to 2 and adding it to the queue,
Removing node 11 from the queue ...,
Removing node 1 from the queue ...,
Visiting node 5, setting its distance to 3 and adding it to the queue,
Visiting node 6, setting its distance to 3 and adding it to the queue,
Removing node 2 from the queue ...,
Removing node 4 from the queue ...,
Visiting node 9, setting its distance to 3 and adding it to the queue,
Visiting node 10, setting its distance to 3 and adding it to the queue,
Removing node 5 from the queue ...,
Removing node 6 from the queue ...,
Visiting node 7, setting its distance to 4 and adding it to the queue,
Visiting node 8, setting its distance to 4 and adding it to the queue,
Removing node 9 from the queue ...,
Removing node 10 from the queue ...,
Removing node 7 from the queue ...,
Removing node 8 from the queue ...

ergibt

BFSdist = {{12}, 2, 2, 1, 2, 3, 3, 4, 4, 3, 3, 1, 0}

Taugt das als Einstieg?

Comments

Auf jeden Fall. Dankeschön

---

Aber der Pseudocode darf doch nur maximal 10 Zeilen lang sein oder

---

Na, dann ist

BFS(j), j=0..n

eine Zeile...

---

Verstehe ich jetzt nicht ganz.

Und sollen die Elemente zum Schluss in BFS die Exzentrizitäten anzeigen?