Matroid Theory
Seiten
2001
Oxford University Press (Verlag)
978-0-19-853563-8 (ISBN)
Oxford University Press (Verlag)
978-0-19-853563-8 (ISBN)
- Titel ist leider vergriffen;
keine Neuauflage - Artikel merken
This title provides a comprehensive introduction to the basics of matroid theory and treats more advanced topics. The book contains over 500 exercises and includes short proofs of major theorems in the subject. The final chapter lists 60 unsolved problems and describes progress towards their solutions.
What is the essence of the similarity between forests in a graph and linearly independent sets of columns in a matrix? Why does the greedy algorithm produce a spanning tree of minimum weight in a connected graph? Is it possible to test in polynomial time whether a matrix is totally unimodular? These questions form the basis of Matroid theory. The study of matroids is a branch of discrete mathematics with basic links to graphs, lattices, codes, transversals, and projective geometries. Matroids are of fundamental importance in combinatorial optimization and their applications extend into electrical engineering and statics. This book falls into two parts: the first provides a comprehensive introduction to the basics of matroid theory, while the second treats more advanced topics. The book contains over five hundred exercises and includes, for the first time in one place, short proofs of all but one of the major theorems in the subject. The final chapter lists sixty unsolved problems and describes progress towards their solutions.
What is the essence of the similarity between forests in a graph and linearly independent sets of columns in a matrix? Why does the greedy algorithm produce a spanning tree of minimum weight in a connected graph? Is it possible to test in polynomial time whether a matrix is totally unimodular? These questions form the basis of Matroid theory. The study of matroids is a branch of discrete mathematics with basic links to graphs, lattices, codes, transversals, and projective geometries. Matroids are of fundamental importance in combinatorial optimization and their applications extend into electrical engineering and statics. This book falls into two parts: the first provides a comprehensive introduction to the basics of matroid theory, while the second treats more advanced topics. The book contains over five hundred exercises and includes, for the first time in one place, short proofs of all but one of the major theorems in the subject. The final chapter lists sixty unsolved problems and describes progress towards their solutions.
1. Preliminaries; 2. Basic definitions and examples; 3. Duality; 4. Minors; 5. Connectivity; 6. Graphic matroids; 7. Representable matroids; 8. Constructions; 9. Higher connectivity; 10. Binary matroids; 11. Ternary matroids; 12. The Splitter theorem; 13. Submodular functions and matroid union; 14. Regular matroids; 15. Unsolved problems; 16. References; Appendix. Some interesting matroids; Notation; Index
| Erscheint lt. Verlag | 3.7.2001 |
|---|---|
| Reihe/Serie | Oxford Graduate Texts in Mathematics |
| Zusatzinfo | numerous line drawings |
| Verlagsort | Oxford |
| Sprache | englisch |
| Maße | 156 x 234 mm |
| Gewicht | 937 g |
| Themenwelt | Mathematik / Informatik ► Informatik ► Theorie / Studium |
| Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika | |
| Mathematik / Informatik ► Mathematik ► Algebra | |
| Mathematik / Informatik ► Mathematik ► Geometrie / Topologie | |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| ISBN-10 | 0-19-853563-5 / 0198535635 |
| ISBN-13 | 978-0-19-853563-8 / 9780198535638 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Eine Einführung in die Systemtheorie
Buch | Softcover (2022)
UTB (Verlag)
CHF 34,95
Buch | Hardcover (2021)
Springer Berlin (Verlag)
CHF 97,95
