Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
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. 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 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. The corank of the graphic matroid is known as the circuit rank or cyclomatic number.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.