Matroid Theory and its Applications in Electric Network Theory and in Statics

ISBN-13: 9783662221457 / Angielski / Miękka / 2013 / 533 str.

Andras Recski

Opis

I. The topics of this book The concept of a matroid has been known for more than five decades. Whitney (1935) introduced it as a common generalization of graphs and matrices. In the last two decades, it has become clear how important the concept is, for the following reasons: (1) Combinatorics (or discrete mathematics) was considered by many to be a collection of interesting, sometimes deep, but mostly unrelated ideas. However, like other branches of mathematics, combinatorics also encompasses some gen- eral tools that can be learned and then applied, to various problems. Matroid theory is one of these tools. (2) Within combinatorics, the relative importance of algorithms has in- creased with the spread of computers. Classical analysis did not even consider problems where "only" a finite number of cases were to be studied. Now such problems are not only considered, but their complexity is often analyzed in con- siderable detail. Some questions of this type (for example, the determination of when the so called "greedy" algorithm is optimal) cannot even be answered without matroidal tools.

Spis treści

ONE.- 1 Basic concepts from graph theory.- 2 Applications.- 3 Planar graphs and duality.- 4 Applications.- 5 The theorems of König and Menger.- 6 Applications.- TWO.- 7 Basic concepts in matroid theory.- 8 Applications.- 9 Algebraic and geometric representation of matroids.- 10 Applications.- 11 The sum of matroids I.- 12 Applications.- 13 The sum of matroids II.- 14 Applications.- 15 Matroids induced by graphs.- 16 Applications.- 17 Some recent results in matroid theory.- 18 Applications.- Appendix 1 Some important results in chronological order.- Appendix 2 List of the Boxes.- Appendix 3 List of the Algorithms.- Appendix 4 Solutions to the Exercises and Problems.