Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03505.jsonl.gz/468

Alle Ebenen sind vollständig gefüllt ausser evtl. die letzte Ebene, wobei nur die Blätter rechts fehlen dürfen.
Erkläre "perfekter Binärbaum"
Alle internen Knoten haben genau 2 Kinder und alle Blätter sind auf der gleichen Ebene
Start bei Knoten 0 - Preorderreihenfolge
043125
Markieren Sie in den folgenden Graphen alle Kanten des induzierten Suchbaums einer Breitensuche die von Knoten 0 ausgeht.
siehe Bild
Sei v ein Knoten eines Graphen G. Stimmt es, dass eine von v ausgehende Tiefensuche in G genau die gleichen Knoten besucht wie eine von v ausgehende Breitensuche in G? Nur eine Antwort
Ja, immer
Nur bei gerichteten Graphen
Nur bei ungerichteten Graphen
Weder bei gerichteten noch bei ungerichteten Graphen
Wir haben in dem Algorithmus für kürzeste Pfade eine Breitensuche verwendet und ihn auf gerichtete Graphen ohne Kantengewichte angewendet. Ist das alles so notwendig? Welche der folgenden Aussagen sind wahr? (Bei gewichteten Kanten ist ein kürzester Pfad, ein Pfad, der eine minimale Summe der Kantengewichte aufweist.)
Das Verfahren berechnet auch kürzeste Pfade für gerichtete, gewichtete Graphen.
Man kann genauso gut den induzierten Suchbaum einer Tiefensuche verwenden.
Das Verfahren berechnet auch kürzeste Pfade für ungerichtete, ungewichtete Graphen.
Das Verfahren berechnet auch kürzeste Pfade für ungerichtete, gewichtete Graphen.
Bei der Berechnung einer topologischen Sortierung berechnen wir eine Folge P_1,..., P_k, wobei jedes P_i die umgekehrte Postorderreihenfolge der i-ten Tiefensuche darstellt. Die Aneinanderreihung Pk, ..., P_1 ergibt dann eine topologische Sortierung. Ich schlage hiermit ein alternatives Vorgehen vor: führe die gleiche Folge von Tiefensuchen durch, berechne aber in der i-ten Suche die (nicht umgekehrte) Postorderreihenfolge R_i. Reiht man diese in der Reihenfolge R_1,...,R_k aneinander und dreht das Gesamtergebnis um, erhält man ebenfalls eine topologische Sortierung des Graphen. Stimmt das?
Ja
Nein
Könnte man im Konstruktor von ConnectedComponents statt der Tiefensuche auch eine Breitensuche verwenden?
Ja
Nein
Kann man die umgekehrte Postorderreihenfolge in Kosarajus Algorithmus auch mit einer Breitensuche bestimmen?
Nein
Ja
Kann man im zweiten Teil von Kosarajus Algorithmus (die Explorationen im Originalgraphen) auch eine Breitensuche verwenden?
Selbstverständlich, es geht schliesslich nur darum, welche Knoten erreichbar sind.
Nein, das ergibt keine starken Zusammenhangskomponenten.
Welche der folgenden Aussagen über Äquivalenzklassen sind wahr?
Ist a in [c] und b in [c], so ist a in [b].
Ist a in [b], so ist [a] = [b].
Ist a in [c] und b in [a], so gilt nicht immer, dass b~c ist.
Ist a in [b], so ist auch [b] in [a].
Ist a in [c] und b in [c], so ist a in [b]
Ist a in [b], so ist [a] = [b]
Ist a in [c] und b in [a], so gilt nicht immer, dass b~c ist