Algorithmische Graphentheorie by Volker Turau PDF

By Volker Turau

ISBN-10: 348659057X

ISBN-13: 9783486590579

Jedes approach, 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 examine 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 Online or Download Algorithmische Graphentheorie PDF

Similar mathematics books

The Math Book: From Pythagoras to the 57th Dimension, 250 by Clifford A. Pickover PDF

Math’s limitless mysteries and wonder spread during this follow-up to the best-selling The technological know-how e-book. starting thousands of years in the past with historical “ant odometers” and relocating via time to our modern day quest for brand new dimensions, it covers 250 milestones in mathematical heritage. one of the quite a few delights readers will know about as they dip into this inviting anthology: cicada-generated major numbers, magic squares from centuries in the past, the invention of pi and calculus, and the butterfly influence.

Download e-book for kindle: Simplicial Global Optimization by Remigijus Paulavičius, Julius Žilinskas

Simplicial worldwide Optimization is based on deterministic masking tools partitioning possible area through simplices. This booklet appears to be like into some great benefits of simplicial partitioning in international optimization via purposes the place the quest house can be considerably diminished whereas making an allowance for symmetries of the target functionality via atmosphere linear inequality constraints which are controlled through preliminary partitioning.

Additional info for Algorithmische Graphentheorie

Example text

4 0 / optimale Reihenfolge ste Gesamtumrüstzeit zu erzielen. Die Zustand 1. 4. Bestimmen Sie für die den Konfliktgraphen Produktionsaufträge, um die geringFertigungszelle befindet sich anfangs im der folgende Klassenhierarchie und die angegebenen Methoden geben Sie eine optimal komprimierte Dispatchtabelle und an. A E ß C D F für eine G H A : m\ B : nii, m4 C : mi,m3 I D : m,\ E : m2,m3 F : mi G : nii H : ni4 I : m5 1 18 5. Es sei M eine a) b) Einleitung Menge von Web-Seiten mit folgenden beiden Eigenschaften: Jede Seite in M enthält mindestens einen Verweis und außerhalb von M gibt es keine Seiten, welche auf Seiten in M verweisen.

21: Eine verbesserte Version der Prozedur transAbschluss Eine für praktische Anwendungen interessante Beschreibung der worst case Komplexität verwendet Parameter, die neben der Länge der Eingabe auch die Länge der Ausgabe des Algorithmus verwenden. Im vorliegenden Beispiel kann man die Ausgabe durch die Anzahl mAb der Kanten des transitiven Abschlusses beschreiben. Die innerste Laufschleife wird maximal m^-mal durchlaufen. Somit ergibt sich eine Gesamtlaufzeit von 0(n2 +nmAb)- Ist die Größenordnung von niAb gleich 0(n), so ergibt sich eine Laufzeit 0(n2).

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.

Download PDF sample

Algorithmische Graphentheorie by Volker Turau


by Kevin
4.2

Rated 4.17 of 5 – based on 7 votes