# matroid

matroid
A structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces.

Wikipedia foundation.

### Look at other dictionaries:

• Matroid — In combinatorics, a branch of mathematics, a matroid (  /ˈmeɪ …   Wikipedia

• Matroid — Ein Matroid (n.) ist eine mathematische Struktur mit deren Hilfe der Begriff der (linearen) Unabhängigkeit verallgemeinert wird. Matroide sind in vielen Bereichen der Kombinatorik (z. B. kombinatorischen Optimierung, diskrete kombinatorische… …   Deutsch Wikipedia

• Matroid intersection — In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection… …   Wikipedia

• Matroid embedding — In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties: (Accessibility Property) Every non empty feasible set X contains an element x such that X{x} is… …   Wikipedia

• matroid — …   Useful english dictionary

• Oriented matroid — theory allows a combinatorial approach to the max flow min cut theorem. A network with the value of flow equal to the capacity of an s t cut An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of… …   Wikipedia

• Bicircular matroid — In in the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B ( G ) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G , that is, the edge sets in which each …   Wikipedia

• Weighted matroid — In combinatorics, a branch of mathematics, a weighted matroid is a matroid endowed with function with respect to which one can perform a greedy algorithm.There is a simple algorithm for finding a basis:* Let A be the empty set. * For each x in E… …   Wikipedia

• Colored matroid — In mathematics, a colored matroid is a matroid whose elements are labeled from a set of colors, which can be any set that suits the purpose, for instance the set of the first n positive integers, or the sign set {+, −}. The interest in colored… …   Wikipedia

• Biased graph — In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph. A biased graph is a… …   Wikipedia