Ê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
Greedoid
Résumé
In 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.
A set system (F, E) is a collection F of subsets of a ground set E (i.e. F is a subset of the power set of E). When considering a greedoid, a member of F is called a feasible set. When considering a matroid, a feasible set is also known as an independent set.
An accessible set system (F, E) is a set system in which every nonempty feasible set X contains an element x such that is feasible. This implies that any nonempty, finite, accessible set system necessarily contains the empty set ∅.
A greedoid (F, E) is an accessible set system that satisfies the exchange property:
for all with there is some such that
(Note: Some people reserve the term exchange property for a condition on the bases of a greedoid, and prefer to call the above condition the “augmentation property”.)
A basis of a greedoid is a maximal feasible set, meaning it is a feasible set but not contained in any other one. A basis of a subset X of E is a maximal feasible set contained in X.
The rank of a greedoid is the size of a basis.
By the exchange property, all bases have the same size.
Thus, the rank function is well defined. The rank of a subset X of E is the size of a basis of X. Just as with matroids, greedoids have a cryptomorphism in terms of rank functions.
A function is the rank function of a greedoid on the ground set E if and only if r is subcardinal, monotonic, and locally semimodular, that is, for any and any we have:
subcardinality:
monotonicity: whenever
local semimodularity: whenever
Most classes of greedoids have many equivalent definitions in terms of set system, language, poset, simplicial complex, and so on.
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.