En la teoría matemática de las matroides , el rango de una matroide es el tamaño máximo de un conjunto independiente en la matroide. El rango de un subconjunto S de elementos del matroide es, de manera similar, el tamaño máximo de un subconjunto independiente de S , y la función de rango del matroide asigna conjuntos de elementos a sus rangos.
La función de rango es uno de los conceptos fundamentales de la teoría matroide a través del cual se pueden axiomatizar las matroides. Las funciones de rango matroide forman una subclase importante de las funciones de conjuntos submodulares . Las funciones de rango de las matroides definidas a partir de ciertos otros tipos de objetos matemáticos, como gráficos no dirigidos , matrices y extensiones de campo, son importantes dentro del estudio de esos objetos.
Ejemplos de
En todos los ejemplos, E es el conjunto base de la matroide, y B es un subconjunto de E .
- Deje que M sea el matroide libre , donde los conjuntos independientes son todos los subconjuntos de E . Entonces la función de rango de M es simplemente: r ( B ) = | B |.
- Sea M un matroide uniforme , donde los conjuntos independientes son los subconjuntos de E con como máximo k elementos, para algún número entero k . Entonces la función de rango de M es: r ( B ) = min ( k , | B |).
- Sea M una matroide de partición : los elementos de E están divididos en categorías, cada categoría c tiene capacidad k c , y los conjuntos independientes son aquellos que contienen como máximo k c elementos de la categoría c . Entonces, la función de rango de M es: r ( B ) = suma c min ( k c , | B c |) donde B c es el subconjunto B contenido en la categoría c .
- Sea M una matriz gráfica , donde los conjuntos independientes son todos los conjuntos de bordes acíclicos ( bosques ) de algún gráfico G fijo no dirigido . Entonces, la función de rango r ( B ) es el número de vértices en la gráfica, menos el número de componentes conectados de B (incluidos los componentes de un solo vértice).
Propiedades y axiomatización
La función de rango de un matroide obedece a las siguientes propiedades.
(R1) El valor de la función de rango es siempre un número entero no negativo .
(R2) Para dos subconjuntos cualesquiera y de , . Es decir, el rango es una función de conjunto submodular .
(R3) Para cualquier conjunto y elemento , .
Estas propiedades pueden usarse como axiomas para caracterizar la función de rango de las matroides: cada función de conjunto submodular con valores enteros en los subconjuntos de un conjunto finito que obedece a las desigualdades para todos y es la función de rango de un matroide. [1] [2]
Las propiedades anteriores implican propiedades adicionales:
- Si , luego . Es decir, el rango es una función monótona .
- .
Otras propiedades matroides del rango
La función de rango puede usarse para determinar las otras propiedades importantes de un matroide:
- Un conjunto es independiente si y solo si su rango es igual a su cardinalidad, y depende si y solo si tiene mayor cardinalidad que rango. [3]
- Un conjunto no vacío es un circuito si su cardinalidad es igual a uno más su rango y cada subconjunto formado al eliminar un elemento del conjunto tiene el mismo rango. [3]
- Un conjunto es una base si su rango es igual a su cardinalidad y al rango del matroide. [3]
- Un conjunto es cerrado si es máximo para su rango, en el sentido de que no existe otro elemento que se le pueda agregar manteniendo el mismo rango.
- La diferencia se llama la nulidad del subconjunto. Es el número mínimo de elementos que se deben eliminar depara obtener un conjunto independiente. [4]
- La corank de un subconjunto puede referirse a al menos dos cantidades diferentes: algunos autores lo usan para referirse al rango de en el matroide dual, , mientras que otros autores usan corank para referirse a la diferencia .
Rangos de matroides especiales
En teoría de grafos , el rango de circuito (o número ciclomático) de un grafo es el corango del matroide gráfico asociado ; mide el número mínimo de bordes que deben eliminarse del gráfico para que los bordes restantes formen un bosque. [5] Varios autores han estudiado la complejidad parametrizada de los algoritmos de gráficos parametrizados por este número. [6] [7]
En álgebra lineal , el rango de un matroide lineal definido por la independencia lineal de las columnas de una matriz es el rango de la matriz, [8] y también es la dimensión del espacio vectorial atravesado por las columnas.
En álgebra abstracta , el rango de un matroide definido a partir de conjuntos de elementos en una extensión de campo L / K por independencia algebraica se conoce como grado de trascendencia . [9]
El rango de Matroid funciona como funciones de utilidad
Las funciones de rango matroide (MRF) se han utilizado para representar funciones de utilidad de agentes en problemas de asignación justa de artículos . Si la función de utilidad del agente es un MRF, significa que:
- La utilidad del agente tiene rendimientos decrecientes (esto se deriva del hecho de que el MRF es una función submodular);
- La utilidad marginal del agente para cada artículo es dicotómica (binaria): 0 o 1. Es decir, agregar un artículo a un paquete no agrega utilidad o agrega una utilidad de 1.
Las siguientes soluciones son conocidas para esta configuración:
- Babaioff, Ezra y Feige [10] diseñan un mecanismo veraz determinista en tiempo polinomial llamado Igualitario priorizado, que genera una asignación dominante de Lorenz, que en consecuencia también es EFX 0 , maximiza el producto de las utilidades, alcanza la participación máxima de 1/2 fracción y alcanza la máxima participación cuando las valoraciones son aditivas. Con prioridades aleatorias, este mecanismo también está exento de envidia ex ante . También estudian valoraciones e- dicotómicas, en las que la utilidad marginal es no positiva o está en el rango [1,1+ e ].
- Benabbou, Chakraborty, Igarashi y Zick [11] muestran que, en este contexto, cada asignación óptima de Pareto maximiza la suma de utilidades (el bienestar utilitario ), el conjunto de asignaciones que maximizan una función simétrica estrictamente cóncava f sobre todos los valores máximos. La suma de asignaciones no depende de la elección de f , y todas estas asignaciones que maximizan f son EF1. Esto implica que las asignaciones de producto máximo son las asignaciones óptimas leximin , y todas son suma máxima y EF1. También presentan un algoritmo de tiempo polinomial que calcula una asignación de suma máxima y EF1 (que no necesariamente maximiza una función cóncava) y un algoritmo de tiempo polinomial que maximiza una función cóncava para el caso especial de MRF basado en la cardinalidad máxima. coincidencia en gráficos bipartitos.
Las funciones de rango matroide son una subclase de las valoraciones sustitutivas brutas .
Ver también
- Oráculo de rango
Referencias
- ^ Shikare, MM; Waphare, BN (2004), Optimización combinatoria , Alpha Science Int'l Ltd., p. 155, ISBN 9788173195600.
- ^ Galés, DJA (2010), Matroid Theory , Publicaciones de Courier Dover, p. 8, ISBN 9780486474397.
- ↑ a b c Oxley (2006) , p. 25.
- ^ Oxley (2006) , p. 34.
- ^ Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs , Publicaciones de Courier Dover, págs. 27-30, ISBN 9780486419756.
- ^ Calderero, Don ; Vishkin, Uzi (1985), "Resolver problemas NP-difíciles en 'casi árboles': cobertura de vértices", Matemáticas aplicadas discretas , 10 (1): 27–45, doi : 10.1016 / 0166-218X (85) 90057-5 , Zbl 0573.68017.
- ^ Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), "Complejidad de parámetros fijos de las etiquetas λ", Matemáticas aplicadas discretas , 113 (1): 59–72, doi : 10.1016 / S0166-218X (00) 00387-5 , Zbl 0982.05085.
- ^ Oxley, James G. (2006), Teoría Matroide , Textos de Posgrado en Matemáticas de Oxford , 3 , Oxford University Press, p. 81, ISBN 9780199202508.
- ^ Lindström, B. (1988), "Matroides, algebraicos y no algebraicos", combinatoria algebraica, extremal y métrica, 1986 (Montreal, PQ, 1986) , London Math. Soc. Lecture Note Ser., 131 , Cambridge: Cambridge Univ. Prensa, págs. 166-174, MR 1052666.
- ^ Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (27 de julio de 2020). "Mecanismos justos y veraces para valoraciones dicotómicas". arXiv : 2002.10704 [ cs.GT ].
- ^ Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). Encontrar asignaciones justas y eficientes cuando las valoraciones no cuadran . Apuntes de conferencias en Ciencias de la Computación. 12283 . págs. 32–46. arXiv : 2003.07060 . doi : 10.1007 / 978-3-030-57980-7_3 . ISBN 978-3-030-57979-1. S2CID 208328700 .