Ja, das wird eine Heimarbeit sein (ich bin selbst lernend, nicht für die Universität), aber ich frage nicht nach einer Lösung. Stattdessen hoffe ich, die Frage selbst zu klären.
In CLRS 3. Ausgabe , Seite 593, Akzise 22.1-5,
Das Quadrat eines gerichteten Graphen G = (V, E) ist der Graph G ^ 2 = (V, E ^ 2) so dass (u, v) ∈ E ^ 2 genau dann, wenn G enthält ein Pfad mit höchstens zwei Kanten zwischen u und v . Beschreiben Sie effiziente Algorithmen für die Berechnung von G2 aus G für die Adjazenzlisten- und Adjazenzmatrixdarstellungen von G. Analysieren Sie die Laufzeiten Ihrer Algorithmen.
Jedoch in CLRS 2. Ausgabe (Ich kann den Buchverweis nicht mehr finden), Seite 530, die gleiche Akzise, aber mit etwas anderer Beschreibung:
Das Quadrat eines gerichteten Graphen G = (V, E) ist der Graph G ^ 2 = (V, E ^ 2) so dass (u, w) ∈ E ^ 2 genau dann, wenn für einige v ∈ V , sowohl (u, v) ∈ E als auch (v, w) ∈ E. Das heißt, G ^ 2 enthält eine Kante zwischen u und w, wenn G einen Pfad mit genau zwei Kanten enthält zwischen dir und w . Beschreiben Sie effiziente Algorithmen für die Berechnung von G ^ 2 aus G für die Adjazenzlisten- und Adjazenzmatrix-Darstellungen von G. Analysieren Sie die Laufzeiten Ihrer Algorithmen.
Für die alte Verbrauchsteuer mit "genau zwei Kanten" kann ich sie verstehen und lösen. Zum Beispiel, für die Adjazenz-Liste, ich mache einfach v- & gt; Nachbar- & gt; Nachbar. Nachbar, dann füge (v, Nachbar .. Nachbar) dem neuen E ^ 2 hinzu.
Aber für die neue Verbrauchsteuer mit "höchstens zwei Rändern" bin ich verwirrt.
Was bedeutet "wenn und nur wenn G einen Pfad mit höchstens zwei Kanten zwischen u und v enthält"?
Da eine Kante die Bedingung "höchstens zwei Kanten" erfüllen kann, sollte u und v nur einen Pfad enthalten, der nur eine Kante enthält, soll ich (u, v) zu E ^ 2 hinzufügen?
Was ist, wenn u und v einen Pfad mit 2 Kanten hat, aber auch einen anderen Pfad mit 3 Kanten, kann ich (u, v) zu E ^ 2 hinzufügen?
Ja, genau das ist es. E^2 sollte (u,v) enthalten, wenn E (u,v) enthält oder w in V , so dass E sowohl (u,w) als auch (w,v) enthält.
Mit anderen Worten, E^2 gemäß der neuen Definition ist die Vereinigung von E und E^2 gemäß der alten Definition.
In Bezug auf Ihre letzte Frage: Es spielt keine Rolle, welche anderen Pfade zwischen u und v existieren (wenn sie es tun). Also, wenn es zwei Pfade zwischen u und v gibt, eins mit 2 Kanten und eins mit 3 Kanten, dann sollte (u,v) in E^2 sein (entsprechend beiden Definitionen).
Das Quadrat eines Graphen G, G ^ 2, definiert durch jene Eckpunkte V ', für die d (u, v) & lt; = 2 und die eges G' von G ^ 2 sind alle jene Kanten von G, die sowohl die Endknoten von V '
Tags und Links algorithm data-structures graph clrs