Graphic matroid

Summary

In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids.[1] A matroid that is both graphic and co-graphic is sometimes called a planar matroid (but this should not be confused with matroids of rank 3, which generalize planar point configurations); these are exactly the graphic matroids formed from planar graphs.

Definition

edit

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   and   are both independent, and   is larger than  , then there is an element   such that   remains independent. If   is an undirected graph, and   is the family of sets of edges that form forests in  , then   is clearly closed under subsets (removing edges from a forest leaves another forest). It also satisfies the exchange property: if   and   are both forests, and   has more edges than  , then it has fewer connected components, so by the pigeonhole principle there is a component   of   that contains vertices from two or more components of  . Along any path in   from a vertex in one component of   to a vertex of another component, there must be an edge with endpoints in two components, and this edge may be added to   to produce a forest with more edges. Thus,   forms the independent sets of a matroid, called the graphic matroid of   or  . 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.[2]

The bases of a graphic matroid   are the full spanning forests of  , and the circuits of   are the simple cycles of  . The rank in   of a set   of edges of a graph   is   where   is the number of vertices in the subgraph formed by the edges in   and   is the number of connected components of the same subgraph.[2] The corank of the graphic matroid is known as the circuit rank or cyclomatic number.

The lattice of flats

edit

The closure   of a set   of edges in   is a flat consisting of the edges that are not independent of   (that is, the edges whose endpoints are connected to each other by a path in  ). This flat may be identified with the partition of the vertices of   into the connected components of the subgraph formed by  : Every set of edges having the same closure as   gives rise to the same partition of the vertices, and   may be recovered from the partition of the vertices, as it consists of the edges whose endpoints both belong to the same set in the partition. In the lattice of flats of this matroid, there is an order relation   whenever the partition corresponding to flat   is a refinement of the partition corresponding to flat  .

In this aspect of graphic matroids, the graphic matroid for a complete graph   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   is naturally isomorphic to the lattice of partitions of an  -element set. Since the lattices of flats of matroids are exactly the geometric lattices, this implies that the lattice of partitions is also geometric.[3]

Representation

edit

The graphic matroid of a graph   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. The column for edge   has   in the row for one endpoint,   in the row for the other endpoint, and   elsewhere; the choice of which endpoint to give which sign is arbitrary. The column matroid of this matrix has as its independent sets the linearly independent subsets of columns.

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. Therefore, the column matrix is isomorphic to  .

This method of representing graphic matroids works regardless of the field over which the incidence is defined. Therefore, graphic matroids form a subset of the regular matroids, matroids that have representations over all possible fields.[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  . Namely, if the vertices of   are   we include the hyperplane   whenever   is an edge of  .

Matroid connectivity

edit

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. Graphic matroids are connected if and only if the underlying graph is both connected and 2-vertex-connected.[2]

Minors and duality

edit
 
Two different graphs (red) that are duals of the same planar graph (pale blue). Despite being non-isomorphic as graphs, they have isomorphic graphic matroids.

A matroid is graphic if and only if its minors do not include any of five forbidden minors: the uniform matroid  , the Fano plane or its dual, or the duals of   and   defined from the complete graph   and the complete bipartite graph  .[2][4][5] The first three of these are the forbidden minors for the regular matroids,[6] and the duals of   and   are regular but not graphic.

If a matroid is graphic, its dual (a "co-graphic matroid") cannot contain the duals of these five forbidden minors. Thus, the dual must also be regular, and cannot contain as minors the two graphic matroids   and  .[2]

Because of this characterization and Wagner's theorem characterizing the planar graphs as the graphs with no   or   graph minor, it follows that a graphic matroid   is co-graphic if and only if   is planar; this is Whitney's planarity criterion. If   is planar, the dual of   is the graphic matroid of the dual graph of  . While   may have multiple dual graphs, their graphic matroids are all isomorphic.[2]

Algorithms

edit

A minimum weight basis of a graphic matroid is a minimum spanning tree (or minimum spanning forest, if the underlying graph is disconnected). 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.

edit

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. These include the bipartite matroids, in which every circuit is even, and the Eulerian matroids, which can be partitioned into disjoint circuits. 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. Within the graphic matroids (and more generally within the binary matroids) these two classes are dual: a graphic matroid is bipartite if and only if its dual matroid is Eulerian, and a graphic matroid is Eulerian if and only if its dual matroid is bipartite.[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.[14]

References

edit
  1. ^ Tutte (1965) uses a reversed terminology, in which he called bond matroids "graphic" and cycle matroids "co-graphic", but this has not been followed by later authors.
  2. ^ a b c d e f g Tutte, W. T. (1965), "Lectures on matroids" (PDF), Journal of Research of the National Bureau of Standards, 69B: 1–47, doi:10.6028/jres.069b.001, MR 0179781. See in particular section 2.5, "Bond-matroid of a graph", pp. 5–6, section 5.6, "Graphic and co-graphic matroids", pp. 19–20, and section 9, "Graphic matroids", pp. 38–47.
  3. ^ Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, p. 95, ISBN 9780821810255.
  4. ^ Seymour, P. D. (1980), "On Tutte's characterization of graphic matroids", Annals of Discrete Mathematics, 8: 83–90, doi:10.1016/S0167-5060(08)70855-0, ISBN 9780444861108, MR 0597159.
  5. ^ Gerards, A. M. H. (1995), "On Tutte's characterization of graphic matroids—a graphic proof", Journal of Graph Theory, 20 (3): 351–359, doi:10.1002/jgt.3190200311, MR 1355434, S2CID 31334681.
  6. ^ Tutte, W. T. (1958), "A homotopy theorem for matroids. I, II", Transactions of the American Mathematical Society, 88 (1): 144–174, doi:10.2307/1993244, JSTOR 1993244, MR 0101526.
  7. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738
  8. ^ Fredman, M. L.; Willard, D. E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.
  9. ^ Chazelle, Bernard (2000), "A minimum spanning tree algorithm with inverse-Ackermann type complexity", Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456, S2CID 6276962.
  10. ^ Tutte, W. T. (1960), "An algorithm for determining whether a given binary matroid is graphic.", Proceedings of the American Mathematical Society, 11 (6): 905–917, doi:10.2307/2034435, JSTOR 2034435, MR 0117173.
  11. ^ Bixby, Robert E.; Cunningham, William H. (1980), "Converting linear programs to network problems", Mathematics of Operations Research, 5 (3): 321–357, doi:10.1287/moor.5.3.321, MR 0594849.
  12. ^ Seymour, P. D. (1981), "Recognizing graphic matroids", Combinatorica, 1 (1): 75–78, doi:10.1007/BF02579179, MR 0602418, S2CID 35579707.
  13. ^ Welsh, D. J. A. (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory, 6 (4): 375–377, doi:10.1016/s0021-9800(69)80033-5, MR 0237368.
  14. ^ Whiteley, Walter (1996), "Some matroids from discrete applied geometry", Matroid theory (Seattle, WA, 1995), Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, pp. 171–311, doi:10.1090/conm/197/02540, ISBN 978-0-8218-0508-4, MR 1411692.