Info B: Woche 11

Folgende Abbildung ist:

• Baum und Wald

• Baum und kein Wald

• Kein Baum und kein Wald

• Wald und kein Baum

Sei G ein Baum. Dann gilt:

• Je 2 Knoten sind durch genau einen Weg verbunden

• G ist zusammenhängend und |E| = |V|

• G ist nicht zusammenhängend und |E| = |V| - 1

• G ist kreisfrei, zusammenhängend und ungerichtet

Ist der folgende Graph planar?

• Ja

• Nein

Sei G ein Graph und s ein Startknoten. Wie heißt das Verfahren, bei dem man erst alle Nachbarn des Startknoten s besucht und dann alle noch nicht besuchten der Nachbarn?

• Breitensuche

• Tiefensuche

• Dijkstra

Sei G = (V, E) ungerichteter, einfacher Graph mit der Wurzel v0.

Welche sind die DFS-Bäume von G?

• 
• 
• 
• 

Ist dieser gerichtete Graph ein DAG?

• Ja

• Nein

Welche algorithmische Frage wurde hier gestellt?

• Hamiltonpfad/Hamiltonkreis

• Eulerpfad/Eulertour

• Spannbaum

• Baum

Sei G und T ungerichtete, einfache Graphen. Welche Aussagen sind richtig?

• G ist ein Wald

• T ist ein Wald

• Es gilt G = (V, E) und

  T = (V, E') mit

  E' Teilmenge von E

• T ist ein Spannbaum von G