Graphical (graphic) matroid

Graphical (graphic) matroid --- графический матроид.

A matroid which is obtained from a graph [math]\displaystyle{ G = (V,A) }[/math] with the vertex set [math]\displaystyle{ V }[/math] and arc set [math]\displaystyle{ A }[/math]. Let [math]\displaystyle{ {\mathcal I}(A) }[/math] be the family of all the subsets of [math]\displaystyle{ A }[/math] which do not include arcs forming a cycle. A graphical matroid obtained from the graph [math]\displaystyle{ G }[/math] is also isomorphic to the matrix matroid obtained from the incidence matrix of [math]\displaystyle{ G }[/math] and is representable over any field, i.e. graphical matroid is regular.

Thus, a matroid is called graphic if it can be represented as the cycle matroid of a graph. A matroid is called cographic if it is the dual of a graphic matroid. Graphic and cographic matroids are representable over every field. The reader may wonder if there is a way of determining whether or not a matroid is graphic. Tutte (1960) gave a polinomial-time algorithm for determining whether a binary matroid is graphic. If the binary matrix is graphic, then the algorithm returns the incidence matrix of a graph, otherwise it concludes that the matrix is not graphic. Later (1981) Seymour gave an algorithm for determining whether any matroid, not necessarily a binary matroid, is graphic.