In the mathematical theory of
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s, a graphic matroid (also called a cycle matroid or polygon matroid) is a
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
whose independent sets are the
forests
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
in a given finite
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
. The
dual matroid
In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it...
Matroid duals go back to the original paper by Hassler ...
s of graphic matroids are called co-graphic matroids or bond matroids. 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
A
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
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
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...
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.
The bases of a graphic matroid
are the full
spanning forests of
, and the circuits of
are the
simple cycles of
. The
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
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.
The corank of the graphic matroid is known as the
circuit rank
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
or cyclomatic number.
The lattice of flats
The
closure of a set
of edges in
is a
flat
Flat or flats may refer to:
Architecture
* Flat (housing), an apartment in the United Kingdom, Ireland, Australia and other Commonwealth countries
Arts and entertainment
* Flat (music), a symbol () which denotes a lower pitch
* Flat (soldier), ...
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
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
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 lattice
In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumption of finiteness. Geometric lattices and matroid lattices, r ...
s, this implies that the lattice of partitions is also geometric.
Representation
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
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
over which the incidence is defined. Therefore, graphic matroids form a subset of the
regular matroid
In mathematics, a regular matroid is a matroid that can be represented over all fields.
Definition
A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". On ...
s, matroids that have
representations
''Representations'' is an interdisciplinary journal in the humanities published quarterly by the University of California Press. The journal was established in 1983 and is the founding publication of the New Historicism movement of the 1980s. It ...
over all possible fields.
The lattice of flats of a graphic matroid can also be realized as the lattice of a
hyperplane arrangement
In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''.
Questions about a hyperplane arrangement ''A'' generally concern geometrical, ...
, 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
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
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
and
2-vertex-connected.
Minors and duality
A matroid is graphic if and only if its
minors do not include any of five forbidden minors: the
uniform matroid
In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...
, the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
or its dual, or the duals of
and
defined from the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
and the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
.
[. 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.] The first three of these are the forbidden minors for the regular matroids, 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
.
Because of this characterization and
Wagner's theorem
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on fi ...
characterizing the
planar graphs as the graphs with no
or
graph minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
, 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
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-lo ...
of
. While
may have multiple dual graphs, their graphic matroids are all isomorphic.
Algorithms
A minimum weight basis of a graphic matroid is a
minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
(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, 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. The fastest known time bound that has been proven for a deterministic algorithm is slightly superlinear.
Several authors have investigated algorithms for testing whether a given matroid is graphic.
[.] For instance, an algorithm of solves this problem when the input is known to be a
binary matroid
In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).. That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent i ...
. 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.
Related classes of matroids
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 matroid
In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.
Example
A uniform matroid U^r_n is bipartite if and only if r is an odd number, because the circuits in such a matroid have size r+1.
Relation to bipartite g ...
s, in which every circuit is even, and the
Eulerian matroid
In matroid theory, an Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits.
Examples
In a uniform matroid U^r_n, the circuits are the sets of exactly r+1 elements. Therefore, a uniform matroid is ...
s, 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
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
. Within the graphic matroids (and more generally within the
binary matroid
In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).. That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent i ...
s) these two classes are dual: a graphic matroid is bipartite if and only if its
dual matroid
In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it...
Matroid duals go back to the original paper by Hassler ...
is Eulerian, and a graphic matroid is Eulerian if and only if its dual matroid is bipartite.
[.]
Graphic matroids are one-dimensional
rigidity matroid
In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of Degrees of freedom (mechanics), degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In ...
s, 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 graph
In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on ''n'' vertices such that, for all ''k'', every ''k''-vertex subgraph has ...
s 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.
[.]
References
{{reflist, colwidth=30em
Matroid theory
Planar graphs
Graph connectivity
Spanning tree