Partición matroide
La partición matroide es un problema que surge en el estudio matemático de las matroides y en el diseño y análisis de algoritmos . Su objetivo es dividir los elementos de un 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 matroide puede resolverse 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]
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 extensos cuya unión es el gráfico completo. Una fórmula probada por Crispin Nash-Williams caracteriza exactamente la arboricidad: es el máximo, en todos los subgrafos del gráfico dado , de la cantidad . [2]
Los bosques de un gráfico forman los conjuntos independientes del matroide gráfico asociado , y la cantidad que aparece en la fórmula de Nash-Williams es el rango del matroide gráfico 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 este matroide no se puedan dividir en menos de subconjuntos 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 al menosSe necesitan conjuntos. La dirección más dura 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]
