Graphic matroidIn 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.
Matroid representationIn the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra. A linear matroid is a matroid that has a representation, and an F-linear matroid (for a field F) is a matroid that has a representation using a vector space over F.
Matroid rankIn the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks. The rank function is one of the fundamental concepts of matroid theory via which matroids may be axiomatized. Matroid rank functions form an important subclass of the submodular set functions.
William TutteWilliam Thomas Tutte ( – ) est un mathématicien et cryptanalyste britannique, puis canadien. Pendant la Seconde Guerre mondiale, il décrypte l'un des principaux codes allemands, ce qui a un impact significatif sur le succès des opérations alliées. Il apporte aussi des contributions importantes en mathématiques, dont un travail fondateur en combinatoire, notamment en théorie des matroïdes et en théorie des graphes. Tutte est né à Newmarket dans le Suffolk, d'un père jardinier.
HypergrapheLes hypergraphes sont des objets mathématiques généralisant la notion de graphe. Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe). Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey.
Arbre couvrantDans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. Dans certains cas, le nombre d'arbres couvrants d'un graphe connexe est facilement calculable. Par exemple, si lui-même est un arbre, alors , tandis que si est un n-cycle, alors .
Family of setsIn set theory and related branches of mathematics, a collection of subsets of a given set is called a family of subsets of , or a family of sets over More generally, a collection of any sets whatsoever is called a family of sets, set family, or a set system. A family of sets may be defined as a function from a set , known as the index set, to , in which case the sets of the family are indexed by members of .
Réunion disjointeEn mathématiques, la réunion disjointe est une opération ensembliste. Contrairement à l'union usuelle, le cardinal d'une union disjointe d'ensembles est toujours égal à la somme de leurs cardinaux. L'union disjointe d'une famille d'ensembles correspond à leur somme en théorie des catégories, c'est pourquoi on l'appelle aussi somme disjointe. C’est une opération fréquente en topologie et en informatique théorique. Dans une réunion A∪B de deux ensembles, l'origine des éléments y figurant est perdue et les éléments de l'intersection ne sont comptés qu'une seule fois.
Component (graph theory)In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.
Matroid oracleIn mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications. The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent.
Regular matroidIn mathematics, a regular matroid is a matroid that can be represented over all fields. 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". One of the ways of constructing a matroid is to select a finite set of vectors in a vector space, and to define a subset of the vectors to be independent in the matroid when it is linearly independent in the vector space.
Vámos matroidIn mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished manuscript in 1968. The Vámos matroid has eight elements, which may be thought of as the eight vertices of a cube or cuboid. The matroid has rank 4: all sets of three or fewer elements are independent, and 65 of the 70 possible sets of four elements are also independent.
Polynôme de TutteLe polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. L'importance de ce polynôme provient des informations qu'il contient sur le graphe .
GreedoidIn combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.
Enveloppe convexeL'enveloppe convexe d'un objet ou d'un regroupement d'objets géométriques est l'ensemble convexe le plus petit parmi ceux qui le contiennent. Dans un plan, l'enveloppe convexe peut être comparée à la région limitée par un élastique qui englobe tous les points qu'on relâche jusqu'à ce qu'il se contracte au maximum. L'idée serait la même dans l'espace avec un ballon qui se dégonflerait jusqu'à être en contact avec tous les points qui sont à la surface de l'enveloppe convexe.
Géométrie discrèteLa géométrie discrète est une branche de la géométrie. On parle de géométrie discrète pour la distinguer de la géométrie « continue ». Tout comme cette dernière, elle peut être analytique, les objets sont dans ce cas décrits par des inéquations. Un exemple simple : la géométrie continue en deux dimensions permet de définir des droites, des cercles dans un plan. Ces objets sont des ensembles de points qui sont des couples de nombres réels.
Maille (théorie des graphes)En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de −1). La maille d'un graphe est la longueur du plus court de ses cycles. Image:Petersen graph blue.svg|Le [[graphe de Petersen]] a une maille de 5 et est une cage. Image:Heawood_Graph.svg|Le [[graphe de Heawood]] a une maille de 6 et est une cage. Image:Frucht_graph.neato.
Circuit rankIn 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 forest. It is equal to the number of independent cycles in the graph (the size of a cycle basis). Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula where m is the number of edges in the given graph, n is the number of vertices, and c is the number of connected components.
Oriented matroidAn oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered. All oriented matroids have an underlying matroid.
MultiensembleUn multiensemble (parfois appelé sac, de l'anglais bag utilisé comme synonyme de multiset) est une sorte d'ensemble dans lequel chaque élément peut apparaître plusieurs fois. C'est une généralisation de la notion d'ensemble : un ensemble ordinaire est un multiensemble dans lequel chaque élément apparaît au plus une seule fois ; ce qu'impose, pour les ensembles usuels, l'axiome d'extensionnalité. On nomme multiplicité d'un élément donné le nombre de fois où il apparaît.
