computación - Tienda de ultramarinos
logo Tienda de Ultramarinos
Etiquetas: computación

Máximo número de aristas en digrafo de diametro D

Breve introducción o repaso

Un grafo es una estructura compuesta por nodos unidos por aristas (edges, en inglés). En teoría de grafos, se denomina grafo completo K_n a aquel que cada uno de sus n nodos tiene una conexión con cada uno de los otros n-1 nodos.

El número de aristas en estos grafos es siempre E(K_n) = \frac{n (n-1)}{2}, que coincide con la suma de enteros de 1 hasta n. Esto se ve claramente dibujando un K_n en una hoja de papel. Primero pones los n nodos, luego tomas cada uno y dibujas todas las aristas que lo unen con el resto, n-1. Cuando lo hagas con el siguiente sólo podrás pintar n-2, con el siguiente n-3, etc.

En un grafo normal, las aristas son bidireccionales, pero hoy vamos a trabajar los grafos dirigidos o digrafos, donde cada arista va acompañada de una flecha que indica la única dirección posible que se puede tomar. Así, el número de aristas en un digrafo dirigido será el doble que en el mismo normal, por lo que:

 E(k) = n^2 - n = n(n-1)

Para simplificar los siguientes dibujos (todos de digrafos), asumiremos que las aristas sin flecha son bidireccionales, valen por dos, y las dibujadas con flecha indicarán la única dirección posible. De ese modo, los dos siguientes grafos dirigidos son equivalentes.

El número de nodos que hay que atravesar para ir de uno a otro se llama distancia. Si medimos la distancia de cada nodo a todos los demás y tomamos el valor máximo, tenemos el diámetro del grafo. En un grafo completo, el diámetro siempre es 1. En el las imágenes de encima, el diámetro es 2.

¿Cuál es el número máximo de aristas que puede tener un digrafo de diámetro D?

A estos grafos les llamaremos K_n^d, donde n es el número de nodos y d el diámetro. Así K_6^3 es el grafo de diámetro 3 y 6 nodos con el mayor número de aristas posibles entre ellos. Además, utilizaremos la función E(G) para contar el número de aristas en el grafo G.

\exists i,j \in K_n^d\Rightarrow distance(i,j)

Voy a poner los ejemplos con K_5^d, pero para seguir mejor los resultados, estaría bien que antes de continuar cogieras papel y lápiz y tratases de solucionar los grafos con 3 y 4 nodos, que son muy sencillos: K_3^2, K_4^2 K_4^3

D=1, es el caso trivial, K_n^1 = K_n por lo que E(K_n^1)=n^2 - n.

Para K_n^2, simplemente tenemos que tomar K_n^1, y eliminar cualquier arista en una dirección, dejándola en la otra. En la siguiente imagen se puede ver que para ir de A a E hemos de pasar obligatoriamente por otro nodo, teniendo así el diametro igual a dos que necesitábamos. Así pues, E(K_n^2)=n^2 - n - 1.

La estrategia a partir de ahora es clara, “aislar” dos nodos de forma que en una dirección siempre sea necesario recorrer los suficientes como para justificar el diámetro. La otra dirección no hay que “cerrarla”, ya que únicamente hacen falta un par de nodos con distancia igual a diametro, y el resto son aristas extra que se suman a la cuenta.

Con K_5^2, hemos visto que los recorridos posibles para llegar de A a E eran pasando por B, C ó D, sin embargo ahora necesitamos un salto más. Para ello, “cerramos” todas las entradas a E, salvo por D. Ahora simplemente prohibimos a A moverse directamente a D, teniendo que ir a través de B ó C. Así, al total de aristas E(K_5^1) =  n^2 - n le hemos quitado cuatro, quedando: E(K_5^3) = 5^2 - 5 - 4 = 16. También podemos decir que a K_5^2 le quitamos tres aristas.

Repetimos el mismo proceso para K_5^4=, que es el último para cinco nodos y donde lo que finalmente hemos conseguido es que de A a E sólo se pueda ir por el camino ABCDE. Para ello simplemente hemos tenido que quitarle dos aristas a E(K_5^3) E(K_5^4)= 16 -2 = 14.

K_5^d termina aquí, pero si hacemos esto con grafos mayores veremos claramente un patrón que se repite: (los paréntesis no son necesarios, sólo para visualizarlo más claro).

 E(K_n^1) = n^2 - n
 E(K_n^2) = (n^2 - n)  -1
 E(K_n^3) = (n^2 - n) - (n - 2) -1 = n^2 - 2n + 1
 E(K_n^4) = (n^2 - n) - (n - 2) - (n - 3) - 1 = n^2 - 3n + 4
 E(K_n^5) = (n^2 - n) - (n - 2) - (n - 3) - (n -4) - 1 = n^2 - 4n + 8
 E(K_n^d) = E(K_n^{d-1}) - (n - ( d - 1))
 E(K_n^d) = n^2 - (d-1) \cdot n + \frac{d\cdot (d-1)}{2} -2

En realidad, K_n^1 es K_n y no se puede tratar con la misma ecuación genérica que el resto, por lo que K_n^d sólo funciona para d\ge2.

Por otro lado, el caso específico K_n^{n-1} se puede solucionar mediante otra aproximación, de igual forma para todos los grafos. Primero, sabemos que la solución constará de un único camino bidireccional que recorra todos los nodos (lo cual es además un camino hamiltoniano). Esto es 2(n-1). El número de aristas es n-1, que valen doble porque son bidireccionales. Veamos el ejemplo con cinco y seis nodos.

Ahora simplemente tenemos que rellenar los huecos del grafo con aristas en la dirección correcta. ¿Cuántas son? Pues fácil, el total de aristas de Kn menos n-1, que son las que acabamos de pintar.

 E(K_n) - (n-1) = \frac{n\cdot (n-1)}{2}-(n-1)

Lo cual, se lo sumamos a lo que ya teníamos y queda:

 E(K_n^{n-1}) = 2\cdot (n-1) +  \frac{n\cdot (n-1)}{2}-(n-1) = \frac{n^2+n-2}{2}

Si tomamos el caso general E(K_n^d) y sustituimos d=n-1, veremos que llegamos exactamente a la función E(K_n^{n-1}). Si bien dije previamente que K_n^d no funciona para d=1, esta nueva ecuación sí que respeta ese caso. Si despejamos n en E(K_n^1) = n^2 - n = \frac{n^2+n-2}{2} = E(K_n^{n-1}) sale una ecuación de segundo grado con raíces en 1 y 2; nos nos interesa la segunda puesto que estábamos considerando d=n-1 y demuestra que la igualdad es correcta. También es mucho más sencillo directamente sustituir n=2 en ambas fórmulas y ver que el resultado es el mismo, 2. El cual es exactamente el número de aristas en un digrafo de dos nodos y diámetro uno.

También podemos tomar valores específicos y comprobar que obtenemos el mismo resultado, por ejemplo:

 E(K_n^4) =  n^2 - 3n + 4
 E(K_5^4) = 5^2 - 3\cdot 5 + 4 = 25 - 15 + 4 =14
 E(K_n^{n-1}) = \frac{n^2+n-2}{2}
 E(K_5^{4}) = \frac{5^2+5-2}{2} = \frac{25 + 5 - 2}{2} = 14

¿Aplicaciones prácticas de este resultado?

En la asignatura Distributed System estamos estudiando algoritmos para seleccionar el nodo líder de una red, figura necesaria en muchas ocasiones para coordinar algoritmos distribuidos. Cada nodo tiene un identificador distinto del resto, así que la selección del líder se puede hacer bien con el que tenga el mayor ID o el que tenga el menor (para lo cual éste ha de pasar por todos los nodos).

Existen muy diversos algoritmos para comunicar el ID entre los participantes, difiriendo todos ellos en el número de rondas necesarias y de mensajes enviados. Es una asignatura a nivel teórico en la que tenemos que analizar la complejidad temporal y computacional (número de mensajes), distinguiendo mejor caso, peor, y comportamiento medio.

Un algoritmo muy simple es FloodMax, en el cual la complejidad es linear. Dura tantas rondas como el diámetro de la red, y en cada ronda cada nodo envía a todos sus vecinos el máximo valor ID que ha recibido hasta entonces. Así pues, el número de mensajes es simplemente el número de aristas por el diámetro.

Un par de clases después de esto, estaba lo suficientemente aburrido como para pensar en el peor caso de una red de tamaño N, para lo cual el primer paso era saber el máximo número de aristas posibles con cada diámetro existente.

Entonces, para saber el número de mensajes en una red de n nodos con diametro d, se hace msg = d \cdot E(K_n^d) y listo. He hecho un pequeño programita para calcular y mostrar estos valores (Graph.java y Graph.class). Ejecutando “java Graph -v N” imprime información detallada de cada diámetro, y con “java Graph N” escribe sólo los resultados para los cuales el número de mensajes es el mayor.

En realidad, la guinda del pastel sería resolver el problema de optimización para maximizar el valor msg = d \cdot E(K_n^d) \quad \forall d, 1 \le d < n[/latex] pero hasta ahí ya no llego. Consulté ayer a un amigo matemático que finalmente demostró que el máximo valor es siempre en [latex]E(K_n^{n-1})[/latex] y pese a que me indicó algunos de los pasos, no he sido capaz de reproducirlos. Si alguien se anima, [latex]\LaTeX[/latex] está activado también en los comentarios, utilizando $ latex fórmula $ , sin espacio entre “$” y “latex“.

Why work toward the Singularity?

«If you travelled backward in time to witness a critical moment in the invention of science, or the creation of writing, or the evolution of Homo sapiens, or the beginning of life on Earth, no human judgement could possibly encompass all the future consequences of that event – and yet there would be the feeling of being present at the dawn of something worthwhile. The most critical moments of history are not the closed stories, like the start and finish of wars, or the rise and fall of governments. The story of intelligent life on Earth is made up of beginnings. Imagine traveling back in time to witness a critical moment in the dawn of human intelligence. Suppose that you find an alien bystander already on the scene, who asks: “Why are you so excited? What does it matter?” The question seems almost impossible to answer; it demands a thousand answers, or none. […]

The beginnings of human intelligence, or the invention of writing, probably went unappreciated by the individuals who were present at the time. But such developments do not always take their creators unaware. […]

In one sense, asking what specific problems will be solved is like asking Benjamin Franklin in the 1700s to predict electronic circuitry, computers, Artificial Intelligence, and the Singularity on the basis of his experimentation with electricity.»

Why work toward the Singularity?

Tema bastante interesante el que plantea la hipótesis de la Singularidad Tecnológica. Lo descubrí hace unos días en Microsiervos y tenía un par de documentos aparcados para cuando sacara algo de tiempo. Qué mejor que mientras me desperezo con un café antes de ponerme a estudiar Arquitectura de Ordenadores I. Se basa un poco en La ley de Moore (duplicación de capacidad de cálculo cada dos años de trabajo) y parte del momento en que las Inteligencias Artificiales alcancen la capacidad humana y sean “quienes” investiguen. Entonces a los dos años se duplicaría su capacidad, reduciendo a un año el tiempo en conseguir duplicar la misma, con lo que un año después la duplicarían de nuevo, reduciendo a seis meses el intervalo de trabajo. Así hasta llegar a un punto de no retorno en el que nos es imposible predecir qué ocurrirá.

Como habrá observado cualquiera un poco interesado por la astrofísica, el nombre viene del propio concepto homónimo de la misma.