arboles

TEORÍA DE GRAFOS
Una de las partes de la matemática discreta que en estos últimos años ha experimentado un desarrollo más notable es la teoría de grafos. Enmarcada dentro de la combinatoria, esta teoría permite modelar de forma simple cualquier sistema cualquier sistema en el cual exista una relación binaria entre ciertos objetos; y es por eso que su ámbito de aplicación es muy general y cubreáreas que van desde la misma matemática-topología, probabilidad, análisis numérico, etc. –hasta la ingeniería eléctrica, de telecomunicación e informática, la investigación operativa, la sociología o, incluso, la lingüística. En seguida presentaremos uno de los temas más importantes de la teoría de grafos: Árboles.
ÁRBOLES
En este trabajo nos centraremos en un tipo especial de grafo llamadoárbol. Los árboles fueron utilizados por primera vez en 1847 por Gustav Kirchhoff (1824-1887) en su trabajo de redes eléctricas, aunque posteriormente fueron desarrolladas y definidos de nuevo por Arthur Cayley (1821-1895). En 1857, Cayley usó estos grafos especiales para enumerar los isómeros diferentes de hidrocarburos saturados C_n H_(2n+2),n∈Z^+.
Con la aparición de los computadores digitales seencontraron nuevas aplicaciones para los árboles. Algunos tipos especiales de árboles son muy importantes en el estudio de las estructuras de datos, las ordenaciones, la teoría de codificación y en la solución de ciertos problemas de optimización.
DEFINICIÓN: Un árbol es un grafo conexo y sin ciclos. La figura 6.2 muestra, por ejemplo, un árbol con orden 7. Este tipo de estructura combinatoriaaparece en muchas aplicaciones de naturaleza distinta.

Por ejemplo, en el diseño en el diseño de algoritmos y estructuras de datos se utilizan los llamados árboles de decisión y, en particular, los árboles binarios, en los cuales existe un único vértice r, llamado raíz, que tiene grado 2, y los vértices restantes tienen grado 1 o 3. Así, en el árbol binario de la figura 6.3, los vértices v y wrepresentan posibles alternativas a partir de u.

El teorema siguiente da diversas caracterizaciones de los árboles. Si u, v son vértices independientes de un grafo G= (V, E ), representaremos por G + uv el grafo resultante de añadir a G la arista uv, es decir, G+uv=(V,E∪{uv} ).
TEOREMA 1. Dado un grafo G, las proporciones siguientes son equivalentes:
G es un árbol.
G es conexo y notiene ciclos.
Entre cada par de vértices de G existe un único camino.
G es conexo con orden n y tamaño n-1.
G es conexo, pero G-e es no conexo para toda arista e∈E(G)
G es acíclico, pero G+uv contiene un ciclo para todo par u,v de vértices independientes.
DEMOSTRACIÓN DEL TEOREMA 1.
(a)↔(b) . Esta equivalencia corresponde a la definición de árbol. (b)↔(c). Sea G un árbol. Si entre dosvértices dados G hubiese dos caminos diferentes, C1 y C2, entonces su unión C1 ∪ C2 sería un sub-grafo de G que contendría al menos un ciclo. Recíprocamente, si entre cada par de vértices distintos de un grafo G hay un único camino, G es conexo y también tiene que ser acíclico; de otro modo, si Γ fuese un ciclo de G, existirían al menos dos caminos distintos entre cada par de vértices de Γ.
(a)↔(d).Esta equivalencia se puede demostrar por inducción sobre el número de vértices. Si G es un árbol con n=1, n=2 o n=3 vértices se cumple que su número de aristas es n-1; ver la figura 6.4

Supongamos que todo árbol de orden k menor que n tiene tamaño k – 1. Sea G un árbol de orden n y sea e=uv∈E(G). El camino u,v es el único en el árbol G entre los vértices u y v. Por tanto, el grafo G-e estáconstituido por dos componentes conexos Tu y Tv que, por ser G acíclico, tampoco contienen ciclos y que, por tanto, son árboles. Si Tu y Tv tienen orden nu y nv, respectivamente, entonces, por la hipótesis de inducción, sus tamaños son, respectivamente n_u-1 y n_v-1. Por tanto, el número de aristas de G es 〖(n〗_u-1)+(n_v-1)+1=(n_u+n_v-1)=n-1. Así pues,(a)→(d), es preciso notar, en primer...