Matroide ponderado

Existe un algoritmo sencillo para encontrar una base:

• Inicialmente dejar${\displaystyle A}$sea ​​el conjunto vacío.
• Para cada${\displaystyle x}$en${\displaystyle E}$
  • si${\displaystyle A\cup \{x\}}$es independiente, entonces establece${\displaystyle A}$a${\displaystyle A\cup \{x\}}$.

El resultado es claramente un conjunto independiente. Es un conjunto independiente maximal porque si${\displaystyle B\cup \{x\}}$no es independiente para algún subconjunto${\displaystyle B}$de${\displaystyle A}$, entonces${\displaystyle A\cup \{x\}}$Tampoco es independiente (la contrapositiva se deduce de la propiedad hereditaria ). Por lo tanto, si descartamos un elemento, nunca tendremos la oportunidad de usarlo más adelante. Generalizaremos este algoritmo para resolver un problema más complejo.

Un conjunto independiente con el mayor peso total se denomina conjunto óptimo . Los conjuntos óptimos siempre son bases, ya que si se puede añadir una arista, se debe hacer; esto solo aumenta el peso total. Resulta que existe un algoritmo voraz trivial para calcular un conjunto óptimo de un matroide ponderado. Funciona de la siguiente manera:

• Inicialmente dejar${\displaystyle A}$sea ​​el conjunto vacío.
• Para cada${\displaystyle x}$en${\displaystyle E}$, tomadas en orden (monótonamente) decreciente por peso
  • si${\displaystyle A\cup \{x\}}$es independiente, entonces establece${\displaystyle A}$a${\displaystyle A\cup \{x\}}$.

Este algoritmo encuentra una base, ya que es un caso especial del algoritmo anterior. Siempre elige el elemento de mayor peso que puede mientras preserva la independencia (de ahí el término "voraz"). Esto siempre produce un conjunto óptimo: supongamos que produce${\displaystyle A=\{e_{1},e_{2},\ldots,e_{r}\}}$y eso${\displaystyle B=\{f_{1},f_{2},\ldots ,f_{r}\}}$Ahora, para cualquier${\displaystyle k}$con${\displaystyle 1\leq k\leq r}$Consideremos conjuntos abiertos${\displaystyle O_{1}=\{e_{1},\ldots ,e_{k-1}\}}$y${\displaystyle O_{2}=\{f_{1},\ldots ,f_{k}\}}$. Desde${\displaystyle O_{1}}$es más pequeño que${\displaystyle O_{2}}$, hay algún elemento de${\displaystyle O_{2}}$que se puede colocar en${\displaystyle O_{1}}$con el resultado aún siendo independiente. Sin embargo${\displaystyle e_{k}}$es un elemento de peso máximo que se puede agregar a${\displaystyle O_{1}}$para mantener la independencia. Por lo tanto${\displaystyle e_{k}}$no tiene un peso menor que algún elemento de${\displaystyle O_{2}}$y por lo tanto${\displaystyle e_{k}}$es de al menos un gran peso como${\displaystyle f_{k}}$. Como esto es cierto para todos${\displaystyle k}$,${\displaystyle A}$es más pesado que${\displaystyle B}$.

La forma más fácil de recorrer los miembros de${\displaystyle E}$en el orden deseado es ordenarlos. Esto requiere${\displaystyle O(|E|\log |E|)}$tiempo utilizando un algoritmo de ordenación por comparación . También necesitamos probar para cada uno${\displaystyle x}$si${\displaystyle A\cup \{x\}}$es independiente; asumiendo que las pruebas de independencia requieren${\displaystyle O(f(|E|))}$tiempo, el tiempo total para el algoritmo es${\displaystyle O(|E|\log |E|+|E|f(|E|))}$.

Si en cambio queremos encontrar un árbol de expansión mínima , simplemente "invertimos" la función de peso restándola de una constante grande. Más específicamente, sea${\displaystyle w_{\text{min}}(x)=Ww(x)}$, dónde${\displaystyle W}$supera el peso total de todas las aristas del grafo. Muchos más problemas de optimización sobre todo tipo de matroides y funciones de peso pueden resolverse de esta manera tan sencilla, aunque en muchos casos se pueden encontrar algoritmos más eficientes que aprovechan propiedades más especializadas.

Nótese también que si tomamos un conjunto${\displaystyle I}$de conjuntos "independientes" que son un subconjunto pero no un matroide, entonces el algoritmo voraz no siempre funcionará. Porque entonces hay conjuntos independientes${\displaystyle I_{1}}$y${\displaystyle I_{2}}$con${\displaystyle |I_{1}|<|I_{2}|}$, pero de tal manera que para ningún${\displaystyle e\in I_{2}\setminus I_{1}}$es${\displaystyle I_{1}\cup e}$independiente.

Elige un${\displaystyle \epsilon >0}$y${\displaystyle \tau >0}$de tal manera que${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|<|I_{2}|}$. Pesar los elementos de${\displaystyle I_{1}\cup I_{2}}$en el rango${\displaystyle 2}$a${\displaystyle 2+2\epsilon }$, los elementos de${\displaystyle I_{1}\setminus I_{2}}$en el rango${\displaystyle 1+\epsilon }$a${\displaystyle 1+2\epsilon }$, los elementos de${\displaystyle I_{2}\setminus I_{1}}$en el rango${\displaystyle 1}$a${\displaystyle 1+\epsilon }$y el resto en el rango${\displaystyle 0}$a${\displaystyle \tau }$. El algoritmo voraz seleccionará los elementos de${\displaystyle I_{1}}$y luego no puede elegir ningún elemento de${\displaystyle I_{2}\setminus I_{1}}$Por lo tanto, el conjunto independiente que construye tendrá un peso como máximo de .${\displaystyle (1+2\epsilon )|I_{1}|+\tau |E|+|I_{1}\cup I_{2}|}$, que es menor que el peso de${\displaystyle I_{2}}$.