Bueno, he hecho un algoritmo que no he posteado porque buscaba una demostración completa, pero ahora creo que sería mejor mostrar el algoritmo, y buscar la demo en conjunto.
1. DESCRIPCION DATOS INICIALES
Se recibe una matriz de relación por cada nivel con el inmediato superior.
Es triangular superior, pues si el nodo L1 en $niv está relacionado con el L2 en $niv+1, y L3>L1, en $niv, no puede estar relacionado con ningún nodo tal que L4 < L2, porque se cruzarían las aristas.
Esas matrices pueden representar todo grafo plano posible. Se supone sin pérdida de generalidad, que el grafo es una triangulación del plano, porque si no lo es, lo probado para la triangulación es válido para cualquier grafo que se obtenga suprimiendo aristas, pues los nodos involucrados tendrían menos relaciones, esto es, no crecería la cantidad de colores que se relacionan.
2. PLAN DE LA DEMOSTRACIÓN
El orden en que el algoritmo recorre los nodos es tal que, un nodo particular sólo está relacionado con tres nodos de orden inferior:
a) uno en el nivel inferior (siempre existe, pues de otra manera no pertenecería al nivel), SOLO HAY UNO DE ORDEN INFERIOR
b) otro en el nivel superior (eventual), y (OJO QUE PUEDE HABER 2 SI SE MARCAN ANTES LOS ENTREPISOS, pero en este caso se puede repetir un color)
c) otro en el mismo nivel, con latitud inferior. Puede tener una arista con latitud superior en el mismo nivel, y orden inferior, pero en ese caso, no tiene relaciones en el nivel superior, porque está solapado bajo una arista que relaciona un nodo de latitud inferior a la suya, con otro que tiene una latitud superior a la de él, en el mismo nivel.
Un nodo sólo puede estar relacionado con otros del nivel inmediato superior o inferior, o de su propio nivel. Supongamos que nod1 en nivel1 está relacionado con nod2 en nivel1+2. Esto significaría que hay un camino desde nod2 hasta el nodo raíz de longitud nivel1+1, con lo cual nod2 no pertenece al nivel1+2 sino a nivel1+1.
Fselect() es una función no codifica aún, que lo que tiene es una arreglo con los colores de los nodos relacionados con newnodo que tienen un orden menor. La función va tomando los colores y se fija si están en el arreglo, si es así, continúa, si no está, se lo asigna a newnodo.
El algoritmo está en awk, un lenguaje interpretado que suele usarse en Unix para procesar texto, y es similar a C.
Es algo engorroso para leer, sé que no tiene suficientes comentarios, pero para las tardes de domingo lluviosas y sin compañía, suele ser un buen rompedero de cabezas ja ja ja!
Saludos!
function explore(nodo)
{
termnod=nodo; //* termnod: si es nodo terminal, lo retorna, si no,
//* lo pisa en cada llamada
niv=nodo.nivel;
lat=nodo.latitud;
ord[nodo]=nord++;
for ( l=minlat[niv+1]; l<maxlat[niv+1]; l++ )
{
/* Exploración nivel superior */
if ( rel[niv, lat, niv+1, l]==true )
{
//* Si hay una arista entre <niv,lat> y <niv+1,l> ...
newnodo.nivel=niv+1;
newnodo.latitud=l;
minlat[niv+1]=l+1; //* No puede haber relaciones con latitud
//* menor, porque se cruzarían las aristas
if ( ord[newnodo]==null ){
//* Si newnodo aún no fué explorado...
pre[newnodo]=termnod;
sig[termnod]=newnodo; //<<@j0 * ver cómo reportar el sig.
//* del último de una rama
ord[newnodo]=nrord++;
testear_entrepiso(newnodo);
color[newnodo] = Fselect(newnodo);
termnod=explore(newnodo);
} //* Fin if ( pre[newnodo]==null )
} //* Fin if ( rel[niv, lat, niv+1, l]==true )
} //* Fin for niv+1
sig[termnod]=nodo; //* ¿Podría llegar a ser el mismo?
return(termnod);
} //* Fin explore()
testear_entrepiso( nodo )
{
/* Exploración 2do. nivel actual hasta latitud actual en ese nivel
** partiendo desde el extremo más lejano, y marcando uno solo */
/* Esto podría ir arriba por los entrepisos */
for (l=maxlat[niv+1]; l>l.punto_de_llamada+1; l--)
{
if ( rel[niv+1, lat, niv+1, l]==true &&
rel[niv, lat, niv, l]==true)
{
newnodo.nivel=niv;
newnodo.latitud=l;
//* Si newnodo aún no fué explorado...
if ( pre[newnodo]==null ){
pre[newnodo]=termnod;
sig[termnod]=newnodo; //<<@j0 * ver cómo reportar el sig.
//del último de una rama
ord[newnodo]=nrord++;
termnod=explore(newnodo);
} //* Fin if ( pre[newnodo]==null )
break; //* Hallada una arista = nivel y no adyacente, no sigue
//* explorando
} //* Fin if ( rel[niv, lat, niv, l]==true )
} //* Fin for nivel actual
}
//* Carga matriz de relación
load_matrel();
//* Nodo inicial
nodo.nivel=0;
nodo.latitud=0;
nrord=1;
//* Explora a partir del nodo origen
explore(0,0);
