Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

7. Übung - abzugeben am 24. 11. 1998 in Ihrer Übungsgruppe

7.a Programm

MODULE Graphen;
  TYPE Graph*= RECORD ........ END;
    ................
  PROCEDURE(VAR g:Graph)Init*(v:LONGINT);
    (* v=Anzahl der Knoten im Graphen *)
  PROCEDURE(VAR g:Graph)CleanUp*();
    (* Freigabe des Graphen = Freigabe des dynamisch allokierten Speicherplatzes *)
  PROCEDURE(VAR g:Graph)SetEdge*(x,y:LONGINT);
   (* Kante x,y in den Graphen aufnehmen *)
  PROCEDURE(VAR g:Graph)NrComps*():LONGINT;
   (* Anzahl der Komponenten im Graph *)
  PROCEDURE(VAR g:Graph)PrComps*();
   (* Ausgabe der Komponenten=welche Knoten gehören zu welcher Komponente *)
  PROCEDURE(VAR g:Graph)PrAdj*();
   (* Ausgabe der Adjazenzmatrix für Test, Überprüfen etc. *)
END Graphen.

Anmerkungen:

• Zu verwalten/verarbeiten sind ungerichtete Graphen.
• Setzen Sie für die Speicherung der Adjazenzmatrizen einfach eine Adjazentmatrix ein.
• Besprechung der geforderten Funktionen erfolgt in der Übung
• Sicherheitsabfragen (HALT, ASSERT) nicht vergessen.

7.b Programm

  PROCEDURE(VAR g:Graph)IsBridge*(x,y:LONGINT):BOOLEAN;
    (* Ist die Kante x,y im Graphen eine Brücke? *)
  PROCEDURE(VAR g:Graph)IsTree*():BOOLEAN;
    (* Ist der Graph ein Baum? *)

Anmerkungen: a+b können gemeinsam abgegeben werden.

7.c Diskussion

• Was sind die Unterschiede zwischen Adjazenzmatrizen und Adjazenzlisten zur Darstellung von Graphen (Speicherplatz, Laufzeit, ......).
• Gibt es eine minimale Anzahl von Farben, mit denen man jeden Graphen färben kann? Wie hängt die minimale Farbenanzahl mit der Ordnung der Knoten eines Graphen zusammen?
• Liegt jede Kante auf einem Kreis? Liegt jede Brücke auf einem Kreis?
• Ist jeder zyklische Graph stark zusammenhängend?