0 Daumen
912 Aufrufe

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.


20211218_085449.jpg

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!

Avatar von

1 Antwort

0 Daumen

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?

Avatar von

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?

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
0 Antworten
0 Daumen
0 Antworten

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community