Graphic matroid
A matroid may be defined as a family of finite sets (called the "independent sets" of the matroid) that is closed under subsets and that satisfies the "exchange property": if sets
is the family of sets of edges that form forests in
More generally, a matroid is called graphic whenever it is isomorphic to the graphic matroid of a graph, regardless of whether its elements are themselves edges in a graph.
is the number of vertices in the subgraph formed by the edges in
[2] The corank of the graphic matroid is known as the circuit rank or cyclomatic number.
In the lattice of flats of this matroid, there is an order relation
is particularly important, because it allows every possible partition of the vertex set to be formed as the set of connected components of some subgraph.
Thus, the lattice of flats of the graphic matroid of
can be defined as the column matroid of any oriented incidence matrix of
Such a matrix has one row for each vertex, and one column for each edge.
elsewhere; the choice of which endpoint to give which sign is arbitrary.
If a set of edges contains a cycle, then the corresponding columns (multiplied by
if necessary to reorient the edges consistently around the cycle) sum to zero, and is not independent.
Conversely, if a set of edges forms a forest, then by repeatedly removing leaves from this forest it can be shown by induction that the corresponding set of columns is independent.
This method of representing graphic matroids works regardless of the field over which the incidence is defined.
[2] The lattice of flats of a graphic matroid can also be realized as the lattice of a hyperplane arrangement, in fact as a subset of the braid arrangement, whose hyperplanes are the diagonals
A matroid is said to be connected if it is not the direct sum of two smaller matroids; that is, it is connected if and only if there do not exist two disjoint subsets of elements such that the rank function of the matroid equals the sum of the ranks in these separate subsets.
[2][4][5] The first three of these are the forbidden minors for the regular matroids,[6] and the duals of
Thus, the dual must also be regular, and cannot contain as minors the two graphic matroids
may have multiple dual graphs, their graphic matroids are all isomorphic.
Algorithms for computing minimum spanning trees have been intensively studied; it is known how to solve the problem in linear randomized expected time in a comparison model of computation,[7] or in linear time in a model of computation in which the edge weights are small integers and bitwise operations are allowed on their binary representations.
[8] The fastest known time bound that has been proven for a deterministic algorithm is slightly superlinear.
[9] Several authors have investigated algorithms for testing whether a given matroid is graphic.
[10][11][12] For instance, an algorithm of Tutte (1960) solves this problem when the input is known to be a binary matroid.
Seymour (1981) solves this problem for arbitrary matroids given access to the matroid only through an independence oracle, a subroutine that determines whether or not a given set is independent.
Some classes of matroid have been defined from well-known families of graphs, by phrasing a characterization of these graphs in terms that make sense more generally for matroids.
A graphic matroid is bipartite if and only if it comes from a bipartite graph and a graphic matroid is Eulerian if and only if it comes from an Eulerian graph.
[13] Graphic matroids are one-dimensional rigidity matroids, matroids describing the degrees of freedom of structures of rigid beams that can rotate freely at the vertices where they meet.
In one dimension, such a structure has a number of degrees of freedom equal to its number of connected components (the number of vertices minus the matroid rank) and in higher dimensions the number of degrees of freedom of a d-dimensional structure with n vertices is dn minus the matroid rank.
In two-dimensional rigidity matroids, the Laman graphs play the role that spanning trees play in graphic matroids, but the structure of rigidity matroids in dimensions greater than two is not well understood.
