Arboles



Matemáticas Discretas
Tema: Árboles

Árboles
Un grafo conectado que contiene circuitos no simples se llama árbol. En el año de 1857 Arthur Cayley, matemático inglés, los empleó para contabilizar componente químicos, no obstante, es importante señalar que no solo es una herramienta de la química sino que se han utilizado en diversas áreas, por ejemplo, conforme el propio interés de lamateria encaminado hacia las ciencias de la computación, se utiliza para la construcción de las redes.
Propiedades de los árboles
Entre las propiedades más importantes de los árboles está la presencia de un paseo entre cualquiera de dos vértices del árbol; segundo, que el número de vértices no es menor al número de aristas del árbol y que un árbol con más de dos vértices tiene por lo menos doshojas.
Un ejemplo claro de los árboles en la vida cotidiana son los árboles genealógicos. Para este caso, los vértices representan a los miembros de la familia y los arcos representan la relación de parentesco. Conforme los conocimientos adquiridos con anterioridad, el árbol no deja de ser un grafo, pero es del tipo no dirigido. Una hoja es un nodo de grado 1.Todo árbol no trivial tiene al menos doshojas.

Representación de árboles
En un árbol no orientado podemos definir un nodo cualquiera como raíz. El nivel de un nodo de un árbol es la distancia de ese nodo ala raíz. La altura h de un árbol es la longitud desde la raíz al nodo más lejano. Un árbol se dice (exactamente) m-ario si todos sus nodos, salvo las hojas y la raíz tienen grado (exactamente) a lo sumo m + 1 y la raíz(exactamente) a lo sumo m. Un árbol se dice balanceado si todas sus hojas están a nivel h o h 􀀀 1.Un árbol se dice balanceado completo si todas sus hojas están a nivel h.

El árbol es un grafo no dirigido conectado con circuitos no simples; además, no contiene arcos múltiples, con la propiedad de que hay un único camino simple entre cada par de vértices, teniendo el siguiente teorema:
Teorema 1. “Un grafono dirigido es un árbol si y solo si hay un camino simple único entre cualesquiera dos de sus vértices”.




Si se observan los siguientes grafos, se concluye que el grafo G1 no es un árbol porque se observa un circuito simple, pero los grafos G2 Y G3 son de árboles, porque están conectados con circuitos no simples.


Como se sabe, existen grafos que no tienen conexión y podría existirconfusión el pensar que un árbol es un grafo conectado que tiene circuitos no simples, pero es importante mencionar que existen árboles del tipo que contienen circuitos no simples que no necesariamente están conectados, y esos árboles reciben el nombre de bosques, cuya característica es que cada uno de sus componentes conectados es un árbol.
Los árboles son mostrados a continuación:

En gran partede las aplicaciones de árboles, se designa a un vértice particular del árbol como la raíz, por lo que se pude asignar una dirección a cada arco, debido que hay un camino único de la raíz a cada vértice del grafo dirigiéndose cada arco alejándose de la raíz, conforme lo enunciado en el teorema 1, en el apartado 6.1.2, por lo tanto es un grafo de árbol con raíz, esto es simplemente el árbol quejunto con su raíz forman un grafo y en caso que fuesen diferentes s vértices como raíz, se producen diferentes árboles con raíz.




A continuación se muestra un grafo de árbol con raíz:

De acuerdo a lo anterior se muestran los árboles con raíz en donde a y c son las raíces correspondientes del grafo R.
Lo usual es elaborar un grafo de árbol con raíz en la parte superior del grafo, en dondelas flechas muestran la dirección de los arcos, como se muestra en la siguiente figura:


En esta figura siguiente se deduce que E es un árbol con raíz a, se observa que los padres son b, c y d y, a su vez, don hermanos, f y g son hijos de b; además, e es hijo de c.




Otro ejemplo: si se supone que A es un árbol con raíz, si v es un vértice en A diferente de la raíz, el padre de v es...