Matroid theory
著者
書誌事項
Matroid theory
Oxford University Press, 1992
大学図書館所蔵 件 / 全41件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
"Oxford science publications"--cover
Includes bibliographical references and index
内容説明・目次
内容説明
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
「Nielsen BookData」 より
