Algorithmische Graphentheorie by Volker Turau

By Volker Turau

Jedes method, 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

Extra info for Algorithmische Graphentheorie

Sample text

Dies erleichtert die Verifikation des Programms und auch die spätere Wartung. Zu beachten ist auch die Verwendung schon existierender Software. Der Anwender eines Algorithmus ist vor allem an der Effizienz interessiert; dies beinhaltet neben dem 36 2 Einführung zeitlichen Aspekt auch den beanspruchten Speicherplatz. Die Entscheidung wird wesentlich davon geprägt, wie oft das zu schreibende Programm ausgeführt werden soll. Falls es sich um ein Programm handelt, welches sehr häufig benutzt wird, lohnt sich der Aufwand, einen komplizierten Algorithmus zu realisieren, wenn dies zu Laufzeitverbesserungen oder Speicherplatzersparnis führt.

Hierbei ist (K[\, i], K[2, i}) die i-te Kante. Es werden 2m Speicherplätze benötigt. 10. 12: Die Kantenliste eines gerichteten Graphen Um bei einem ungerichteten Graphen festzustellen, ob es eine Kante von i nach j gibt, muß die ganze Kantenliste durchsucht werden. Bei gerichteten Graphen ist es vorteilhaft, die Kanten lexikographisch zu sortieren. In diesem Falle kann man mittels binärer Suche schneller feststellen, ob es eine Kante von i nach j gibt. 30 2 Einführung Für ungerichtete Graphen kann die Kantenliste erweitert werden, so daß jede Kante zweimal vertreten ist, einmal in jeder Richtung.

Diese Situation kann leicht durch einen gerichteten Graphen dargestellt werden. Die Dateien bilden die Ecken, und falls eine Datei direkt in eine andere eingefügt wird, wird dies durch eine gerichtete Kante zwischen den Ecken, die der Datei und der eingefügten Datei entspre- 2 32 Einführung chen, dargestellt. Somit erhält man einen gerichteten Graphen. Die Anzahl der Ecken entspricht der Anzahl der Dateien, und die Datei Di wird direkt oder indirekt in die Datei D3 eingefügt, falls es einen Weg von Dj nach Di gibt.

Download PDF sample

Rated 4.12 of 5 – based on 42 votes