Matroid Theory and Its Applications: Lectures given at a Summer School of the Centro Internazionale Matematico Estivo (C.I.M.E.) held in Varenna ... 2, 1980 (C.I.M.E. Summer Schools, 83)

Cover
Matroid Theory and Its Applications
ISBN 9783642111099
CONTENTS
Un\' Introduzione Alla Teoria Delle Funzioni Di Möbius
	1. Introduzione
	2. Reticoli distributivi ed insiemi parzialmente ordinati
	3. Coni di valutazione
	4. Anello di valutazione di un reticolo distributivo
	5. La funzione di Mebius
	6. L\'algebra di Mebius
	7. La funzione di Mebius nei reticoli semimodulari
	8. L\'anello di Tutte-Grothendieck
	9. Un\'applicazione geometrica
	Bibliografia
Some Remarks on the Critical Problem
	Introduction
	References
The Tutte Polynomial Part I: General Theory
	1. Introduction
	2. A Prototypical Example
	3. The Tutte Polynomial
	4. Matroid Constructions
	5. Reconstruction
	6. Identities, Inequalities, and Extrenal Matroid Theory
	Bibliography
On 3-Connected Matroids and Graphs
	Introduction
	Acknowledgement
	References
The Poset of Subpartitions and cayley\'s Formula for the Complexity of a complete Graph
	I. Introduction
	II. The Poset of Subpartitions
	II. The Subpartition of a Function
	III. Cayley\'s Formula for Tree(n)
	References
Engineering Applications of Matroids - A Survey
	Introduction
	I. Various Problems
	II. Various Remarks
	III. Formulation of the Network Analysis Problem
	IV. The Classical Result
	V. A Stronger Necessary Condition
	VI. How Can One Check Conditions (C1) and (C2) ?
	VII. Is (C2) Sufficient?
	VIII. Should We Always Accept \'Generality\'?
	IX. Some Remarks on Question 3B
	X. Applications to Network Synthesis
	Acknowledgements
	References
Matroids and Combinatorial Optimisation
	1. Computational Complexity
		1. Introduction
		2. Low level complexity
		3. The class NP
		4. NP-complete problems
		5. Some Examples
		6. P-space
	2. Matroid Theory
		1. Definitions
		2. Classes of matroids
		3 . Special Matroids
		4. Excluded minor theorems
		5. Matroid polyhedra
	3. Matroids and Algorithms
		1. greedy algorithm
		2. The union of matroids
		3. The Shannon switching game
		4. A polynomial algorithm for k-connectivity
	4. Lovasz\'s Attack on the Parity Problem
		1. The parity problem
		2. 2-polymatroids
		3. The Gallai - Lovasz Identity
		4. A min-max theorem for linear 2-polymatroids
		5. On a polynomial algorithm for the 2-parity problem
		6. Pinning planar structures
	5. Oracle Bounds on Algorithms
		1 The concept of an oracle
		2. Examples and further results
		3. The 2-PARITY problem is exponential
	6. Seymour\'s Characterisation of Regular Matroids
		1 Binary and regular matroids
		2. Splitters
		3. The decomposition theorem
		4. A polynomial algorithm to test whether a matrix is totally unimodular
	7. Colouring, Flows and Blocking Problems
		1. The blocking problem
		2. Colouring graphs
		3. Flows taking values in an abelian group
		4. Tangential Blocks
		5. A problem on the Desargues Configuration
	8. Flows in Matroids
		1. The max-flow min-cut theorem
		2. Multicommodity flows
		3. Multicommodity flows in matroids
		4. A summary of results
	References
Voltage-Graphic Matroids
	References