5.3.1. Algorithmen für grundlegende Eigenschaften

Lernziele

Algorithmen aus graph_misc.h
Einfach und zweifach zusammenhängende Graphen

In der Header-Datei graph_misc.h sind, wie der Name andeutet, verschiedene „kleinere“ Graphenalgorithmen deklariert, d. h. recht einfache Funktionen, die immer wieder in der täglichen Programmierarbeit mit der Klasse graph Verwendung finden. Die Funktionen Is_Planar() und Is_Planar_Map() daraus haben wir schon besprochen.

Einfach und zweifach zusammenhängende Graphen

Ein ungerichteter Graph heißt (einfach) zusammenhängend (connected), wenn jeder Knoten von jedem anderen aus über einen Pfad erreichbar ist. Der Graph aus Abbildung 5.17 ist einfach zusammenhängend. Die Funktion

bool Is_Connected(graph& G);

testet, ob ein Graph G (als ungerichteter Graph gesehen) zusammenhängend ist.

Abbildung 5.17. Ein einfach, aber nicht zweifach zusammenhängender Graph

Ein einfach, aber nicht zweifach zusammenhängender Graph

Der Graph ist zusammenhängend, weil jeder Knoten von jedem anderen aus erreichbar ist. Er ist nicht zweifach zusammenhängend: Der Knoten 2 ist ein Artikulationspunkt. Wird er entfernt, gibt es keinen Pfad mehr von 1 nach 5; der Graph ist dann nicht mehr zusammenhängend.

Jeder Graph kann durch einen Aufruf von

list<edge> Make_Connected(graph& G);

in einen zusammenhängenden Graphen verwandelt werden. Diese Funktion liefert eine Liste der Kanten zurück, die eingefügt werden mussten, um den Graphen zusammenhängend zu machen. Es wird immer eine minimale Anzahl von Kanten eingefügt.

Ein Artikulationspunkt (articulation point, cut vertex) in einem ungerichteten, zusammenhängenden Graphen ist ein Knoten, durch dessen Entfernung der Graph in mehrere Komponenten zerfällt, also unzusammenhängend wird; er ist sozusagen eine Art „Schwachstelle“, wenn man den Graphen als Netzwerk betrachtet.

Ein ungerichteter, zusammenhängender Graph heißt zweifach zusammenhängend (biconnected), wenn er keinen Artikulationspunkt besitzt. Das hat zur Folge, dass jeder Knoten von jedem anderen aus über mindestens zwei disjunkte Pfade erreichbar ist; daher die Bezeichnung „zweifach zusammenhängend“. Der Graph aus Abbildung 5.17 ist nicht zweifach zusammenhängend. Die Funktion

bool Is_Biconnected(graph& G, node& ap);

testet, ob ein Graph G (als ungerichteter Graph gesehen) zweifach zusammenhängend ist. Ist er das nicht, liefert sie in ap einen Artikulationspunkt zurück.

Die Funktion

list<edge> Make_Biconnected(graph& G);

kommt der Bush-Administration sehr gelegen, da sie das Stromnetz der USA, das einen Graphen darstellt, sicherer gegen Terroristen macht: Sie fügt eine minimale Anzahl von Kanten ein, so dass es keinen Artikulationspunkt mehr gibt, und liefert die eingefügten Kanten in einer Liste zurück.

Graphen kopieren

Häufig stellt sich das Problem, eine isomorphe Kopie H eines Graphen G anzulegen und auf dieser Kopie (statt auf dem ursprünglichen Graphen) weiterzuarbeiten. „Isomorph“ bedeutet dabei, dass jedem Knoten v von G genau ein Knoten v' von H entspricht, und dass jeder ursprünglichen Kante (v,w) von G genau eine Kante (v',w') von H entspricht (wobei v' der dem Knoten v, und w' der dem Knoten w entsprechende Konten ist).

Die Funktion

void CopyGraph(graph& H, graph& G);

erzeugt eine isomorphe Kopie H des graph G.

Oftmals ist darüber hinaus notwendig, die Beziehungen zwischen den Knoten und Kanten von G und H zu kennen, weil man von einem Knoten bzw. einer Kante von G zum entsprechenden Knoten bzw. zur entsprechenden Kante von H gelangen will (oder umgekehrt). Ein Aufruf von

void CopyGraph(GRAPH<node, edge>& H, graph& G);

mit einem parametrisierten GRAPH, dessen Knoten- bzw. Kanteninformationen vom Typ node bzw. edge sind, speichert zu jedem Knoten und jeder Kante von H zusätzlich ein Item, das auf den ursprünglichen Knoten bzw. die ursprüngliche Kante von G verweist. Somit kann dann, ausgehend von einem Knoten v bzw. einer Kante e von H, durch

node v_in_G = H[v];
edge e_in_G = H[e];

auf den entsprechenden Knoten bzw. die entsprechende Kante von G zugegriffen werden.

Um dagegen umgekehrt von den Knoten von G zu den entsprechenden Knoten von H zu gelangen, muss explizit eine Kopie von G erzeugt werden, und die Beziehungen müssen während des Erzeugens von H z. B. in einem node_array gespeichert werden:

graph H;
node_array<node> copy_in_H(G);
// copy all nodes of G
node v;
forall_nodes(v, G) 
  copy_in_H[v] = H.new_node(v);
// copy all edges of G
edge e;
forall_edges(e, G)
  H.new_edge(copy_in_H[G.source(e)], copy_in_H[G.target(e)]);

Danach kann, ausgehend von einem Knoten v von G, durch

node v_in_H = copy_in_H[v];

auf den entsprechenden Knoten von H zugegriffen werden.

Weitere Funktionen

In graph_misc.h finden sich weitere Funktionen, die die tägliche Arbeit mit graph erleichtern. Hier eine Auswahl davon:

Is_Simple() testet, ob ein Graph einfach ist, d. h., ob er keine Multikanten besitzt.

Is_Acyclic() testet, ob ein Graph zyklusfrei ist.

Is_Bipartite() testet, ob ein Graph bipartit ist: Ein Graph heißt bipartit, wenn die Knoten so in zwei Teilmengen A und B zerfallen, dass für jede Kante der Quell- und der Zielknoten in verschiedenen Teilmengen liegen. Siehe hierzu auch den K3,3 aus Abbildung 5.10.

Delete_Loops() entfernt alle Selbstschleifen und liefert eine Liste der Knoten zurück, die vormals eine Selbstschleife besaßen.

Weitere Informationen

Die restlichen Funktionen aus graph_misc.h finden sich auf der entsprechenden Manualseite.

Übungen

Übung 61.

Wie viele und welche Kanten müssen in Abbildung 5.17 eingefügt werden, um den Graphen zweifach zusammenhängend zu machen? Lassen Sie die Kanten von Make_Biconnected() einfügen und visualisieren Sie das Ergebnis mit einem GraphWin.