Algorithmen und Datenstrukturen 2 WS 1999/2000

2. Übung - abzugeben am 19. 10. 1999 in Ihrer Übungsgruppe

2.a.1) Graphentheorie

Gegeben seien folgende beiden Graphen:

Graph 1		Graph 2

• Bestimmen Sie den Grad jedes Knotens (d, d+, d-) von Graph 1.
• Überlegen Sie, ob diese beiden Graphen isomorph sind. Wenn ja, so zeigen Sie die Isomorphie durch die entsprechende Abbildungsvorschrift.
• Sind die beiden Graphen ident?
• Ist Graph 1 stark zusammenhängend?
• Ist Graph 1 schwach zusammenhängend?
• Ist Graph 2 stark zusammenhängend?
• Ist Graph 2 schwach zusammenhängend?

2.a.2) Graphentheorie

Gegeben Sie folgender Graph:

Beantworten Sie dazu kurz folgende Fragen:

• Ist der Graph zusammenhängend bzw. aus wie vielen Komponenten besteht er?
• Welche Kanten im Graph sind Brücken??
• Sind folgende Graphen Bäume und wenn ja, welcher Ordnung:
  a.) Der gesamte Graph?
  b.) Der Graph aus den Knoten 8 und 9 (samt zugehörigen Kanten)?
  c.) Der Graph aus den Knoten 0 bis 7 (samt zugehörigen Kanten)?
  d.) analog c, aber ohne Kante [4,5]?

2.b.1) Maximales Matching

Die Wohngemeinschaft "Algorithmen und Datenstrukturen" hat eine neue Wohnung mit 5 Zimmern angemietet. Bei der Aufteilung der 5 Zimmer auf die 5 KollegInnen ergeben sich allerdings gewisse Probleme. Hans Hash, ein Mitglied dieser Wohngemeinschaft, bietet einen Lösungsvorschlag an:
Jedes Mitglied soll die Attraktivität jedes Zimmers durch eine Zahl zwischen 0 ("Haß") und 20 ("Liebe") bewerten. Die Zuordnung wird dann so vorgenommen, daß die Summe der Attraktivitätsgrade maximal wird.
Die Wohngemeinschaft stimmt dieser Vorgangsweise ("Algorithmus") zu.

Es entsteht folgende Bewertung:

	Zi. 1	Zi. 2	Zi. 3	Zi. 4	Zi. 5
Hans HASH	8	16	20	12	0
Gaby GRAPH	12	4	16	20	8
Bernhard BAYER	20	8	0	4	12
Gerda GREEDY	0	16	12	20	8
KOMPLEXLER	16	0	8	20	4

Zeigen Sie, wie Sie dieses Beispiel (welches aus einer Übung zur LVA Operation Research I stammt) als maximales Matching interpretieren können.
Obgleich wir in der LVA (bis jetzt) noch keinen Algorithmus für das maximale Matching besprochen haben, versuchen Sie bitte, die korrekte Lösung = Zimmerzuordnung intuitiv festzustellen.

2.b.2) Fertigungsplanung und Graphen

Gegeben sei folgendes Problem aus der Fertigungsplanung:

1. Einholen von Angeboten, Vergleich, Wirtschaftlichkeitsrechnung, Entscheidung, Bestellung. (25 Tage)
2. Demontage der alten Anlage (8 Tage)
3. Entfernung der alten Maschinenfundamente (5 Tage, Vorgänger 2)
4. Konstruktion neues Maschinenfundament (9 Tage, Vorgänger 1)
5. Lieferzeit für die neue Anlage (21 Tage, Vorgänger 1)
6. Errichten neues Maschinenfundament (9 Tage, Vorgänger 3 und 4)
7. Installation neue Anlage (6 Tage, Vorgänger 5 und 6)
8. Personalausbildung (15 Tage, Vorgänger 1)
9. Elektrische Anschlüsse (2 Tage, Vorgänger 7)
10. Probelauf (1 Tag, Vorgänger 8 und 9)
11. Abnahme, Feier mit Sekt und Kaviar, Inbetriebnahme (2 Tage inkl. "Kater", Vorgänger 10)