1. Clutters
Gérard Cornuéjols · Society for Industrial and Applied Mathematics eBooks · 2001
A clutter C is a pair (V, E), where V is a finite set and E is a family of subsets of V none of which is included in another. The elements of V are the vertices of C and those of E are the edges. For example, a simple graph (V, E) (no multiple edges or loops) is a clutter. We refer to West [208] for definitions in graph theory. In a clutter, a matching is a set of pairwise disjoint edges. A transversal is a set of vertices that intersects all the edges. A clutter is said to pack if the maximum cardinality of a matching equals the minimum cardinality of a transversal. This terminology is due to Seymour [183]. Many min-max theorems in graph theory can be rephrased by saying that a clutter packs. We give three examples. The first is Känig's theorem.