Árboles de exposición mínima y máxima

ÁRBOL DE EXPANSIÓN MÍNIMA

• Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar un loop.
• El ´árbol de expansión mínima es apropiado para problemas en las cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantánea .
• Este problema se refiere las ramas o arcos de la red para llegar a todos los nodos de la red, de manera tal que se minimiza la longitud total.
• La aplicación de estos problemas de optimización se ubica en las redes de comunicación eléctrica, telefónica ,carretera, ferroviaria, aérea, marítima, etc; donde los nodos representan puntos de consumo eléctrico, teléfonos, aeropuertos, computadoras.
• Y los arcos podría ser de alta tensión, cable de fibra óptica,etc.
• si n=numero de nodos, entonces la solución óptima debe incluir n-1 arcos.
• 

ÁRBOL DE EXPANSIÓN MÁXIMA

• Según la primera, un bosque de expansión es un subgrafo que consiste en un árbol de expansión en cada componente conexo del grafo (equivalentemente, es un subgrafo libre de ciclos maximal). Esta definición es frecuente en informática y optimización, así como la que se emplea habitualmente al tratar los bosques mínimos de expansión, la generalización a subgrafos disconexos de árboles de expansión minimales.
• Otra definición, empleada en teoría de grafos, es la de un bosque de expansión es un subgrafo que es a la vez bosque (es decir, no contiene ciclos) y de expansión (es decir, incluye a todos los vértices).
• 

CONTEO DE ÁRBOLES DE EXPANSIÓN

• La fórmula de Cayley es una fórmula para obtener el número de árboles de expansión en un grafo completo {\displaystyle K_{n}} con n vértices. La fórmula establece que {\displaystyle t(K_{n})=n^{n-2}}. Otra prueba de la fórmula de Cayley es la existencia de exactamente {\displaystyle n^{n-2}} árboles etiquetados con n vértices. La fórmula de Cayley puede ser demostrada mediante el teorema de matriz-árbol de Kirchhoff o mediante el código de Prüfer.
• Si G es un grafo completo bipartido {\displaystyle K_{p,q}}, entonces se cumple {\displaystyle t(G)=p^{q-1}q^{p-1}}. Si G es el grafo hipercúbico n-dimensions {\displaystyle Q_{n}}, entonces se verifica que {\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}. Estas fórmulas son también corolarios del teorema matriz-árbol.
• Si G es un multigrafo y e es una arista de G, entonces el número t(G) satisface la recurrencia de supresión-contracción:
• {\displaystyle t(G)=t(G-e)+t(G/e)}
•