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

The Loom of God: Tapestries of Mathematics and Mysticism

From the mysterious cult of Pythagoras to the outstanding mechanics of Stonehenge to the “gargoyles” and fractals on today’s desktops, arithmetic has regularly been a strong, even divine strength on the earth. In a full of life, clever synthesis of math, mysticism, and technology fiction, Clifford Pickover explains the everlasting magic of numbers.

Good Math: A Geek's Guide to the Beauty of Numbers, Logic, and Computation (Pragmatic Programmers)

Mathematics is beautiful--and it may be enjoyable and interesting in addition to functional. strong Math is your consultant to a few of the main exciting subject matters from thousand years of arithmetic: from Egyptian fractions to Turing machines; from the genuine which means of numbers to facts timber, team symmetry, and mechanical computation. If you've ever puzzled what lay past the proofs you struggled to accomplish in highschool geometry, or what limits the services of computing device in your table, this can be the ebook for you.

Why do Roman numerals persist? How will we recognize that a few infinities are higher than others? and the way will we be aware of for convinced a application will ever end? during this fast paced travel of contemporary and not-so-modern math, desktop scientist Mark Chu-Carroll explores many of the maximum breakthroughs and disappointments of greater than thousand years of mathematical concept. there's pleasure and wonder in arithmetic, and in additional than dozen essays drawn from his well known "Good Math" web publication, you'll locate thoughts, proofs, and examples which are usually mind-blowing, counterintuitive, or simply simple weird.

Mark starts his trip with the fundamentals of numbers, with an wonderful journey in the course of the integers and the traditional, rational, irrational, and transcendental numbers. The voyage keeps with a glance at many of the oddest numbers in arithmetic, together with 0, the golden ratio, imaginary numbers, Roman numerals, and Egyptian and carrying on with fractions. After a deep dive into smooth good judgment, together with an advent to linear common sense and the logic-savvy Prolog language, the journey concludes with a journey of contemporary set concept and the advances and paradoxes of recent mechanical computing.

in case your highschool or university math classes left you greedy for the internal that means in the back of the numbers, Mark's e-book will either entertain and enlighten you.

Everything and More: A Compact History of Infinity

"A gripping advisor to the fashionable taming of the limitless. "—The big apple occasions. With a brand new advent via Neal Stephenson. Is infinity a legitimate mathematical estate or a meaningless abstraction? David Foster Wallace brings his highbrow ambition and attribute bravura variety to the tale of the way mathematicians have struggled to appreciate the countless, from the traditional Greeks to the nineteenth-century mathematical genius Georg Cantor's counterintuitive discovery that there has been a couple of type of infinity.

Additional resources for Algorithmische Graphentheorie

Example text

Für das grundlegende Verständnis eignet sich am Besten eine mehr oder weniger informelle Beschreibung, mathematische Formalismen anlehnt und einfache Konstrukte von Programmiersprachen verwendet. Diese Beschreibungsform wird als Pseudocode bezeichnet. Das Ziel dieser Beschreibungsform besteht darin, die verwendeten Datenstrukturen und den Ablauf eines Algorithmus kompakt und gleichzeitig eindeutig zu beschreiben. Der Pseudocode für einen Algorithmus muss so detailliert sein, dass die Korrektheit nachgewiesen und die worst case Komplexität hinsichtlich Speicher- und Zeitbedarf bestimmt werden kann.

Für l 0,1,... ,n gilt: In wenn es in G einen Weg von i nach j verwendet. , 1} genau dann eine Kante welcher nur Ecken aus der Beweis. Der Beweis erfolgt durch vollständige Induktion nach l. Für i 0 ist die Aussage richtig. Die Aussage sei nun für l > 0 richtig. , l + 1} verwendet. , / + 1} verwendet. , l}, so ist die Aussage nach Induktionsvoraussetzung richtig. Verwendet W die Ecke l + 1, so gibt es auch einen einfachen Weg W mit dieser Eigenschaft. Es sei Wi der Teilweg von i nach l + 1 und W2 der von l + 1 nach j.

Kanten des Graphen. Der letzte Iterator steht nur für ungerichtete Graphen zur 'Java Universal Network/Graph Framework (JUNG), JGraphT, Boost Graph Library (BGL), Library of Efficient Data types and Algorithms (LEDA), GOBLIN Graph library, Ruby Graph Library (RGL) 2 46 Einführung Verfügung.

Download PDF sample

Rated 4.34 of 5 – based on 3 votes