partición matroide

Subdivisión en pocos conjuntos independientes.

La partición de matroides es un problema que surge en el estudio matemático de matroides y en el diseño y análisis de algoritmos . Su objetivo es dividir los elementos de una matroide en el menor número posible de conjuntos independientes. Un ejemplo es el problema de calcular la arboricidad de un gráfico no dirigido , el número mínimo de bosques necesarios para cubrir todos sus bordes. La partición de matroides se puede resolver en tiempo polinomial , dado un oráculo de independencia para la matroide. Se puede generalizar para mostrar que una suma matroide es en sí misma una matroide, para proporcionar un algoritmo para calcular rangos y conjuntos independientes en sumas matroides, y para calcular el conjunto independiente común más grande en la intersección de dos matroides dadas. ^[1]

Ejemplo

Una partición de los bordes del gráfico bipartito completo K _4,4 en tres bosques, mostrando que tiene arboricidad como máximo tres

La arboricidad de un gráfico no dirigido es el número mínimo de bosques en los que se pueden dividir sus bordes, o de manera equivalente (agregando bordes superpuestos a cada bosque según sea necesario) el número mínimo de bosques que se extienden cuya unión es el gráfico completo. Una fórmula probada por Crispin Nash-Williams caracteriza exactamente la arboricidad: es el máximo, sobre todos los subgrafos del gráfico dado , de la cantidad . ^[2] ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \left\lceil {\frac {|E(H)|}{|V(H)|-1}}\right\rceil }$

Los bosques de un gráfico forman los conjuntos independientes de la matroide gráfica asociada , y la cantidad que aparece en la fórmula de Nash-Williams es el rango de la matroide gráfica de , el tamaño máximo de uno de sus conjuntos independientes. Por lo tanto, el problema de determinar la arboricidad de un gráfico es exactamente el problema de partición matroide para el matroide gráfico. El hecho de que los elementos de esta matroide no puedan dividirse en menos subconjuntos que independientes es entonces solo una aplicación del principio de casillero que dice que, si los elementos se dividen en conjuntos de tamaño como máximo , entonces se necesitan al menos conjuntos. La dirección más difícil de la fórmula de Nash-Williams, que puede generalizarse a todas las matroides, es la prueba de que siempre existe una partición de este tamaño. ^[1] ${\displaystyle |V(H)|-1}$ ${\displaystyle H}$ ${\displaystyle |E(H)|}$ ${\displaystyle {\frac {|E(H)|}{|V(H)|-1}}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x/y}$

Fórmula para el tamaño de la partición

Para generalizar la fórmula de Nash-Williams, se puede reemplazar por una matroide y el subgrafo de con una restricción de a un subconjunto de sus elementos. El número de aristas del subgrafo se convierte, en esta generalización, en la cardinalidad del subconjunto seleccionado, y la fórmula para el tamaño máximo de un bosque se convierte en el rango . Por lo tanto, el número mínimo de conjuntos independientes en una partición de la matroide dada debe venir dado por la fórmula ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle M|S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle H}$ ${\displaystyle |S|}$ ${\displaystyle |V(H)|-1}$ ${\displaystyle H}$ ${\displaystyle r(S)}$ ${\displaystyle M}$

${\displaystyle k(M)=\max _{S}\left\lceil {\frac {|S|}{r(S)}}\right\rceil }$.

Esta fórmula es realmente válida y Edmonds (1965) le dio una prueba algorítmica. ^{[1] [3]} En otras palabras, una matroide se puede dividir como máximo en subconjuntos independientes, si y solo si para cada subconjunto de , la cardinalidad de es como máximo . ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle k\cdot r(S)}$

Algoritmos

El primer algoritmo para la partición matroide fue propuesto por Edmonds (1965). ^[3] Es un algoritmo de ruta incremental que considera los elementos de la matroide uno por uno, en un orden arbitrario, manteniendo en cada paso del algoritmo una partición óptima para los elementos que se han considerado hasta ahora. En cada paso, al considerar un elemento que aún no ha sido colocado en una partición, el algoritmo construye un gráfico dirigido que tiene como nodos los elementos que ya han sido particionados, el nuevo elemento y un elemento especial para cada uno de los independientes. conjuntos en la partición actual. Luego forma un gráfico dirigido en este conjunto de nodos, con un arco dirigido para cada elemento matroide que se puede agregar al conjunto de particiones sin que se vuelva dependiente, y con un arco dirigido para cada par de elementos matroides de modo que al eliminarlos de su partición y reemplazándolo por formas otro conjunto independiente. ^{[1] [3]} ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \bot _{i}}$ ${\displaystyle k}$ ${\displaystyle G_{x}}$ ${\displaystyle \bot _{i}\rightarrow y}$ ${\displaystyle y}$ ${\displaystyle i}$ ${\displaystyle z\rightarrow y}$ ${\displaystyle (y,z)}$ ${\displaystyle z}$ ${\displaystyle y}$

Ahora hay dos casos:

• Si este gráfico contiene una ruta dirigida desde un elemento al elemento recién considerado , entonces la ruta más corta (o más generalmente cualquier ruta que no tenga bordes de atajo) describe una secuencia de cambios que se pueden realizar simultáneamente en los conjuntos de particiones en para formar una nueva partición, con el mismo número de conjuntos, que también incluya . En este caso, el algoritmo realiza estos cambios y continúa. ${\displaystyle \bot _{i}}$ ${\displaystyle x}$ ${\displaystyle x}$
• Si, por otro lado, no existe tal ruta, entonces consista en los elementos matroid desde los cuales se puede acceder en . Cada conjunto en la partición actual debe ser un conjunto independiente máximo en la restricción , ya que si se pudiera agregar algún elemento al conjunto de partición en la restricción, entonces existiría un arco (si el conjunto de particiones no es máximo en la partición matroide completa). ) o un arco donde (si el conjunto de particiones no es máximo pero es máximo en la matroide completa). En cualquier caso, la existencia de este arco contradice la construcción supuesta del conjunto , y la contradicción prueba que cada conjunto de partición es máximo. Por lo tanto, según la dirección sencilla de la fórmula de partición matroide, el número de conjuntos necesarios para dividir es al menos ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle D}$ ${\displaystyle M|S}$ ${\displaystyle y}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle \bot _{i}\rightarrow y}$ ${\displaystyle i}$ ${\displaystyle M}$ ${\displaystyle z\rightarrow y}$ ${\displaystyle z\notin S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

${\displaystyle \left\lceil {\frac {|S|}{r(S)}}\right\rceil =\left\lceil {\frac {kr(S)+1}{r(S)}}\right\rceil =k+1}$,

entonces, en este caso, el algoritmo puede encontrar una partición óptima colocándola en su nuevo conjunto independiente y dejando los otros conjuntos independientes sin cambios. ^{[1] [3]} ${\displaystyle x}$

El algoritmo general, entonces, considera cada elemento de la matroide dada por turno, construye el gráfico , prueba qué nodos pueden alcanzar y utiliza esta información para actualizar la partición actual para que incluya . En cada paso, la partición de los elementos considerados hasta ahora es óptima, por lo que cuando finalice el algoritmo habrá encontrado una partición óptima para toda la matroide. Demostrar que este algoritmo es correcto requiere demostrar que una ruta sin atajos en el gráfico auxiliar siempre describe una secuencia de operaciones que, cuando se realizan simultáneamente, preserva correctamente la independencia de los conjuntos en la partición; Edmonds dio una prueba de este hecho. Debido a que el algoritmo solo aumenta el número de conjuntos en la partición cuando la fórmula de partición matroide muestra que se necesita un número mayor, la corrección de este algoritmo también muestra la corrección de la fórmula. ^{[1] [3]} ${\displaystyle x}$ ${\displaystyle G_{x}}$ ${\displaystyle x}$ ${\displaystyle x}$

Aunque este algoritmo depende sólo de la existencia de un oráculo de independencia para su corrección, en muchos casos se pueden encontrar algoritmos más rápidos aprovechando la estructura más especializada de tipos específicos de matroides (como las matroides gráficas ) de las cuales se deriva un problema de partición particular. sido definido. ^[4]

Problemas relacionados

Una suma matroide (donde cada una es una matroide) es en sí misma una matroide, y tiene como elementos la unión de los elementos de los sumandos. Un conjunto es independiente en la suma si puede dividirse en conjuntos que sean independientes dentro de cada sumando. El algoritmo de partición matroide se generaliza al problema de probar si un conjunto es independiente en una suma matroide. Su exactitud se puede utilizar para demostrar que una suma matroide es necesariamente una matroide. ^{[3] [4]} Un problema extendido, que a veces también se llama partición matroide , es encontrar un conjunto más grande que sea independiente en la suma matroide, es decir, un conjunto más grande que pueda dividirse en conjuntos que sean disjuntos en cada entrada. matroide. Cunningham ^[5] presenta un algoritmo para resolver este problema en matroides de elementos O ( n ) n utilizando llamadas a un oráculo de independencia . ${\displaystyle \sum _{i}M_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle O(n^{2.5})}$

El problema de intersección de matroides es encontrar el conjunto más grande que sea independiente en dos matroides y . Puede resolverse convirtiéndolo en un problema de suma matroide equivalente: si es una base de la suma , donde es el dual de , entonces debe tener rango completo en y eliminando un conjunto independiente máximo de deja una intersección máxima. ^[6] ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle B}$ ${\displaystyle M_{1}+M_{2}^{*}}$ ${\displaystyle M_{2}^{*}}$ ${\displaystyle M_{2}}$ ${\displaystyle B}$ ${\displaystyle M_{2}^{*}}$ ${\displaystyle M_{2}^{*}}$ ${\displaystyle B}$

La partición de matroides es una forma de problema de cobertura de conjuntos , y el problema de empaquetamiento de conjuntos correspondiente (encontrar un número máximo de conjuntos de expansión disjuntos dentro de una matroide determinada) también es de interés. Puede resolverse mediante algoritmos similares a los de la partición matroide. ^[4] Los problemas de empaquetamiento y cobertura de conjuntos fraccionarios asociados con una matroide (es decir, asignar un peso a cada conjunto independiente de tal manera que para cada elemento el peso total de los conjuntos que lo contienen sea como máximo uno o al menos uno , maximizando o minimizando el peso total de todos los conjuntos, respectivamente) también se pueden resolver en tiempo polinómico utilizando métodos de partición matroide. ^[1]

Además de su uso para calcular la arboricidad de un gráfico, la partición matroide se puede utilizar con otras matroides para encontrar un subgrafo de un gráfico determinado cuyo grado promedio sea máximo y para encontrar la dureza de los bordes de un gráfico (una variante de la dureza del gráfico). que implica la eliminación de aristas en lugar de vértices). ^[1]

La partición de números restringida por Matroid es un problema diferente en el que k (el número de subconjuntos en la partición) es fijo. Hay k matroides diferentes en el mismo conjunto de terreno, y el objetivo es dividir el conjunto de terreno en k subconjuntos, de modo que cada subconjunto i sea un conjunto independiente en matroide i . Sujeto a esta restricción, se debe minimizar alguna función objetivo. En una generalización de esta variante, cada una de las k matroides tiene un peso, y la función objetivo depende de los pesos (peso máximo, peso mínimo o suma de pesos).

Referencias

1. Scheinerman, Edward R .; Ullman, Daniel H. (1997), "5. Arboricidad fraccional y métodos matroides", Teoría de grafos fraccionados , Serie Wiley-Interscience en Matemáticas discretas y optimización, Nueva York: John Wiley & Sons Inc., págs. 99-126, ISBN 0-471-17864-0, SEÑOR  1481157.
2. Nash-Williams, C. St. JA (1964), "Descomposición de gráficos finitos en bosques", Revista de la Sociedad Matemática de Londres , 39 (1): 12, doi :10.1112/jlms/s1-39.1.12, MR  0161333.
3. Edmonds, Jack (1965), "Partición mínima de una matroide en subconjuntos independientes" (PDF) , Revista de investigación de la Oficina Nacional de Estándares , 69B : 67–72, doi : 10.6028/jres.069b.004 , SEÑOR  0190025.
4. Gabow, Harold N .; Westermann, Herbert H. (1992), "Bosques, marcos y juegos: algoritmos para sumas y aplicaciones matroides", Algorithmica , 7 (5–6): 465–497, doi :10.1007/BF01758774, SEÑOR  1154585.
5. Cunningham, William H. (1 de noviembre de 1986). "Límites mejorados para algoritmos de intersección y partición matroide". Revista SIAM de Computación . 15 (4): 948–957. doi :10.1137/0215066. ISSN  0097-5397.
6. Edmonds, Jack (1970), "Funciones submodulares, matroides y ciertos poliedros", Estructuras combinatorias y sus aplicaciones (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) , Nueva York: Gordon y Breach, págs. 69–87, SEÑOR  0270945.