By Peter Läuchli (auth.)

ISBN-10: 3034856350

ISBN-13: 9783034856355

ISBN-10: 3034856369

ISBN-13: 9783034856362

Show description

Read Online or Download Algorithmische Graphentheorie PDF

Best german_12 books

Download e-book for kindle: Lebensmittel und Mikroorganismen: Frischware — by K.-H. Wallhäußer

1m Umgang mit Lebensmitteln muBte der Mensch schon fruh feststellen, daB zahlreiche Produkte rasch verderben und dann oft gesundheitsgefahrdend sind. Cber Jahrtausende blieben die Ursachen eines solchen Verderbs verborgen und seine Auswirkungen in der Regel auf einen kleinen hauslichen Kreis beschrankt.

Download e-book for iPad: Journalismus im Internet: Profession – Partizipation – by Christoph Neuberger, Christian Nuernbergk, Melanie Rischke

Im web verliert der Journalismus sein Monopol als „Gatekeeper“, weil dort jeder ohne großen Aufwand publizieren kann. Vermittlung zwischen Kommunikatoren und Rezipienten bleibt aber weiterhin notwendig. Wer aber kanalisiert die „Informationsflut“ im net? Wer sortiert den „Informationsmüll“ aus?

Additional resources for Algorithmische Graphentheorie

Example text

24 Kapitel 4. Komplexitat Beispiele fiir NP-vollstandige Probleme sind: das Rucksackproblem (Seite 22), das friiher erwahnte Problem der Dreifarbbarkeit von Graphen (Seite 21). Zum Schluss noch eine allgemeine Bemerkung zur Komplexitat von GraphenAlgorithmen: • Wie am Anfang dieses Unterkapitels auseinandergesetzt wurde, wird das Komplexitatsmass durch die Kodierung der Eingabedaten beeinflusst. Fiir eine Betrachtung im Zusammenhang mit der NP-Vollstandigkeit bemerken wir, dass die Langen aller "verniinftigen" Kodierungen von Graphen (Adjazenz-, Inzidenzmatrix; Adjazenzlisten) zu n polynomial aquivalent sind.

Zu beachten ist dabei: Obwohl G schlicht vorausgesetzt ist, konnen durch Zusammenziehen von Kanten Parallelkanten entstehen. Diese miissen stehengelassen werden. Dagegen sind Schlingen, die durch Zusammenziehen einer Parallelkante entstehen, sofort wegzulassen. Man vergewissert sich leicht, dass damit die obigen Feststellungen 1. und 2. immer noch gelten. 2 solI den Prozess illustrieren. Es wird dabei auch klar, dass fUr die Bildung der Geriiste genau die zusammengezogenen Kanten zu sammeln sind, wabrend man die gelOschten Kanten vergessen kann.

2. Algorithmen 57 Eine von Minty stammende Branch-and-Bound-Methode beruht auf der folgenden Idee: Sei u eine beliebige Kante von G. Dann gilt: 1. Die Geriiste von G, die u nicht enthalten, sind genau die Geriiste des Graphen G', der aus G durch Loschung von u entsteht. 2. Die Geriiste von G, die u enthalten, sind genau die Geriiste des Graphen Gil, der aus G durch Zusammenziehung von u entsteht, und zu denen man dann u wieder hinzunimmt. ) Daraus ergibt sich recht ofl'ensichtlich ein rekursives Verfahren.

Download PDF sample

Algorithmische Graphentheorie by Peter Läuchli (auth.)


by Mark
4.3

Read e-book online Algorithmische Graphentheorie PDF
Rated 4.94 of 5 – based on 7 votes