0 Daumen
1,3k Aufrufe

Aufgabe:

Wende Breitensuche auf G mit Startknoten v1 an. Gib die entsprechende Baum an. Kommen zu einem Zeitpunkt mchrere Knoten in Frage, wähle den Knoten mit kleinstem Index.

20211204_214628.jpg

Text erkannt:

Abbildung 1: Abbildung des Graphen \( G \).



Problem/Ansatz:

Ich hab bei dieser Aufgabe 5  Lösungen und die sind alle falsch. Können Sie mir bitte zeigen, nach welcher Reinfolge ich vorgehen soll? Ich kann es leider nicht hinkriegen :(

Avatar von

Das ist jetzt meine 6. Lösung:

V1

V1, V7

V1, V7,V10

V1,v7,v10,v2

V1,v7,v10,v2,v6

V7,v10,v2,v6

V10,v2,v6

V2,v6

V2,v6,v3

V6,v3

V6,v3,v4

V6,v3,v4,v5

V3,v4,v5,v8

V3,v4,v5,v8,v9

V4,v5,v8,v9

V5,v8,v9

V8,v9

V9


1 Antwort

0 Daumen
 
Beste Antwort

https://www.geogebra.org/m/yvrrvbxp

ich versuche mich gerade an dem Thema

GraphOnline ist der Meinung

Durchquerungsreihenfolge:1 2 6 7 10 3 5 4 8 9

blob.png

meine App (Javascript) kommt, etwas ausführlicher, auch auf

BFS = {{"Removing node 1 from the queue..."},
{"Visiting node 2, setting its distance to 1 and adding it to the queue"},
{"Visiting node 6, setting its distance to 1 and adding it to the queue"},
{"Visiting node 7, setting its distance to 1 and adding it to the queue"},
{"Visiting node 10, setting its distance to 1 and adding it to the queue"},
{"Removing node 2 from the queue..."},
{"Visiting node 3, setting its distance to 2 and adding it to the queue"},
{"Removing node 6 from the queue..."},
{"Visiting node 5, setting its distance to 2 and adding it to the queue"},
{"Removing node 7 from the queue..."},
{"Removing node 10 from the queue..."},
{"Removing node 3 from the queue..."},
{"Visiting node 4, setting its distance to 3 and adding it to the queue"},
{"Visiting node 8, setting its distance to 3 and adding it to the queue"},
{"Removing node 5 from the queue..."},
{"Visiting node 9, setting its distance to 3 and adding it to the queue"},
{"Removing node 4 from the queue..."},
{"Removing node 8 from the queue..."},
{"Removing node 9 from the queue..."}}


was mir "richtiger" erscheint als Deine undurchsichtige Schreibe ;-).

Avatar von 21 k

Vielen lieben Dank für deine Mühe. Ich hab es nochmal probiert und hab dasselbe bekommen :) :)

Danke, nun, dann wären wir schon zu dritt :-)

Dann mach ich mal einen Haken proofed and tested an den Code...

Ich habe noch eine kurze Frage:

Kannst du mir bitte bitte sagen, wie ich bei dieser Aufgabe vorgehen kann? Ich bin seit 1 stunde drin geblieben :(


Sei H = (V, E) ein zusammenhängender Graph und TH (w) der Tiefensuchebaum von H, der entsteht, wenn Tiefensuche mit Startknoten w ∈ V ausgeführt wird. Wir nennen einen Knoten v ∈ V Artikulation, wenn H ohne v unzusammenhängend ist. Zeige: Gilt δ(ur) ≥ 2 in TH (w), dann ist w eine Artikulation.

Sorry, kenne die Terminologie nicht.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community