Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphic matroid
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.