arboles de expansion

arboles de expansion
La fórmula de Cayley es una fórmula para obtener el número de árboles de expansión en un grafo completo con n vértices. La fórmula establece que . Otra prueba de la fórmulade Cayley es la existencia de exactamente á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 dePrüfer.
Si G es un grafo completo bipartido , entonces se cumple . Si G es el grafo hipercúbico n-dimensions , entonces se verifica que . Estas fórmulas son también corolarios del teoremamatriz-á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:

donde G-e es el multigrafo que se obtiene al eliminar la arista e, yG/e es la contracción de G sobre e, en la que las múltiples aristas de esta contracción no son eliminadas.

Los árboles de expansión
son útiles para difundir y recoger información de controlen las redes; a veces son útiles también para el enrutamiento
• Para difundir datos desde el nodo n:
– El nodo n realiza una amplia difusión de los datos en todos los arcos
– Otros nodosretardan los datos en los arcos de otros árboles adyacentes
• Para recoger datos en el nodo n:
– Todas las ramas del árbol (todas salvo la n) envían datos
– Los otros nodos (todos salvo el n) esperanla recepción de datos en todos sus arcos salvo en uno adyacente y, a continuación, envían los datos
del árbol adyacente recibidos más los propios por el arco restante

Algoritmo para construirun árbol de expansión para un grafo conexo G = (N,A):
1) Seleccionar cualquier nodo n en N; N' = {n}; A' = { }
2) Si N' = N, entonces parar (T=(N',A') es un árbol de expansión)
3) Elegir(i,j) ∈ A, i ∈ N', j ∉N' N' := N'∪{j}; A' := A'∪{(i,j)}; ir al paso 2
• La conectividad de G garantiza que se puede elegir un arco en el paso 3 siempre
• ¿Es único el árbol de expansión?...