Graphen

In diesem Kapitel beschäftigen wir uns mit Graphen.

Definition

Ein (gerichteter) Graph G is ein Tupel G=(V,E) mit V als der endlichen Menge der Knoten von G und $E\subseteq V\cdot V$ als der endlichen Menge der Kanten von G. Um ein Graph als Datenstruktur zu nutzen, können sowohl Knoten als auch Kanten weitere Attribute beinhalten. Ein gerichteter Graph mit den Werten F ist ein Tupel $F=(V,E,\alpha ,\beta )$ mit (V,E) als Graph, $\alpha (v)$ als Wert des Knotens $v\in V$ und $\beta (e)$ als Wert der Kante $e\in E$ .

Beispiel

G=(V,E)

V={1,2,3,4,5}

E={(1,2),(3,4),(5,1),(2,5),(5,4)}

F=(V,E, $\alpha ,\beta$ )

V={1,2,3,4,5}

E={(1,2),(3,4),(5,1),(2,5),(5,4)}

$\alpha$ (1)="Anna", $\alpha$ (2)="Carl",..., $\beta$ (1,2)="kennt",...

Graphen als Datenstruktur

Knoten und Kanten können auch komplexere Werte enthalten, wie beispielsweise mehrere Werte oder Arrays. Der Einfachheit halber identifizieren wir(in diesem Kurs) den Wert eines Knotens mit dem Knoten selber und nutzen meist natürliche Zahlen als Knotenbezeichner:

$V\subseteq \mathrm {N}$
$\alpha (v)$ für alle $v\in V$

Listen und Bäume sind Spezialfälle von Graphen.

Anwendungen

Graphen werden für Verbindungsnetzwerke wie Bahnnetze, Flugverbindungen oder Strassenkarten benutzt. Aber auch für Verweise wie WWW, Literaturverweise, Wikipedia, symbolische Links und vieles mehr. Auch bei technischen Modellen kommen Graphen zum Einsatz, beispielsweise bei Platinen-Layout, finite Elemente und Computergrafik. In Sozialen Netzwerken und Argumentationsgraphen kommen Graphen auch zum Einsatz.

Atomare Operationen auf Graphen

Zu dem Operationen zählen lesen mit

Adj(x,y): Sind Knoten x und y benachbart?

Adj(1,2)=true, Adj(4,5)=false

Suc(x): Menge der Nachfolger von x

Suc(1)={2}, Suc(5)={1,4}

Bei Graphen mit expliziten Werten: Wert eines Knotens/Kante lesen

und schreiben mit

Add(x)/Del(x): Knoten x hinzufügen/löschen
Add(x,y)/Del(x,y): Kante (x,y) hinzufügen/löschen

Typische Problemstellungen

Zu den typischen Problemstellungen zählen die Traversierung, die Findung des kürzesten Wegs, die Graphfärbung, das Flussproblem, die Verbundheit und das Graphclustering (Community Detection).

Graphen in Java

In Java gibt es keine hauseigene Graphenimplementierung, allerdings gibt es diverse Pakete für verschiedene Anwendungen.

Jung (http://jung.sourceforge.net)

Graph<Integer, String> g = new SparseMultigraph<Integer, String>(); 
g.addVertex((Integer)1); 
g.addVertex((Integer)2); 
g.addEdge("Edge1", 1, 2);

Neo4j (http://www.neo4j.org)

GraphDatabaseService= new 
GraphDatabaseFactory().newEmbeddedDatabase(“PATH”); 
Transaction tx = graphDb.beginTx(); 
try{ 
Node firstNode = graphDb.createNode(); 
Node secondNode = graphDb.createNode(); 
Relationship relationship = firstNode.createRelationshipTo(secondNode,
… ); 
tx.success(); 
}finally{ 
tx.finish(); 
}

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 16 zu finden.