Implementación

Primeramente, se ha de decidir si una colección de subconjuntos de un conjunto dado $E=\{1,2, \dots n\}$ forma un matroide. Para esto se debe revisar que esa colección satisfaga, en efecto, los axiomas que definen a un matroide. Nótese que la cardinalidad de una colección de subconjuntos de E candidata a ser la colección de conjuntos independientes, cal I, de E, ha de tener entre 0 y 2ⁿ-1, pero este último valor puede ser muy grande cuando el orden de E crezca. Claramente, guardar toda la colección mencionada de subconjuntos de E es irrealizable. Pero afortunadamente no es necesario almacenar toda esa informacion ya que basta analizar los elementos maximales de esa colection de subconjuntos.

Una lista de conjuntos maximales independientes de un matroide ${\cal M}$ es una manera más eficiente de especificar ${\cal M}$ que una lista de todos los conjuntos independientes. Todos los demas conjuntos independientes de ${\cal M}$ se obtienen tomando todos los subconjutos de estos conjuntos maximales independientes.

Un conjunto maximal independiente de un matroide es una base en ${\cal M}$. Todas las bases de ${\cal M}$ tienen, de hecho, la misma cardinalidad, la cual se dice ser el rango del matroide. Dada una colección de subconjuntos de $E=\{1,2, \dots n\}$ de la misma cardinalidad, debemos revisar que estos conjuntos determinen un matroide. La verificación se simplifica en base a la siguiente
 

Proposición 4.1   Sea ${\cal B}$ una colección de subconjuntos de un conjunto E. Entonces ${\cal B}$ es la colección de bases de un matroide si y sólo si se satisfacen las siguientes condiciones:

(B1)

${\cal B} \neq \emptyset$

(B2)

Si B₁ y B₂ son miembros de ${\cal B}$ y $x \in B_1-B_2$, entonces existe un elemento y de B₂-B₁ tal que $B_1-x \cup y \in {\cal B}$.

En la implementación, el espacio adyacente siempre es $E=[\![1,n]\!]$ y su conjunto de partes es, en la práctica, $2^{E}\approx [\![0,2^n-1]\!]$ donde la representación en base 2 de cada número $x\in 2^{E}$ es la función característica de un conjunto $I_x\subset E$. Con esto las revisiones de la anterior proposición se hacen en complejidad O(K²) donde K es el número de bases en el matroide a probarse.
 

Dados n y k, la hipergráfica completa $K_n^{(k)}=\{x\in 2^{E}\vert x\mbox{ tiene $k$\space bits prendidos}\}$ forma un matroide llamado uniforme. Todo matroide uniforme es representable y posee como cardinalidad a un coeficiente binomial ${n\choose k}$. Los esquemas de compartición de secretos que definen son los llamados de umbral de k en n. El procedimiento para fragmentar secretos es el de Shamir [5]:

En un campo de Galois $\mbox{\it GF}(p^r)$, se considera un polinomio de grado m-1: $$F(X)=a_{m-1} X^{m-1} +\cdots +a_{1} X +a_{0}$$

y al coeficiente a₀ como el secreto (los demás coeficientes pueden ser elegidos arbitrariamente). Cada fragmento es una pareja (x,y), donde y=F(x) y, por supuesto, $x\not=0$. Cuando se tiene m puntos, el polinomio, y por tanto su coeficiente a₀, queda determinado de manera única mas m-1 puntos no son suficentes para determinarlo. Este es pues un esquema de umbral-(m,n) perfecto. En este esquema, el secreto también podría ser el valor de una función G en el vector de coeficientes $(a_{m-1}, \ldots , a_1,a_0)$.

A la fecha hemos desarrollado programas para realizar las pruebas siguientes:

• Dado ${\cal B}\subset 2^{E}$ decídase si es el conjunto de bases de un matroide.
• Dado K>0 encuéntrese todos los n y k tales que $K={n\choose k}$ enlístese a K_n^(k).
• Dado K>0, enlístese a las gráficas con exactamente K árboles generadores. Con esto se obtiene matroides gráficos
• Revisión de la representabilidad de matroides.

Los procedimientos de enlistado se transforman en procedimientos de selección aleatoria de matroides. Al generar un matroide (uniforme o gráfico) se revisa su representabilidad y tras repetir este experimento estimamos la frecuencia de matroides representables entre el total de matroides posibles. Cuando se tiene un matroide representable, se revisa si acaso su colección de conjuntos es o no ideal, de manera exhaustiva.

2000-11-28