scientific article; zbMATH DE number 3891371

From MaRDI portal
Publication:3347890





Die Kombinatorik hat in den letzten Jahrzehnten viele große Ideen hervorgebracht, als deren bedeutendstes Ergebnis man durchaus die Schöpfung der Matching- oder Transversaltheorie ansehen kann. Die Sätze von Hall, Dilworth, Menger, der Fluß-Schnitt-Satz, der Zusammenhang zum Hauptsatz des Linearen Programmierens, der Perfekte-Graphen-Satz -- sie alle sind Meilensteine in unserem Verständnis kombinatorischer Strukturen. Aber auch die kombinatorischen Algorithmen haben ihren Ausgang in diesem Gebiet genommen. Matching Algorithmen sind heute aus keinem Kurs über Diskrete Mathematik, theoretische Informatik oder Operations Research wegzudenken. Das vorliegende Buch konzentriert sich fast ausschließlich, wie schon im Titel angedeutet, auf die theoretischen Aspekte. Es ist in drei Abschnitte gegliedert: Zunächst bringt der Autor eine Auswahl der wichtigsten Sätze aus der gewöhnlichen Transversaltheorie, bespricht sodann Anwendungen über Matrizen, Ordnungen und Graphen, und wendet sich im dritten Abschnitt der Verallgemeinerung der Transversaltheorie zu, wenn die zugrundeliegenden Mengen eine Matroid-Struktur tragen. Der Autor hat eine straffe Exposition des Themas gegeben -- das Buch ist flüssig und anregend geschrieben. Inhaltlich sei nur eine einschränkende Bemerkung gemacht. Es ist schade, daß jeder Hinweis auf den engen Zusammenhang zum Dualitätssatz von Linearen Programmen fehlt. Gerade diese Verbindung öffnet ja erst den Zugang zu algebraischen und geometrischen Überlegungen. Trotzdem: Das Buch sei jedem, der sich in dieses Gebiet einarbeiten will, empfohlen, und es wird auch dem Kenner noch einiges zu bieten haben, z.B. den wunderbaren Satz von Baranyai über Parallelismen, der hier wohl erstmals in einem Lehrbuch erscheint. Inhalt: I. Der Heiratssatz von Philip Hall. II. Das Auswahlprinzip. III. Partielle Transversalen. IV. Gemeinsame Repräsentantenmengen. V. Anzahlsätze. VI. Kombinatorik von Matrizen. VII. Partielle Ordnungen. VIII. Graphen und Netzwerke. IX. Matroide. X. Transversaltheorie auf Matroiden. XI. Transversalmatroide und gemeinsame Transversalen. XII. Die Vereinigung von Matroiden.












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347890)