{"id":1874,"date":"2010-10-19T02:07:25","date_gmt":"2010-10-19T00:07:25","guid":{"rendered":"http:\/\/www.tiendadeultramarinos.es\/?p=1874"},"modified":"2011-05-13T17:21:05","modified_gmt":"2011-05-13T15:21:05","slug":"maximo-numero-de-aristas-en-digrafo-de-diametro-d","status":"publish","type":"post","link":"https:\/\/www.tiendadeultramarinos.es\/?p=1874","title":{"rendered":"M\u00e1ximo n\u00famero de aristas en digrafo de diametro D"},"content":{"rendered":"

Breve introducci\u00f3n o repaso<\/h2>\n

Un grafo es una estructura compuesta por nodos unidos por aristas (edges<\/em>, en ingl\u00e9s). En teor\u00eda de grafos<\/a>, se denomina grafo completo<\/a> K_n a aquel que cada uno de sus n<\/em> nodos tiene una conexi\u00f3n con cada uno de los otros n-1<\/em> nodos.<\/p>\n

El n\u00famero 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<\/em>. 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<\/em>. Cuando lo hagas con el siguiente s\u00f3lo podr\u00e1s pintar n-2<\/em>, con el siguiente n-3<\/em>, etc.<\/p><\/a>

\n

En un grafo normal, las aristas son bidireccionales, pero hoy vamos a trabajar los grafos dirigidos<\/a> o digrafos, donde cada arista va acompa\u00f1ada de una flecha que indica la \u00fanica direcci\u00f3n posible que se puede tomar. As\u00ed, el n\u00famero de aristas en un digrafo dirigido ser\u00e1 el doble que en el mismo normal, por lo que:<\/p>\n

\n E(k) = n^2 - n = n(n-1)\n<\/p>\n

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\u00e1n la \u00fanica direcci\u00f3n posible. De ese modo, los dos siguientes grafos dirigidos son equivalentes.<\/p>\n

\n\"\"\"\"<\/div>\n

El n\u00famero 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\u00e1s y tomamos el valor m\u00e1ximo, tenemos el di\u00e1metro<\/strong> del grafo. En un grafo completo, el di\u00e1metro siempre es 1. En el las im\u00e1genes de encima, el di\u00e1metro es 2.<\/p>\n

\u00bfCu\u00e1l es el n\u00famero m\u00e1ximo de aristas que puede tener un digrafo de di\u00e1metro D?<\/h2>\n

A estos grafos les llamaremos K_n^d, donde n<\/em> es el n\u00famero de nodos y d<\/em> el di\u00e1metro. As\u00ed K_6^3 es el grafo de di\u00e1metro 3 y 6 nodos con el mayor n\u00famero de aristas posibles entre ellos. Adem\u00e1s, utilizaremos la funci\u00f3n E(G) para contar el n\u00famero de aristas en el grafo G<\/em>.<\/p>\n

\n\\exists i,j \\in K_n^d\\Rightarrow distance(i,j)\n<\/p>\n

Voy a poner los ejemplos con K_5^d, pero para seguir mejor los resultados, estar\u00eda bien que antes de continuar cogieras papel y l\u00e1piz y tratases de solucionar los grafos con 3 y 4 nodos, que son muy sencillos: K_3^2, K_4^2 K_4^3<\/p>\n

\nD=1, es el caso trivial, K_n^1 = K_n por lo que E(K_n^1)=n^2 - n.\n<\/p>\n

Para K_n^2, simplemente tenemos que tomar K_n^1, y eliminar cualquier arista en una direcci\u00f3n, dej\u00e1ndola 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\u00ed el diametro igual a dos que necesit\u00e1bamos. As\u00ed pues, E(K_n^2)=n^2 - n - 1.<\/p>\n

\"\"<\/p>\n

La estrategia a partir de ahora es clara, \u00abaislar\u00bb dos nodos de forma que en una direcci\u00f3n siempre sea necesario recorrer los suficientes como para justificar el di\u00e1metro<\/strong>. La otra direcci\u00f3n no hay que \u00abcerrarla\u00bb, ya que \u00fanicamente hacen falta un par de nodos con distancia igual a diametro, y el resto son aristas extra que se suman a la cuenta.<\/p>\n

Con K_5^2, hemos visto que los recorridos posibles para llegar de A a E eran pasando por B, C \u00f3 D, sin embargo ahora necesitamos un salto m\u00e1s. Para ello, \u00abcerramos\u00bb todas las entradas a E, salvo por D. Ahora simplemente prohibimos a A moverse directamente a D, teniendo que ir a trav\u00e9s de B \u00f3 C. As\u00ed, 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\u00e9n podemos decir que a K_5^2 le quitamos tres aristas.<\/p>\n

\n\"\"<\/p>\n

Repetimos el mismo proceso para K_5^4=, que es el \u00faltimo para cinco nodos y donde lo que finalmente hemos conseguido es que de A a E s\u00f3lo 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.<\/p>\n

\n\"\"\n<\/p>\n

K_5^d termina aqu\u00ed, pero si hacemos esto con grafos mayores veremos claramente un patr\u00f3n que se repite: (los par\u00e9ntesis no son necesarios, s\u00f3lo para visualizarlo m\u00e1s claro).<\/p>\n

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

En realidad, K_n^1 es K_n y no se puede tratar con la misma ecuaci\u00f3n gen\u00e9rica que el resto, por lo que K_n^d s\u00f3lo funciona para d\\ge2.<\/p>\n

Por otro lado, el caso espec\u00edfico K_n^{n-1} se puede solucionar mediante otra aproximaci\u00f3n, de igual forma para todos los grafos. Primero, sabemos que la soluci\u00f3n constar\u00e1 de un \u00fanico camino bidireccional que recorra todos los nodos (lo cual es adem\u00e1s un camino hamiltoniano<\/a>). Esto es 2(n-1). El n\u00famero de aristas es n-1<\/em>, que valen doble porque son bidireccionales. Veamos el ejemplo con cinco y seis nodos.<\/p>\n

\n\"\"\"\"\n<\/p>\n

Ahora simplemente tenemos que rellenar los huecos del grafo con aristas en la direcci\u00f3n correcta. \u00bfCu\u00e1ntas son? Pues f\u00e1cil, el total de aristas de Kn<\/sub> menos n-1<\/em>, que son las que acabamos de pintar. <\/p>\n

\n E(K_n) - (n-1) = \\frac{n\\cdot (n-1)}{2}-(n-1)\n<\/p>\n

Lo cual, se lo sumamos a lo que ya ten\u00edamos y queda:<\/p>\n

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

\"\"\"\"<\/p>\n

Si tomamos el caso general E(K_n^d) y sustituimos d=n-1<\/em>, veremos que llegamos exactamente a la funci\u00f3n E(K_n^{n-1}). Si bien dije previamente que K_n^d no funciona para d=1<\/em>, esta nueva ecuaci\u00f3n s\u00ed 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\u00f3n de segundo grado con ra\u00edces en 1 y 2; nos nos interesa la segunda puesto que est\u00e1bamos considerando d=n-1<\/em> y demuestra que la igualdad es correcta. Tambi\u00e9n es mucho m\u00e1s sencillo directamente sustituir n=2<\/em> en ambas f\u00f3rmulas y ver que el resultado es el mismo, 2. El cual es exactamente el n\u00famero de aristas en un digrafo de dos nodos y di\u00e1metro uno.<\/p>\n

Tambi\u00e9n podemos tomar valores espec\u00edficos y comprobar que obtenemos el mismo resultado, por ejemplo:<\/p>\n

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

\u00bfAplicaciones pr\u00e1cticas de este resultado?<\/h2>\n

En la asignatura Distributed System<\/em> estamos estudiando algoritmos para seleccionar el nodo l\u00edder de una red, figura necesaria en muchas ocasiones para coordinar algoritmos distribuidos. Cada nodo tiene un identificador distinto del resto, as\u00ed que la selecci\u00f3n del l\u00edder se puede hacer bien con el que tenga el mayor ID o el que tenga el menor (para lo cual \u00e9ste ha de pasar por todos los nodos).<\/p>\n

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

Un algoritmo muy simple es FloodMax<\/em>, en el cual la complejidad es linear. Dura tantas rondas como el di\u00e1metro de la red, y en cada ronda cada nodo env\u00eda a todos sus vecinos el m\u00e1ximo valor ID que ha recibido hasta entonces. As\u00ed pues, el n\u00famero de mensajes es simplemente el n\u00famero de aristas por el di\u00e1metro.<\/p>\n

Un par de clases despu\u00e9s de esto, estaba lo suficientemente aburrido como para pensar en el peor caso de una red de tama\u00f1o N, para lo cual el primer paso era saber el m\u00e1ximo n\u00famero de aristas posibles con cada di\u00e1metro existente.<\/p>\n

Entonces, para saber el n\u00famero 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\u00f1o programita para calcular y mostrar estos valores (Graph.java<\/a> y Graph.class<\/a>). Ejecutando \u00abjava Graph -v N<\/em>\u00bb imprime informaci\u00f3n detallada<\/a> de cada di\u00e1metro, y con \u00abjava Graph N<\/em>\u00bb escribe s\u00f3lo los resultados para los cuales el n\u00famero de mensajes es el mayor<\/a>.<\/p>\n

En realidad, la guinda del pastel ser\u00eda resolver el problema de optimizaci\u00f3n para maximizar el valor msg = d \\cdot E(K_n^d) \\quad \\forall d, 1 \\le d < n[\/latex] pero hasta ah\u00ed ya no llego. Consult\u00e9 ayer a un amigo matem\u00e1tico que finalmente demostr\u00f3 que el m\u00e1ximo valor es siempre en [latex]E(K_n^{n-1})[\/latex] y pese a que me indic\u00f3 algunos de los pasos, no he sido capaz de reproducirlos. Si alguien se anima, [latex]\\LaTeX[\/latex] est\u00e1 activado tambi\u00e9n en los comentarios, utilizando $ latex f\u00f3rmula $ , sin espacio entre \u00ab$<\/em>\u00bb y \u00ablatex<\/em>\u00ab.<\/p>\n<\/div>

<\/a><\/p>