Greedoid
En combinatoria , un greedoid es un tipo de sistema de conjuntos . Surge de la noción de matroide , que fue introducida originalmente por Whitney en 1935 para estudiar gráficos planares y luego fue utilizada por Edmonds para caracterizar una clase de problemas de optimización que pueden resolverse mediante algoritmos codiciosos . Alrededor de 1980, Korte y Lovász introdujeron el greedoid para generalizar aún más esta caracterización de algoritmos codiciosos; de ahí el nombre greedoid. Además de la optimización matemática , los greedoides también se han relacionado con la teoría de grafos., teoría del lenguaje, teoría del orden y otras áreas de las matemáticas .
Un sistema de conjuntos ( F , E) es una colección F de subconjuntos de un conjunto básico E (es decir, F es un subconjunto del conjunto de potencias de E). Al considerar un greedoide, un miembro de F se denomina conjunto factible . Al considerar una matroide , un conjunto factible también se conoce como conjunto independiente .
Un sistema de conjuntos accesible ( F , E) es un sistema de conjuntos en el que cada conjunto factible no vacío X contiene un elemento x tal que X \ {x} es factible. Esto implica que cualquier sistema de conjuntos accesible , finito y no vacío contiene necesariamente el conjunto vacío ∅. [1]
(Nota: Algunas personas reservan el término propiedad de intercambio para una condición sobre la base de un greedoid, y prefieren llamar a la condición anterior la "propiedad de aumento").
Una base de un greedoide es un conjunto factible máximo, lo que significa que es un conjunto factible pero no está contenido en ningún otro. Una base de un subconjunto X de E es un conjunto factible máximo contenido en X.
El rango de un greedoide es el tamaño de una base. Por la propiedad de intercambio, todas las bases tienen el mismo tamaño. Por tanto, la función de rango está bien definida . El rango de un subconjunto X de E es el tamaño de una base de X. Al igual que con las matroides, los greedoides tienen un criptomorfismo en términos de funciones de rango. [2] Una función es la función de rango de un verdoide en el conjunto básico E si y solo si es subcardinal, monótona y localmente semimodular, es decir, para cualquiera y cualquiera que tengamos
