Prof. Dr. A. Goerdt TU Chemnitz
Julian Pape-Lange Wintersemester 2021/2022
13.10.2021
Theoretische Informatik I
1. Übung
Abgabe: Lösen Sie Aufgaben 1 und 2 handschriftlich. Ihre Lösungen geben Sie bitte
entweder
• bis zum 21.10.2021 um 13:00 Uhr per Mail
an
mit Betreff: TI1 Hausaufgaben oder
• bis zum 21.10.2021 um 13:00 Uhr im Briefkasten der Professur Theoretische Infor-
matik (vor Raum A10.266.4)
ab.
1. Aufgabe: ((1+1+3)P)
Gegeben sei folgender gerichteter Graph G.
1 - 2 3
?
?
?
4 5 6
(a) Stellen Sie G durch Adjazenzlisten dar.
(b) Stellen Sie G durch eine Adjazenzmatrix dar.
(c) Zeigen Sie mit dem Algorithmus aus der Vorlesung, dass G kreisfrei ist und geben
Sie zu jedem Knoten an, in welcher Löschung er entfernt wird. Geben Sie auch eine
topologische Sortierung der Knoten an.
2. Aufgabe: ((3+2)P)
(a) Geben Sie einen Algorithmus an, der die Anzahl der Kreise mit Länge 2 in einem
gegebenen gerichteten Graphen ermittelt.
(b) Geben Sie eine Abschätzung für die Laufzeit Ihres Algorithmus an.
3. Aufgabe: Programmieren Sie eine (Warte-)Schlange (FIFO-Speicher).
4. Aufgabe: Für viele Algorithmen wollen wir, dass die Knoten von Graphen die Zahlen
von 1 bis |V | sind. In der Praxis kann es aber passieren, dass die Knoten andere Namen
haben.
Erklären Sie, wie wir Graphen mit beliebigen Knotennamen in Graphen mit den Knoten
von 1 bis |V | umwandeln können.
1
,
,
,
Julian Pape-Lange Wintersemester 2021/2022
13.10.2021
Theoretische Informatik I
1. Übung
Abgabe: Lösen Sie Aufgaben 1 und 2 handschriftlich. Ihre Lösungen geben Sie bitte
entweder
• bis zum 21.10.2021 um 13:00 Uhr per Mail
an
mit Betreff: TI1 Hausaufgaben oder
• bis zum 21.10.2021 um 13:00 Uhr im Briefkasten der Professur Theoretische Infor-
matik (vor Raum A10.266.4)
ab.
1. Aufgabe: ((1+1+3)P)
Gegeben sei folgender gerichteter Graph G.
1 - 2 3
?
?
?
4 5 6
(a) Stellen Sie G durch Adjazenzlisten dar.
(b) Stellen Sie G durch eine Adjazenzmatrix dar.
(c) Zeigen Sie mit dem Algorithmus aus der Vorlesung, dass G kreisfrei ist und geben
Sie zu jedem Knoten an, in welcher Löschung er entfernt wird. Geben Sie auch eine
topologische Sortierung der Knoten an.
2. Aufgabe: ((3+2)P)
(a) Geben Sie einen Algorithmus an, der die Anzahl der Kreise mit Länge 2 in einem
gegebenen gerichteten Graphen ermittelt.
(b) Geben Sie eine Abschätzung für die Laufzeit Ihres Algorithmus an.
3. Aufgabe: Programmieren Sie eine (Warte-)Schlange (FIFO-Speicher).
4. Aufgabe: Für viele Algorithmen wollen wir, dass die Knoten von Graphen die Zahlen
von 1 bis |V | sind. In der Praxis kann es aber passieren, dass die Knoten andere Namen
haben.
Erklären Sie, wie wir Graphen mit beliebigen Knotennamen in Graphen mit den Knoten
von 1 bis |V | umwandeln können.
1
,
,
,
