Arboles

Unidad 6. Á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 la materia encaminado hacia las cienciasde la computación, se utiliza para la construcción de las redes. 6.1.1. Propiedades de los árbolesEntre 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 dos hojas.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. Ejemplo de árbol genealógico:En este ejemplo cabe señalar que los recuadros representan los vértices delgrafo y los arcos son las líneas que representan las relaciones de parentesco conforme a esta familia:6.1.2. Representación de árbolesEl á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 grafo no dirigido es un árbol si ysolo si hay un camino simple único entre cualesquiera dos de sus vértices”.Conforme los siguientes grafos, ¿cuál de ellos es del tipo de árboles?Ejemplo:¿Cuáles de los grafos de la figura 6.2 son árboles?Fig. 6.2 Grafo 1,2 y 3Si 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ánconectados con circuitos no simples.Como se sabe, existen grafos que no tienen conexión y podría existir confusió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 cadauno de sus componentes conectados es un árbol.Los árboles son mostrados a continuación:En gran parte de 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, enel apartado 6.1.2, por lo tanto es un grafo de árbol con raíz, esto es simplemente el árbol que junto 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.Lousual es elaborar un grafo de árbol con raíz en la parte superior del grafo, en donde las flechas muestran la dirección de los arcos, como se muestra en la siguiente figura:En el apartado 6.1.1 se elaboró un árbol genealógico con el propósito de familiarizarse con la terminología, que es de origen genealógico y botánico. Observe el siguiente grafo:En esta figura se deduce que E es un árbol con raíza, 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 el único vértice u tal que hay un arco dirigido de u a v. Cuando u es el padre de v, v es llamado un hijo de u. Los vértices con el mismo padre son llamados...