Matroids: The Value of Abstraction
3. Multiple births
You can verify that this collection of sets can serve as the independent setI for a matroid on the set E, by verifying that the axioms (rules) we have stated apply to this collection of sets.
If one starts at a vertex in our graph, then moves along previously unused edges and returns to the original vertex, one travels a circuit. In the graph above examples of circuits are: u, v, s, u; and v (via edge 1), w, v (via edge 2). Note that we will consider two circuits the same if they are listed in reverse cyclic order and that there are many ways of writing down the same circuit that look a bit different. Thus, s, w, x, t, s and w, x, t, s, w and w, s, t, x, w are all different notations for the same circuit.
C3 (C1 C2) - e
Circuit 3 captures the property of circuits which says that when two circuits have an edge e in common, one can create a new circuit from the edges of the two circuits which does not use edge e.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance