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 .
Definiciones
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]
Un greedoid ( F , E) es un sistema de conjuntos accesible que satisface la propiedad de intercambio :
- para todo X, Y ∈ F con | X | > | Y |, hay algo de x ∈ X \ Y tal que Y∪ {x} ∈ F
(Nota: Algunas personas reservan el término propiedad de intercambio para una condición sobre la base de un greenid, 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 greedoide en el suelo conjunto E si y solo si es subcardinal, monótona y localmente semimodular, es decir, para cualquier y cualquier tenemos
- subcardinalidad :;
- monotonicidad : cuando sea ; y
- semimodularidad local : cuando sea .
Clases
La mayoría de las clases de greedoides tienen muchas definiciones equivalentes en términos de sistema de conjuntos, lenguaje, poset, complejo simplicial , etc. La siguiente descripción toma la ruta tradicional de enumerar solo un par de las caracterizaciones más conocidas.
Un verdoide de intervalo ( F , E) es un verdoide que satisface la propiedad de intervalo :
- si A, B, C ∈ F con A ⊆ B ⊆ C, entonces, para todo x ∈ E \ C, (A∪ {x} ∈ F y C∪ {x} ∈ F ) implica B∪ {x} ∈ F
De manera equivalente, un verdoide de intervalo es un verdoide tal que la unión de dos conjuntos factibles cualesquiera es factible si está contenido en otro conjunto factible.
Un antimatroide ( F , E) es un verdeide que satisface la propiedad de intervalo sin límites superiores :
- si A, B ∈ F con A ⊆ B, entonces, para todo x ∈ E \ B, A∪ {x} ∈ F implica B∪ {x} ∈ F
De manera equivalente, un antimatroide es (i) un greedoide con una base única; o (ii) un sistema de plató accesible cerrado bajo unión. Es fácil ver que un antimatroide es también un verdoide de intervalo.
Un matroid ( F , E) es un greedoid no vacío que satisface la propiedad de intervalo sin límites inferiores :
- si B, C ∈ F con B ⊆ C, entonces, para todo x ∈ E \ C, C∪ {x} ∈ F implica B∪ {x} ∈ F
Es fácil ver que una matroide es también una greedoide de intervalo.
Ejemplos de
- Considere un gráfico no dirigido G. Sea el conjunto de suelo los bordes de G y los conjuntos factibles el conjunto de bordes de cada bosque (es decir, un subgrafo que no contiene ciclo) de G. Este sistema de conjuntos se llama ciclo matroide . Se dice que un sistema de conjuntos es una matroide gráfica si es la matroide cíclica de algún gráfico. (Originalmente, el ciclo matroide se definía en circuitos , o conjuntos dependientes mínimos . De ahí el nombre ciclo).
- Considere una gráfica G finita, no dirigida, con raíz en el vértice r. Sea el conjunto de suelo los vértices de G y los conjuntos factibles los subconjuntos de vértices que contienen r que inducen subgráficos conectados de G. Esto se llama la búsqueda de vértices greedoid y es una especie de antimatroide.
- Considere una gráfica D finita y dirigida con raíz en r. Sea el conjunto de suelo los bordes (dirigidos) de D y los conjuntos factibles los conjuntos de bordes de cada subárbol dirigido enraizado en r con todos los bordes apuntando en dirección opuesta a r. Esto se denomina greedoid de búsqueda de línea o greedoid de ramificación dirigida . Es un greedoide de intervalo, pero no es un antimatroide ni un matroide.
- Considere una matriz m-por-n M. Sea el conjunto básico E los índices de las columnas de 1 an y los conjuntos factibles sean F = {X ⊆ E: submatriz M {1, ..., | X |} , X es una matriz invertible }. A esto se le llama el verdoide de eliminación de Gauss porque esta estructura subyace al algoritmo de eliminación de Gauss . Es un greedoid, pero no un greedoid de intervalo.
Algoritmo codicioso
En general, un algoritmo codicioso es solo un proceso iterativo en el que se elige la mejor opción local , generalmente una entrada de peso máximo, en cada ronda hasta que se hayan agotado todas las opciones disponibles. Para describir una condición basada en greedoides en la que un algoritmo codicioso es óptimo (es decir, obtiene una base de valor máximo), necesitamos algunas terminologías más comunes en la teoría de greedoides. Sin pérdida de generalidad , consideramos un greedoide G = ( F , E) con E finito.
Un subconjunto X de E tiene rango factible si la intersección más grande de X con cualquier conjunto factible tiene un tamaño igual al rango de X. En un matroide, cada subconjunto de E es rango factible. Pero la igualdad no es válida para los greedoides en general.
Una función w: E → ℝ es R -compatible si {x ∈ E: w (x) ≥ c} tiene rango factible para todos los números reales c.
Una función objetivo f: 2 S → ℝ es lineal sobre un conjunto S si, para todo X ⊆ S, tenemos f (X) = Σ x ∈ X w (x) para alguna función de peso w: S → ℜ.
Proposición. Un algoritmo codicioso es óptimo para cada función de objetivo lineal compatible con R sobre un greenid.
La intuición detrás de esta proposición es que, durante el proceso iterativo, cada intercambio óptimo de peso mínimo es posible gracias a la propiedad de intercambio, y se pueden obtener resultados óptimos a partir de los conjuntos factibles en el greedoide subyacente. Este resultado garantiza la optimización de muchos algoritmos conocidos. Por ejemplo, se puede obtener un árbol de expansión mínimo de un gráfico ponderado utilizando el algoritmo de Kruskal , que es un algoritmo codicioso para el ciclo matroide. El algoritmo de Prim se puede explicar tomando la búsqueda de vértices greedoid en su lugar.
Ver también
Referencias
- ^ Tenga en cuenta que la propiedad de accesibilidad es estrictamente más débil que la propiedad hereditaria de un matroide , que requiere que cada subconjunto de un conjunto independiente sea independiente.
- ^ Björner, Anders ; Ziegler, Günter M. (1992), "8. Introduction to greedoids" , en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge: Cambridge University Press, págs. 284–357 , doi : 10.1017 / CBO9780511662041.009 , ISBN 0-521-38165-7, MR 1165537 , Zbl 0.772,05026
- Björner, Anders ; Ziegler, Günter M. (1992), "8. Introduction to greedoids" , en White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge: Cambridge University Press, págs. 284–357 , doi : 10.1017 / CBO9780511662041.009 , ISBN 0-521-38165-7, MR 1165537 , Zbl 0.772,05026
- Edmonds, Jack (1971), "Matroids y el algoritmo codicioso", Programación matemática , 1 : 127-136, doi : 10.1007 / BF01584082 , S2CID 5599224 , Zbl 0253.90027.
- Helman, Paul; Moret, Bernard ME; Shapiro, Henry D. (1993), "Una caracterización exacta de las estructuras codiciosas", SIAM Journal on Discrete Mathematics , 6 (2): 274-283, CiteSeerX 10.1.1.37.1825 , doi : 10.1137 / 0406021 , Zbl 0798.68061.
- Korte, Bernhard ; Lovász, László (1981), "Estructuras matemáticas subyacentes a algoritmos codiciosos", en Gecseg, Ferenc (ed.), Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, 24-28 de agosto de 1981 , Conferencia Notes in Computer Science, 117 , Berlín: Springer-Verlag , págs. 205-209, doi : 10.1007 / 3-540-10854-8_22 , Zbl 0473.68019.
- Korte, Bernhard; Lovász, László ; Schrader, Rainer (1991), Greedoids , Algorithms and Combinatorics, 4 , Nueva York, Berlín: Springer-Verlag , ISBN 3-540-18190-3, Zbl 0733.05023.
- Oxley, James G. (1992), teoría matroide , publicaciones científicas de Oxford, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl 0784.05002.
- Whitney, Hassler (1935), "Sobre las propiedades abstractas de la independencia lineal", American Journal of Mathematics , 57 (3): 509–533, doi : 10.2307 / 2371182 , hdl : 10338.dmlcz / 100694 , JSTOR 2371182 , Zbl 0012.00404.
enlaces externos
- Introducción a Greedoids
- Teoría de los algoritmos codiciosos
- Funciones submodulares y optimización
- Emparejamientos, matrices y funciones submodulares