Графтардың орман жиындарымен матроидтар

Matroid with graph forests as independent sets
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. 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.

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.

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. 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 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. 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. 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. 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.