Netzwerke. Ein spezielles Gebiet der Graphentheorie

Examensarbeit aus dem Jahr 2007 im Fachbereich Mathematik - Angewandte Mathematik, Note: 1-, Universit?t Hamburg, Sprache: Deutsch, Abstract: Einleitung Die vorliegende Arbeit soll einen Einblick in die Graphentheorie geben. Dabei wird insbesondere auf Netzwerke als graphische Darstellungsform eingegangen. Bevor aber ein Blick auf die Netzwerke geworfen werden kann, sollen in Kapitel 1 einige Grundbegriffe der Graphentheorie erl?utert werden. Diese Grundbegriffe wurden im Jahr 1736 eingef?hrt als Leonard Euler sein "K?nigsberger Br?ckenproblem" ver?ffentlichte in dem er versucht, einen Rundweg durch die Stadt K?nigsberg zu finden, ohne dabei eine der sieben Br?cken zweimal passieren zu m?ssen. Am Ende de Rundganges sollte sich der Spazierg?nger am Ausgangspunkt wiederfinden. Euler zeigt durch die ?bertragung des K?nigsberger Stadtplanes in einen ungerichteten Graphen, dass es einen solchen Weg nicht gibt. Die von Euler eingef?hrten Begriffe lassen sich aber auch auf gerichtete Graphen ?bertragen, die in Kapitel 2 behandelt werden. Weiterhin soll in diesem Kapitel der Begriff des Turniers erl?utert werden. Im 3. Kapitel werden schlie lich die Netzwerke thematisiert. Der Leser wird mit Begriffen wie "Fl?sse" und "Schnitte" vertraut gemacht, um den Maximum-Fluss-Minimum-Schnitt-Satz von Ford und Fulkerson beweisen zu k?nnen. In einem ausf?hrlichen Beispiel ist dann der Algorithmus von Ford und Fulkerson dargestellt. Kapitel 4 befasst sich mit "trennenden Mengen". Der Schwerpunkt dieses Kapitels liegt auf dem Satz von Menger und den daraus resultierenden Folgerungen, die mit dem Maximum-Fluss-Minimum-Schnitt-Satz des vorherigen Kapitels bewiesen werden k?nnen. Zum Schluss werden im 5. Kapitel die bisher erzielten Ergebnisse auf zwei Bespiele angewendet. In beiden Beispielen steht der Maximum-Fluss-Minimum-Schnitt-Satz im Vordergrund.

Author: Sandra Riedemann

Publisher: Grin Verlag

Publication Date: Jul 03, 2009

Number of Pages: 82 pages

Binding: Paperback or Softback

ISBN-10: 3640361733

ISBN-13: 9783640361731