WorksheetsAL Tutorium 9
Total questions: 12
Worksheet time: 8mins
Welche Aussagen sind auf ungerichteten Graphen äquivalent zu: u ∈ N(v)
u,v∈V
{u, v}∈ E
Ein Pfad von u zu v existiert.
Ein Pfad von v zu u existiert.
Was ist in einfachen Graphen erlaubt?
Mehrfachkanten
Schleifen
Kreise
Pfade
Welche Knoten in ungerichteten Bäumen können als Wurzel gewählt werden?
Blätter
Innere Knoten
Knoten mit genau 2 Nachbarn
Knoten mit genau 3 Nachbarn
Welche Graphenrepräsentation braucht mehr Speicher?
Adjazenzliste
Adjazenzmatrix
Woran erkennt man ungerichtete Graphen in einer Adjazenzmatrix?
Matrix ist invertierbar
Matrix ist diagonal
Matrix ist symmetrisch
Matrix hat nur 0-Einträge
Was berechnet die BFS?
BFS Baum
Kürzeste Wege zwischen allen Knoten
Zusammenhangskomponente
Kürzester Weg zum Startknoten
Wann backtrackt man in einer DFS?
Wurzel gefunden
Alle Nachbarn eingefärbt
Gefärbten Knoten gefunden
Zu zufälligen Zeitpunkten
Welche Nummern gibt es in einer DFS?
FIN
ENT
FND
DFS
Welche Nummer beschreibt die Färbreihenfolge einer DFS
DFS
FIN
Welche Kanten gibt es in einem DFS Baum?
Vor
Baum
Rück
Quer
Wie erkennt man Querkanten anhand der DFS und FIN Nummer?
FIN: groß -> klein
DFS: klein -> groß
FIN: klein -> groß
DFS: klein -> groß
FIN: groß -> klein
DFS: groß -> klein
FIN: klein -> groß
DFS: groß -> klein
Wie erkennt man Vorkanten anhand der DFS und FIN Nummer?
FIN: groß -> klein
DFS: klein -> groß
FIN: klein -> groß
DFS: klein -> groß
FIN: groß -> klein
DFS: groß -> klein
FIN: klein -> groß
DFS: groß -> klein
