AL Tutorium 9

• 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