Algorithmische Graphentheorie by Volker Turau

By Volker Turau

Jedes process, das aus diskreten Zuständen oder Objekten und Beziehungen zwischen diesen besteht, kann als Graph modelliert werden. Viele Anwendungen erfordern effiziente Algorithmen zur Verarbeitung derartiger Systeme. Der Schwerpunkt dieser Einführung in die algorithmische Graphentheorie liegt in der praktischen Anwendung der Algorithmen innerhalb der Informatik. Die Algorithmen sind in kompakter shape in einer programmiersprachennahen Notation dargestellt, die eine Übertragung in eine objektorientierte Programmiersprache wie Java oder C# leicht macht. Die praktische Relevanz der behandelten Algorithmen wird in vielen Anwendungen aus Gebieten wie Compilerbau, Künstlicher Intelligenz, Betriebssystemen, Computernetzwerken, world-wide-web, examine sozialer Netzwerke und Operations learn demonstriert. Neun Kapitel decken die wichtigsten Teilgebiete der algorithmischen Graphentheorie ab. Das Buch enthält rund three hundred Übungsaufgaben in verschiedenen Schwierigkeitsgraden, für das Bachelor- und das Masterstudium. Die ausführlichen Lösungen befinden sich in einem Anhang.

Show description

Read or Download Algorithmische Graphentheorie PDF

Similar mathematics books

Functional Analysis and Operator Theory

Court cases of a convention Held in reminiscence of U. N. Singh, New Delhi, India, 2-6 August 1990

Intelligent Computer Mathematics: 10 conf., AISC2010, 17 conf., Calculemus 2010, 9 conf., MKM2010

This publication constitutes the joint refereed lawsuits of the tenth overseas convention on synthetic Intelligence and Symbolic Computation, AISC 2010, the seventeenth Symposium at the Integration of Symbolic Computation and Mechanized Reasoning, Calculemus 2010, and the ninth foreign convention on Mathematical wisdom administration, MKM 2010.

Extra resources for Algorithmische Graphentheorie

Sample text

Man nennt sie die Zusammenhangskomponenten. Ein zusammenhängender Graph besteht also nur aus einer Zusammenhangskomponente. 3 besteht aus vier und der zweite Graph aus drei Zusammenhangskomponenten. Ein ungerichteter Graph heißt vollständig, wenn je zwei Ecken durch eine Kante verbunden sind. Der vollständige Graph mit n Ecken wird mit Kn bezeichnet. 3 ist der Graph K\. Ein Graph heißt bipartit, wenn sich die Menge E der Ecken in zwei disjunkte Teilmengen Ei und E2 zerlegen läßt, so daß weder Ecken aus Ei, noch Ecken aus E2 untereinander benachbart sind.

Eingerahmt. , E4 bezeichnet. Von 0 verschiedene Diagonaleinträge zeigen an, daß die entsprechenden Ecken auf geschlossenen Wegen liegen. Somit kann mit diesem Verfahren auch die Existenz geschlossener Wege überprüft werden. In Kapitel 4 werden für dieses Problem einfachere Ver- fahren vorgestellt. Welches der beiden diskutierten Verfahren ist vorzuziehen? Dazu könnte man beide Verfahren implementieren und beide auf die gleichen Graphen anwenden; dabei müßte man den Verbrauch an Speicherplatz und CPU-Zeit messen und vergleichen.

Durch diese qualitative Bewertung sind nur Aussagen folgendender Form möglich: Für große Eingaben ist dieser Algorithmus schneller bzw. platzsparender. Es kann sein, daß ein Algorithmus mit Laufzeit 0(n3) für kleine n einem Algorithmus mit Laufzeit 0(n2) überlegen ist. In einem konkreten Problem muß man diesen Aspekt natürlich berücksichtigen. Mit Hilfe der Laufzeitkomplexität kann man auch abschätzen, für welche 2 38 Einführung die Rechenanlage noch in der Lage ist, das Problem in vertretbarer Zeit zu lösen.

Download PDF sample

Rated 4.04 of 5 – based on 11 votes