GEOESTADISTICA.COM :: DISEÑO DE MINAS

Diseño de Minas a Cielo Abierto: Algoritmo del Bosque Subcompactado

Esta metodología fue creada por informáticos belgas, el análisis que se describe es parte de una publicación de René Vallet en la revista "Annales des Mines de Belgique". Lo interesante de este algoritmo es que también emplea la terminología y fundamentos de la teoría de grafos, pero amplía sus conceptos con nuevos términos que hacen fácil su comprensión y aplicación. A continuación se inicia con algunas definiciones de grafos.

Un grafo es conexo, si para todo par de vértices existe una cadena desde un vértice hacia el otro. Fig. 1:

Fig. 1

Fig. 2

El sub grafo A del grafo G, es un componente conexo si las dos condiciones siguientes se cumplen:

A, es conexo
No existe ninguna cadena que una un vértice desde A hacía un vértice G-A

Los diferentes componentes conexos de G constituyen una partición de G
A, es libre relativamente a G si ningún vértice de G-A es antecedente de un vértice de A. Fig. Nº 2 (3,5,2)
A, es neutro relativamente a G si ningún vértice de A es antecedente de G-A. Fig. Nº 3 (3,5,3)

Fig. 3

Fig. 4

Todo componente conexo de G es a la vez libre y neutro relativamente a G
Si dos sub grafos son libres relativamente a G, su reunión intersección diferencia es libre relativamente a G
Si el sub grafo A es libre relativamente a G y si el sub grafo B es libre relativamente a G-A, su reunión o intersección es libre relativamente a G, Fig. 4

Densidad de un sub grafo es igual a la masa del sub grafo dividido por el número de vértices que lo contiene.

Raíz de un árbol, es un vértice que se distingue de los otros porque se le define y considera como tal
Rama es un sub grafo conexo de un árbol, ligado al resto de su árbol por un solo arco
Un tronco es un sub grafo conexo de un árbol que contiene la raíz de este árbol
Rama verdadera es un sub grafo conexo cuando no contiene la raíz del árbol
Bosque subcompactado es un bosque donde todos los árboles tienen una raíz y que posee la propiedad siguiente: La densidad de toda rama libre es igual o superior a toda rama verdadera neutra
Bosque es un grafo donde cada componente es un árbol

Resolución del Algoritmo

Paso 1: A partir del grafo G = G(X, A), se construye un grafo parcial G` que es un bosque donde todos los árboles tienen una raíz y que no contienen ninguna verdadera rama neutra.

Paso 2: Seleccionar dentro de G` la rama libre A` que tenga la densidad máxima. Sea A el sub grafo de G que contiene los mismos vértices de A` . Si un vértice de j de (G-A) es antecedente de un vértice i de A, ir al paso 3.

Si A es libre relativametne a G se debe ir al paso 4.

Paso 3: Si A`es una verdadera rama, suprimir del grafo parcial G` , el arco que dentro de G une A` con (G` - A`). Si A` es un árbol entero, la raíz de este árbol pierde su calidad de raíz. Agregar el grafo parcial G` el arco que dentro de G une j con i. Regresar al paso 2.

Paso 4: El sub grafo A toma lugar dentro de la secuencia de sub grafos libres de densidad máxima. Retirar A del grafo G. Retirar A` del grafo parcial G`.

Si los dos grafos son vacios el proceso se termina. Sino se debe ir al paso 2.

Discusión del Algoritmo

El paso 1 crea un grafo parcial que es un bosque sub-compactado. Cuando se entra por primera vez en la operación 2, A` es entonces el sub-grafo libre de densidad máxima de G`.

Si A es libre dentro del grafo completo, A es el sub grafo libre de densidad máxima de G, y la operación 4, sustrayendo A de G`, crea un nuevo grafo parcial G` que es siempre un bosque sub-compactado.

Si A no es libre relativamente a G, la operación hace de A` una verdadera rama neutra creada, ella también hace un nuevo G` el cual es siempre un bosque sub-compactado.

Cualquiera que sea el camino seguido, cuando se regresa a la operación 2, el grafo parcial G` queda como un bosque sub-compactado.

Si el número de vértices que contiene G es finito, el número de grafos parciales posibles de G es un número finito. Si el algoritmo no puede generar dos veces el mismo parcial, el número de operaciones que necesitará para tratar G es un número finito. El mismo grafo parcial no será generado dos veces si la rama libre A`, una vez transformado en rama neutra por la operación 3, no puede resultar más una libre en la serie de tratamientos.

Las ramas libres de densidad máxima que la serie de tratamientos encontrará son de 3 formas:

Aquellos que son contenidos por la rama A` actual
Aquellos que no son contenidos por la rama A`actual y que no lo contienen
Aquellos que contienen la rama A` actual

Antes de resultar ramas neutras, aquellos que son contenidos dentro de A` serán separados de A` , puesto que el arco que los une a A` será suprimido por la operación 3. En este caso la rama A` actual las perderá, pero lo que quedará de A` será siempre una rama neutra.

Aquellos que no son contenidos detnro de A` y que no contienen A` resultarán ramas neutras, ya sea de A` mismo o del resto del grafo. En el primer caso, A` estará contenido en la nueva rama neutra. Este mismo será un trozo de rama ni libre ni neutro. En el segundo caso, A` quedará invariable.

Cuando aquellos que contengan A` se convierten en ramas neutras, A` estará contenida dentro de la nueva rama neutra. Según la posición del nuevo arco, A` será una rama neutra, o resultará un tronco de rama neutra. En ningún caso A` puede resultar una rama libre.

Ejemplo de Aplicación

En la Fig. Nº 5 se ilustra el problema de partida, en donde se presentan las valorizaciones de cada bloque a minar.

El primer paso (Fig. 6) es transformar este grafo G en un grafo parcial G` que es un bosque formado por árboles que poseen una raíz, sin presencia de ramas verdaderas neutras. La elección de estas raíces, para cada árbol se guía por la existencia de un vértice de alto valor que se encuentra en profundidad. No se establece otra regla de elección.

Fig. 5

Fig. 6

En este grafo parcial G` se escoge el árbol de mayor densidad Fig. 7 denominándolo A` (y en el grafo G lo denominamos A). Vemos qeu un vértice de (G - A) es antecedente de un vértice A, por lo tanto continuamos al paso 3.
En este paso, visto que A` es una verdadera rama (pues consideramos que no contiene a la raíz del grafo), suprimimos los arcos que en G unen A` con (G` - A' ). Luego agregamos en este grafo G` el arco que una (G` - A`) con la raíz de A` Fig. 8. Regresamos al paso 2.

Fig. 7

Fig. 8

En este caso repetimos la búsqueda de ramas (ó árboles) de mayor densidad. Encontramos al de densidad 7. En el cual repetimos la operación de eliminar en G` los arcos que en G unen este vértice A con (G - A). Fig. 9 y finalmente agregamos (Fig 10), el arco que una la raíz de A` (sería el mismo vértice A) con (G` - A`) pero con un arco cuyo antecedente se encuentra en (G`- A`) pero con un arco cuyo antecedente se encuentra en (G` - A`) pudiendo ser con la rama o árbol anteriormente conectada.

Fig. 9

Fig. 10

Continuamos buscando ramas o árboles de mayor densidad, y encontramos al de 5.5 (Fig. 5.7). En el cual repetimos la operación de eliminar arcos que unen la nueva rama A` con G` - A`, que existen en G, y agregar el arco que una la raíz de A` con G`- A`(Fig. 5.8).

Fig. 11

Fig. 12

A continuación encontramos al vértice A' que se muestra en la Fig. 13 con la densidad 5, resultando la Fig. 14 con las operaciones ya señaladas.

Fig. 13

Fig. 14

El siguiente paso encuentra al nuevo A, de densidad 4 (Fig. 15). Vemos en G que (G - A) no posee ningún vértice antecedente de A, por lo tanto A es libre relativamente a G y nos trasladamos al paso 4.

En el paso 4 (Fig. 16), retiramos el sub grafo A' de G' y A del grafo G. como G - A no es vacío, continuamos el proceso con el paso 2.

Fig. 15

Fig. 16

En este paso sabemos que continuamos buscando la rama A' de mayor densidad, esta vez igual a 3.5 (Fig. 17). En donde se puee trazar un arco de vértice antecedente que se encuentra en G' - A', por lo cual la rama no puede ser retirada. Fig. 18.

Fig. 17

Fig. 18

A continuación el nuevo A' se muestra en la Fig. 19. En donde A resulta libre relativamente G, pudiendo ser extraido, pues no es posible de trazar un arco cuyo vértice antecedente se encuentra en (G' - A' ). Fig. 20.