No label defined (Q3347890)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3891371
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3891371 |
Statements
1982
0 references
transversal theory
0 references
matrices
0 references
order and graphs
0 references
matroid structure
0 references
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.
0 references