Arboles ( Matematicas discretas)

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 ciencias de la computación, se utiliza para la construcción de las redes.

6.1.1. 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 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 del grafo y los arcos son las líneas que representan las relaciones de parentesco conforme a esta familia:

6.1.2. Representación de árboles

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 grafo no dirigido es un árbol si y solo 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 3

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 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 cada uno 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, en el 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.

Lo usual 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í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 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 hermanos. Los ancestros de un vértice diferente de la raíz son los vértices en el grafo de la raíz a ese vértice, excluyendo el vértice mismo e incluyendo a la raíz. Los descendientes de un vértice v son aquellos vértices que tienen a v como ancestro. Un vértice de un árbol es llamado hoja si no tiene hijos. Los vértices que tienen hijos son llamados vértices internos. La raíz es un vértice interno a menos que sea el único vértice del grafo, en ese caso es una hoja. Si a es un vértice en un árbol, el subárbol con a como raíz, es el subgrafo del árbol que consiste de a y sus descendientes y todos los arcos incidentes en estos descendientes.

 

Observa la siguiente figura:

En este árbol Z, la raíz está en el vértice a; el padre de c es b y su descendencia es b y e; los hermanos de i son h y j, quienes son hijos de g; además, se pueden observar todos los ancestros de m; y también se observa que en este árbol con raíz existe otro subárbol con raíz en el vértice g, si se hace un acercamiento en esta parte se percibe lo siguiente:

 

El padre es g, los hijos son h,i,j y los descendentes de j son i e m, y el descendente de h es k.

También existe un árbol con raíz, de nombre m-ario, que consiste en que cada vértice interno no tiene más de m hijos, y  el árbol m-ario completo consiste si cada vértice tiene exactamente m hijos y  un árbol m-ario con cuando m=2 es llamado árbol binario.

Conforme lo visto anteriormente se distinguirán los diferentes tipos de grafos:

Este grafo representa un árbol binario completo porque cada uno de sus vértices internos tiene un hijo.

En esta figura se representa un árbol, árbol 3-ario, completo porque cada uno de sus vértices internos tiene tres hijos.

 

Este es un árbol 5-ario completo porque cada vértice interno tiene 5 hijos.

Este grafo representa un árbol m-ario completo para alguna m, porque algunos de sus vértices internos tienen dos hijos y otros tienen tres hijos.

También existe el caso de un árbol con raíz ordenado debido que los hijos de cada vértice interno están ordenados, y estos se expresan en el grafo de tal forma que los hijos de cada vértice interno se representan en orden de izquierda a derecha. Si el árbol con raíz ordenado tiene un vértice interno del cual emanan dos hijos, el primero se nombra hijo izquierdo y el segundo es llamado hijo derecho.

6.1.3. Árboles de decisión

Los árboles con raíz pueden ser empleados para modelar problemas en los que una serie de decisiones conducen a la solución. Por ejemplo, un árbol binario de búsqueda es utilizado para localizar elementos basados en una serie de comparaciones, donde cada comparación nos dice si hemos localizado el elemento o si debemos ir a la izquierda o a la derecha. Un árbol con raíz, en el que cada vértice interno corresponde a una decisión, con un subárbol en esos vértices para cada posible resultado de la decisión, se llama árbol de decisión.

El siguiente ejemplo ilustra una aplicación de los árboles de decisión. Supóngase que hay 7 monedas, todas con el mismo peso y una moneda falsa que pesa menos que las otras, el cuestionamiento es: ¿Cuántas pesadas son necesarias usando una balanza para determinar cuál de las ocho monedas es la falsa? Con el algoritmo se puede encontrar la moneda falsa.

Existen tres posibilidades cada vez que se realiza una pesada con la balanza, Las dos charolas tienen un mismo peso, la primera charola pesa más o la segunda pesa más. En consecuencia, el árbol de decisión de la secuencia de pesadas es un árbol 3-ario. Hay al menos 8 hojas en el árbol de decisión, ya que hay ocho posibles resultados, y cada posible resultado tiene que ser representado por al menos una hoja. El número más grande de pesadas que se necesita para determinar la moneda falsa es la altura del árbol de decisión. Así, al menos dos pesadas son necesarias. Es posible determinar la moneda falsa usando dos pesadas: