Inhalt

• Grundlagen
• Laden von Multigraphen
• Minimal Spannender Baum
• Steiner Minimaler Baum
• Hamiltonkreis
• Matchings
• Sonstiges (Vorträge, Hilfssätze, Aktuelles)

Grundlagen

Ein Graph G = (V, E) besteht aus einer Menge V von sogenannten Knoten und einer Menge E von sogenannten Kanten, die Teilmenge von V x V ist. Wir bezeichen mit |G| = |V| = n die Anzahl der Knoten und mit |E| = m die Anzahl der Kanten. Ist die Kante e = [x, y] in E enthalten, so sind ihre Endknoten x und y adjazent, bzw. benachbart oder verbunden, hingegen ist x mit e inzident. N(v) bezeichnet alle Knoten, die mit v benachbart sind. Mit dem Grad(v) oder auch d(v) bezeichnen wir die Größe |N(v)| der Nachbarschaft von v. Der kleinste Grad, der von einem Knoten in einem Graphen angenommen wird, heißt Minimalgrad, entsprechend der größte Grad Maximalgrad. Haben alle Knoten des Graphen k den gleichen Grad, so ist der Graph k-regulär. Ordnen wir den Kanten Zahlen zu, so erhalten wir Gewichtete Graphen, die Gewichte werden auch Längen genannt. In ungewichteten Graphen setzen wir für jede Kante das Gewicht 1 voraus.

Graphen werden visualisiert, indem jeder Knoten als ein Punkt dargestellt wird und jede Kante als ein Strich zwischen ihren inzidenten Knoten repräsentiert wird. Ist eine Kante e = [x, y] mehrmals in E enthalten, also y mehrmals in der Nachbarschaft von x enthalten, so wird der Graph als Multigraph bezeichnet. Als Teilgraph G' = (V', E') von G = (V, E) bezeichnen wir einen Graphen, wenn V' Teilmenge von V ist und E' nur Kanten aus E enthält, deren beide Endknoten in V' liegen. Enthält ein Graph keine Kanten, so ist er leer und seine Knoten bilden eine stabile Menge. Ist hingegen E = V x V, also jeder Knoten mit jedem anderen verbunden, so ist der Graph vollständig und wird als Clique K_n bezeichnet. Die Cliquenzahl Omega eines Graphen gibt an, dass die Clique K_Omega der größte vollständige Teilgraph von G ist. Das Komplement eines Graphen G enthält alle Knoten des Graphen G, jedoch genau die Kanten aus V x V, die nicht in G enthalten sind. Die Cliquenzahl des Komplements ist die Stabilitätszahl Alpha von G, dh. die maximale stabile Menge von G enthält Alpha viele Knoten, so dass keine zwei dieser Knoten in G benachbart sind.

Eine Folge (v_i)_i von Knoten, wobei v_{i + 1} ein Nachbar von v_i ist, nennt man einen Weg durch den Graphen. Wird dabei kein Knoten doppelt benutzt, bezeichnen wir den Weg als Pfad. Ein Weg, bei dem der letzte Knoten dem ersten entspricht, nennen wir ein Zykel. Sind sonst alle Knoten verschieden auf dem Zykel, so haben wir einen Kreis. Existiert zwischen je zwei Knoten des Graphen ein Pfad, so nennen wir ihn zusammenhängend. Das Gewicht/Länge eines Graphen ist die Summe der Gewichte seiner Kanten. Entsprechend ist die Länge eines Pfades die Summe der Gewichte der Kanten des Pfades. Gibt es zwischen 2 Knoten x und y einen Pfad, so gibt es auch einen kürzesten Pfad, der die Länge minimiert. Dessen Länge wird als Abstand dist(x, y) bezeichnet. Existiert kein Pfad zwischen x und y, so ist ihr Abstand unendlich. Enthält ein Graph keine Kreise, so wird er Wald genannt. Ist er zudem noch zusammenhängend, so nennen wir ihn Baum. Ordnen wir jedem Knoten eine ganze Zahl zu, so sprechen wir von einer Knotenfärbung. Die Färbung ist korrekt, falls keine zwei benachbarten Knoten die gleiche Farbe aufweisen. Kann G mit k Farben korrekt gefärbt werden, so heißt er k-färbbar. Die chromatische Zahl Chi eines Graphen ist die kleinste Zahl, für die eine k-Färbung des Graphen existiert.

Laden von Multigraphen

Problem

Der Graph liegt als Text-Datei vor, in dem pro Kante ein Eintrag [Kante-Nr, Knoten1-Nr, Knoten2-Nr] vorhanden ist. Die Kantennummer identifiziert die Kante und die beiden Knoten sind die inzidenten Knoten dieser Kante. Bei Multigraphen erhält jede Kante eine andere Nummer, auch wenn sie die gleichen Endknoten haben. Entsprechend enthält die Datei auch mehrere Einträge, die auf die gleichen Knotenpaare verweisen. In der Implementation soll der Graph jedoch lediglich eine Kante pro Knotenpaar mit dem Vermerk der Vielfachheit enthalten, wobei Vielfachheit die Anzahl wirklicher Kanten zwischen diesen Knoten im Multigraphen meint.

Das Laden von großen Graphen soll schnell und platzsparend geschehen. Ist m die Anzahl der Kanten incl. Multikanten, m' hingegen die Anzahl der Kanten ohne Dublikate, so lädt der Load-Multigraphs-Algorithmus Multigraphen mit n Knoten und m Kanten und erzeugt einen Graphen auf n Knoten und m' Kanten, in dem gleiche Multikanten zu einer Kante kontrahiert werden, jedoch die Vielfachheit dieser Kante vermerkt ist. Bemerkenswert ist dabei, dass der Algorithmus eine in m lineare Laufzeit von O(n + m) hat, jedoch nur einen in m' linearen Platzbedarf von O(n + m') hat.

DOWNLOAD: LoadingMultigraphs.ps (??? kb) zur Zeit leider nicht verfügbar

Minimal-Spannender-Baum

Problem 

Gesucht wird ein Minimal Spannende Baum (MST) eines Graphen. Das ist ein Teilgraph, der alle Knoten enthält und zusammenhängend ist. Zudem soll seine Länge minimal sein. Dies ist erzwungenerweise ein Baum. Das Problem ist polynomiell lösbar mit Algorithmen von Kruskal oder Prim. Der erste benötigt eine Laufzeit von O(m log n), der zweite hingegen O(n log n) mithilfe von Fibonacci-Heaps.

Updating Minimal Spanning Trees

Steiner-Minimaler-Baum

Problem 

Lower Bound And Implementation Of Relative Greedy Algorithm

Hamiltonkreis

Problem 

Existenzaussage

Unter gewissen Voraussetzungen können jedoch Existenzaussagen getroffen werden. Dazu zählt der Satz von Dirac, der für einen Graphen mit einem Minimalgrad >= n/2 einen Hamiltonkreis verspricht. In Zusammenarbeit mit M. Löffler haben wir diese Bedingung leicht abgeschwächt, eine Bedingung an die Anzahl Nachbarn zweier Knoten kam hinzu. Man beachte, dass n/2 und 3n/4 gerade die Erwartungswerte für die beiden Eigenschaften sind. 

Ist der Minimalgrad >= n (1/2 - q) und |Nachbarn von x und y| >= n (3/4 - q/2) für alle x,y in V und q < 1/14 - 2/7n und n > 4, so existiert ein Hamiltonkreis. 

DOWNLOAD: Hamilton.ps (??? kb) zur Zeit leider nicht verfügbar

Matchings

Problem

Approximation des Optimums

Mitunter dauert das Berechnen des Optimums zu lange. Approximationsalgorithmen berechnen nur eine Näherung des Optimums, versprechen jedoch eine gewisse Güte ihrer Lösung (Abweichung v. Optimum in Prozent) und eine extrem schnelle Berechnungszeit. In meiner Diplomarbeit habe ich zwei solcher Algorithmen für das gewichtete Matchingproblem entwickelt.

GreedyA5 mit Güte: 2/3 - eps  Speed: O(m + n + 1/eps * log n/eps)
GreedyA7 mit Güte: 3/4 - eps  Speed: O((m + n) * 1/eps * log n/eps * log 1/eps)

DOWNLOAD: Diplomarbeit.pdf 800kB

Sonstige Projekte

Vorträge:

• MainMemory übersteigende Indexe: A Database Index to Large Biological Sequences
• textuelles Fallbasiertes Schließen in der Medizin: Textual CBR
  
• Optimierung von Steinerbaum-Algorithmen Teil 1: TagDerInformatik2002.zip, 1.3MB
• Optimierung von Steinerbaum-Algorithmen Teil 2: ForschungsSeminar.zip, 800kB

Noch zu beweisen:

• Perfekte planare Graphen sind degeneriert.