Elementos matematica discreta

152 CAPÍTULO 6. ÁRBOLES Estos ejemplos son un caso particular de la siguiente regla general.Teorema 6.6.- Si el grafo asociado a una estructura rectangular es conexo, entonces se trata de una estruc-tura rígida. Por el contrario, si el grafo no es conexo, la estructura se puede deformar. Profundicemos un poco más en el estudio de las estructuras. Aunque algunas de ellas sean rígidas, puedeque estén reforzadas en exceso, es decir, se pueden eliminar tirantes diagonales y el armazón sigue siendorígido. Esto ocurre, por ejemplo, en la estructura a) de la figura 6.8. Si analizamos el correspondiente grafo,observamos que contiene varios ciclos (f1 − c2 − f2 − c3 − f1 es uno de ellos). Si eliminamos en este ciclo unaarista cualquiera, el armazón sigue siendo rígido. Si eliminamos más aristas de forma que no queden ciclos yel grafo siga siendo conexo, obtendremos una estructura rígida con el mínimo número de refuerzos. Es decir,si encontramos un árbol generador dentro de un grafo, estaremos resolviendo el problema de encontrar unaestructura rígida con el mínimo número de refuerzos. Por ejemplo, en el grafo a) podemos quitar aristas hastadejarlo reducido al siguiente árbol generador f1 f2 f3 •• •• ••.......................................................................................................................................................................................................................................................... c1 c2 c3La estructura asociada a este grafo es rígida. En el caso de la estructura c), como el correspondiente grafo yaes un árbol generador, se trata de un reforzamiento mínimo. De nuevo, éstos son casos particulares de unaregla más general.Teorema 6.7.- Si el grafo asociado a una estructura rectangular es un árbol generador, entonces se trata deuna estructura rígida con un reforzamiento mínimo, es decir si se elimina algún tirante diagonal, el armazóndeja de ser rígido.6.4. Árboles generadores minimales En otras situaciones, como puede ser la de conectar una serie de poblaciones mediante una red de tele-comunicaciones, el problema no es exactamente saber si existe un árbol generador, sino más bien saber cuáles el árbol generador más económico, siendo que una línea de la red, entre dos poblaciones dadas, tiene undeterminado coste. Esto nos conduce a los conceptos de grafo ponderado y árbol generador minimal.Ejemplo 6.11.- Supongamos que se va a establecer, de forma experimental, una red inalámbrica entre cincoedificios de un campus universitario. El siguiente grafo muestra los posibles enlaces que se podrían incluir enla red junto con su coste en miles de euros. A E• 50 6•5 1460 1•2 1513 70• 16B•................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... D 75 CEstá claro que para comunicar dos edificios no es necesario un enlace directo, pues se puede mandar unmensaje de uno a otro de forma indirecta. Por ejemplo, enviar un mensaje de A a B y de B a C en lugarde enviarlo directamente de A a C. Supongamos que el coste de enviar un mensaje una vez instalada la redes despreciable comparado con el coste de hacer una comunicación directa. El problema consiste entonces endeterminar la red con el mínimo coste que garantice la comunicación entre los cinco edificios del campus.