• Author / Uploaded
• Omer Primera

Citation preview

República Bolivariana de Venezuela Ministerio del Poder Popular para la Defensa Universidad Nacional Experimental Politécnica de la Fuerza Armada Nacional Bolivariana (UNEFA) UNEFA – Extensión Guacara Guacara, Edo. Carabobo

Unidad III: Grafos Prof. Ing. Alexander Zavala Asignatura: Teoría de Grafos Carrera: Ing. De Sistemas

Integrantes: Omer Primera C.I: 28.456.174

Guacara, marzo 2020.

Grafo de Euler. Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice.

Casos. Dado un grafo conexo (no existen nodos aislados) y no dirigido G=(V , E), si Gtiene exactamente dos vértices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, G tiene un ciclo euleriano. Teorema: Dado G ( V , E ) no orientado y conexo; si tiene 2 k nodos de grado impar, entonces G puede ser escrito como unión de k caminos (simples) distintos sobre los arcos y valen las siguientes expresiones: 1) G es euleriano; 2) ∀ v ∈V  con grado ( v)≥2y par. n

3) G=∐ C i todos disjuntos (caminos distintos) en los arcos, es decir C Ei ∩C Ej =∅ con i≠ j i=1

∀ Ci va de un nodo de grado impar a un nodo de grado impar. Un grafo admite un camino euleriano cuando tiene exactamente dos nodos de grado impar (conexos a los caminos). CONEXO

NO CONEXO

Propiedades.     

Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par. Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos. Si un grafo no dirigido G es euleriano entonces su gráfo-línea L (G) se dice que es también euleriano. Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos. Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y dos vértices en el grafo tienen grado impar.

Algoritmo de Fleury. Gracias a los teoremas de Euler es posible saber si un grafo dado tiene trayectorias o circuitos de Euler, lastimosamente estos teoremas no indican la manera de encontrar dicho recorrido. En esta sección se mostrarán una serie de instrucciones muy sencillas conocidas como El algoritmo de Fleury las cuales permitirán encontrar una trayectoria o circuito de Euler en caso de que este exista. Una definición preliminar necesaria es la de puente. Un puente es Una arista tal que al quitarla grafo se convierte en un grafo disconexo. El algoritmo de Fleury (Grafos Eulerianos) que permite encontrar una trayectoria o circuito de Euler. Algoritmo de Fleury para un circuito de Euler: 1. Verificar que es conexo con todos los vértices pares. 2. Seleccionar un vértice arbitrario. 3. Seleccionar una arista a partir del vértice actual que no sea puente (es decir, que no desconecte el grafo), a menos que no haya otra alternativa. 4. Desconectar los vértices que están unidos por la arista seleccionada. 5. Si todos los vértices ya están desconectados, ya se tiene el circuito de Euler. De otra forma continuar con el paso 3.

Ejemplo: {B, E} es un puente.

A

B

E

C

D

Ciclo de Hamilton. Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo. Los caminos y ciclos hamiltonianos se llaman así en honor de William Rowan Hamilton, inventor de un juego que consistía en encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, aunque su solución no era generalizable a todos los grafos. Un camino hamiltoniano es un camino que pasa por cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano. Estos conceptos se pueden extender para los grafos dirigidos los cuales son igual a un carro.

Ejemplos:     

Todos los grafos ciclos son hamiltonianos. Los grafos completos con más de dos vértices son hamiltonianos. Todos los campeonatos poseen caminos dirigidos hamiltonianos. Se puede consultar la demostración en [Theorem 2.2.1]. Todos los sólidos platónicos (el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro), considerados como grafos, son hamiltonianos. Entre los grafos eulerianos los hay que son hamiltonianos y los hay que no lo son, y entre los grafos hamiltonianos los hay que son eulerianos y los hay que no lo son.

Grafos: G1, G2, G3 y G4 1. 2. 3. 4.

El grafo G1 es euleriano y hamiltoniano. El grafo G2 es euleriano y no es hamiltoniano. El grafo G3 no es euleriano y es hamiltoniano. El grafo G4 es conexo, no es euleriano ni hamiltoniano. Condiciones Necesarias.

Podemos, no obstante, anotar algunas condiciones necesarias para que un grafo sea hamiltoniano.   

Un grafo hamiltoniano ha de ser conexo. Un grafo hamiltoniano no puede tener vértices de grado 1: en todos los vértices deben incidir al menos dos aristas, la de “entrada” y la de “salida”. Si S es un subconjunto del conjunto de vértices de un grafo G, escribimos G − S para designar el subgrafo que aparece al eliminar todos los vértices de S y todas las aristas adyacentes a los vértices de S.

Teorema: Si un grafo G es hamiltoniano entonces para cualquier subconjunto no vacío de vértices S de G, el número de componentes conexas del subgrafo G − S es menor o igual que el cardinal de S. (Cf. [Theorem 6.2.4]). En particular, un grafo hamiltoniano no puede poseer vértices de corte, esto es, un vértice tal que si lo eliminamos junto a todas las aristas que confluyen en él, el subgrafo resultante tiene más componentes conexas que el grafo original. El recíproco no es cierto.

Condiciones Suficientes. Teorema de Bondy-Chvátal: Existen muchos resultados que proporcionan condiciones suficientes que garanticen el carácter hamiltoniano de un grafo. De entrada, para poder analizar si un grafo de más de 2 vértices es hamiltoniano podemos suprimir los lazos y las aristas paralelas. Además un grafo con 2 vértices es hamiltoniano si y sólo si tiene al menos dos aristas entre ambos vértices. Por tanto nos concentramos en el análisis de grafos simples, sin lazos y con más de 2 vértices. La mejor aportación en este sentido es un teorema publicado en 1976 debido a J. A. Bondy y a V. Chvátal, que generaliza los resultados anteriormente encontrados por G. A. Dirac (1952) y Ø. Ore (1960). Todos estos resultados afirman, básicamente, que un grafo es hamiltoniano si existen “suficientes aristas”. Para enunciar el Teorema de Bondy-Chvátal es menester definir primero qué es la clausura de un grafo. Dado un grafo G con n vértices, la clausura de G es el grafo que tiene los mismos vértices que G y que aparece al agregar todas las aristas de la forma {u, v} para cualquier par de vértices u y v que no sean adyacentes y cumplan que grado (v) + grado (u) ≥ n. Teorema: Un grafo es hamiltoniano si y sólo si lo es su clausura. Puede consultarse una demostración del Teorema de Bondy-Chvátal en [Theorem 7.20]. Los Teoremas de Ore y Dirac. Como todos los grafos completos son hamiltonianos, todos los grafos cuya clausura sea un grafo completo son hamiltonianos. Esto nos permite deducir algunas condiciones suficientes para que un grafo sea hamiltoniano; en particular aparece el Teorema de Ore y el Teorema de Dirac. Teorema: Si G es un grafo conexo, simple y sin lazos con n vértices, con n ≥ 3, en el cual grado (u) + grado (v) ≥ n para todo par de vértices no adyacentes u, v, entonces G es hamiltoniano. Se puede consultar una demostración directa del Teorema de Ore en [Theorem 6.2.5]. Teorema: Si G es un grafo conexo, simple, sin lazos y con n vértices en el cual grado (u) ≥ n/2 para todo vértice u, entonces G es hamiltoniano.

Corolario: Si G es un grafo conexo, simple y sin lazos con n vértices, con n ≥ 3, en el cual grado (u) + grado (v) ≥ n − 1 para todo par de vértices no adyacentes u, v, entonces G posee un camino hamiltoniano. Ejemplo: Consideremos el siguiente grafo, al que se suele denominar como “grafo casa”, que es claramente hamiltoniano:

Grafo Casa.   

No podemos deducir que es hamiltoniano aplicando el Teorema de Dirac pues hay vértices de grado 2 y 2 < 5/2. No podemos deducir que es hamiltoniano aplicando el Teorema de Ore pues hay dos pares de vértices no adyacentes de grado 2 y 2 + 2 < 5. La clausura del grafo casa se obtiene añadiendo en primer lugar las aristas rojas y después las azules. Por lo tanto, la clausura del grafo es el grafo completo de 5 vértices. El grafo completo es hamiltoniano. En consecuencia se puede deducir que el grafo casa es hamiltoniano aplicando el Teorema de Bondy-Chvátal.

Clausura del grafo casa.

Una consecuencia del Teorema de Ore es el resultado siguiente. Su demostración puede consultarse en [Theorem 6.2.14].

Corolario: Si G es un grafo conexo, simple y sin lazos con n vértices, con n ≥ 3, en el cual grado (u) + grado (v) ≥ n − 1 para todo par de vértices no adyacentes u, v, entonces G posee un camino hamiltoniano. Ejemplo: Si G es un grafo simple, sin lazos y con n vértices en el cual grado (u) + grado (v) ≥ n − 1 para todo par de vértices u, v, entonces G no es necesariamente hamiltoniano. Esto se aprecia en muchos ejemplos; en particular, en los siguientes.

Ejemplos. Dígrafos Hamiltonianos. Para grafos dirigidos mencionemos un resultado de H. Meyniel que proporciona también una condición suficiente para que un digrafo fuertemente conexo sea hamiltoniano. Teorema: Si D es un grafo dirigido fuertemente conexo de n vértices en el cual grado (u) + grado (v) ≥ 2n − 1 para toda pareja u, v de vértices no adyacentes entonces D es grafo dirigido hamiltoniano.

Árbol. Árbol

Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es 2-4-5-6. Vértices

v

Aristas

v-1

Número cromático

2 si v > 1

Propiedades

Bipartito, expandible y plano (si el conjunto de vértices es numerable)

En teoría de grafos, un árbol es un grafo en el que cualesquier dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre. Un árbol es un grafo simple no dirigido G que satisface: 1. G es conexo y no tiene ciclos . 2. G no tiene ciclos y, si se añade alguna arista se forma un ciclo.

3. G es conexo y si se le quita alguna arista deja de ser conexo. 4. G es conexo y el grafo completo de 3 vértices  K 3 no es un menor de G. 5. Dos vértices cualesquiera de G están conectados por un único camino simple.

Las condiciones anteriores son todas equivalentes, es decir, si se cumple una de ellas otras también se cumplen. Para árboles finitos además se cumple que: Si un árbol G tiene un número finito de vértices, n, entonces tiene n − 1 aristas. Algunas definiciones relacionadas con los árboles son:  









Un grafo unidireccional simple G es un bosque si no tiene ciclos simples. Un árbol dirigido es un grafo dirigido que sería un árbol si no se consideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular. Un árbol recibe el nombre de árbol con raíz si un vértice ha sido designado raíz. En este caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol (programación). Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2,..., n}. Un árbol regular u homogéneo es un árbol en el que cada vértice tiene el mismo grado. Todo árbol posee una altura. Recorriendo el mismo en forma de grafo dirigido y considerando que las aristas parten desde los vértices hacia algún otro vértice o hacia alguna hoja, de forma tal que todo camino inicia en la raíz y termina en una hoja, puede afirmarse que el árbol posee una altura h. Dicha altura será igual a la longitud del camino con más aristas. Clasificación.

Un árbol es llamado k-ario si cada nodo tiene, como máximo, k hijos. Un caso particularmente importante es el de un árbol 2-ario, al cual se denomina árbol binario. Si todos los nodos del árbol exceptuando las hojas, poseen exactamente k hijos, ese árbol además de ser k-ario es completo. Otro caso particular es el del árbol estrella, el cual consiste de un único nodo, que es la raíz. El resto de sus vértices son hojas. Todo árbol estrella de k vértices tiene un único nodo con k-1 hijos, por lo tanto, todo árbol estrella de k vértices es (k-1)-ario.

Propiedades. Todo árbol es a su vez un grafo con sólo un conjunto numerable de vértices es además un grafo plano. Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G. Todo árbol k-ario completo de altura h tiene kh hojas . Dado n vértices etiquetados, hay n n−2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d1, d2,...,dn es: , que es un coeficiente multinomial. ( d −1, d n−2 −1 , . .. , d −1 ) 1

2

n

Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entenderse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primeros valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sucesión A000055 en OEIS). Otter (1948) probó que: t (n ) C∝ n n

−5 2

as n → ∞

Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números α y β (α ≈ 3 y β ≈ 0.5) tales que: lim

n→∞

t(n) n

β∝ n

−5 2

Árbol Generador Minimales. El peso de un árbol generador es la suma de los pesos de las ramas del árbol. Un árbol generador mínimo es uno con peso mínimo. Una interpretación física de este problema es considerar los vértices de un grafo como ciudades, y los pesos de las aristas como los costos de construcción y mantenimiento de vías de comunicación entre las ciudades. Supongamos que queremos construir una red de

comunicaciones que conecte a todas las ciudades a un costo mínimo. Entonces el problema es determinar un árbol generador mínimo. Un procedimiento para resolver este problema se base en la observación de que entre todas las aristas en un circuito, la arista con mayor peso no está en el árbol generador mínimo. Sea "C" un circuito en un grafo pesado, y "E" la arista con el mayor peso en "C". Supongamos que "E" es una rama de un árbol generador de T. Sea del conjunto de corte correspondiente a la rama a la rama "E" como el circuito C y el conjunto de corte d deben tener un numero par de aristas en común además de la arista "E" deberán existir al menos una o más aristas que estén tanto en C como en D. Sea F una de estas aristas. Observemos que F es una cuerda del árbol generador t debido a que D es un conjunto de corte. Agreguemos la arista F al árbol generador T y denotemos el subgrafo resultante como U. Es obvio que U es un subgrafo generador que contiene exactamente un circuito, el circuito correspondiente a F. Si eliminamos E de U, obtenemos un árbol generador cuyo peso es menor que T. Construiremos un subgrafo del grafo pesado paso por paso, al ir examinando cada arista en orden creciente de pesos. Se agregara una arista al subgrafo parcialmente construido si no origina un circuito, y será descartada en caso contrario. La constricción termina cuando todas las aristas han sido examinadas. Es claro que nuestra construcción de origen a un subgrafo que no contiene un circuito. El subgrafo también es conexo. Así el subgrafo construido es un árbol. Además, este es un árbol generador debido a que el grafo original es conexo. Finalmente, el árbol generador es mínimo porque en el proceso de construcción una arista era excluida a favor de las aristas de pesos mayores solo si sé sabía que la arista excluida no podía estar en un árbol generador mínimo. En otras palabras, las v - 1 aristas en el subgrafo son efectivamente las v - 1 aristas con los pesos menores que pueden ser incluidas en un árbol generador mínimo. Ejemplo:

Algoritmo de Prim.

El algoritmo de Prim permite encontrar un árbol recubridor mínimo de un grafo. El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo. El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik. Demostración. Sea G un grafo conexo y ponderado. En toda iteración del algoritmo de Prim, se debe encontrar una arista que conecte un nodo del subgrafo a otro nodo fuera del subgrafo. Ya que G  es conexo, siempre habrá un camino para todo nodo. La salida Y del algoritmo de Prim es un árbol porque las aristas y los nodos agregados a Y están conectados. Sea Y1 el árbol recubridor mínimo de G. Si Y 1=Y → Y es el árbol recubridor mínimo.

Si no, sea e la primera arista agregada durante la construcción de Y y, que no está en Y 1 ❑❑y sea V el conjunto de nodos conectados por las aristas agregadas antes que e. Entonces un extremo de e está en V y el otro no. Ya que Y 1 es el árbol recubridor mínimo de G hay un camino en Y 1 que une los dos extremos. Mientras que uno se mueve por el camino, se debe encontrar una arista f  uniendo un nodo en V  a uno que no está en V . En la iteración que e se agrega a Y , f  también se podría haber agregado y se hubiese agregado en vez de e   si su peso fuera menor que el de ee. Ya que f  no se agregó se concluye: P( f ) ≥ P(e) Sea Y 2❑❑ el grafo obtenido al remover f  y agregando e ∈ Y 1. Es fácil mostrar que Y 2   conexo tiene la misma cantidad de aristas que Y 1, y el peso total de sus aristas no es mayor que el de Y 1, entonces también es un árbol recubridor mínimo de GG y contiene a e y todas las aristas agregadas anteriormente durante la construcción de V . Si se repiten los pasos mencionados anteriormente, eventualmente se obtendrá el árbol recubridor mínimo de G   que es igual a Y . Esto demuestra que Y  es el árbol recubridor mínimo de G. Ejemplo de ejecución del algoritmo:

Imagen

Descripción

No En el En el visto grafo árbol

Este es el grafo ponderado de partida. No es un árbol, ya que para serlo se requiere que no haya ciclos, y en este caso sí hay. Los números cerca de las A, B, C, G D aristas indican el peso. Ninguna E, F de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida.

El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. B, E, C, G A, D De estos, 5 es el valor más F pequeño, así que marcamos la arista DA.

El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 C es el valor más pequeño, así que marcamos el vértice F y a la arista DF.

B, E, A, D, G F

El algoritmo continúa. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este null punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado.

C, E, A, D, G F, B

Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, null entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol.

C, G

A, D, F, B, E

G

A, D, F, B, E, C

Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se null marca con el arco EC. El arco BC también se marca con rojo.

G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya null marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39.

null

A, D, F, B, E, C, G

Algoritmo de Kruskal.

El algoritmo de Kruskal calcula un árbol recubridor mínimo de un grafo. El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956.12. Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor mínimo son el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de Boruvka. Descripción. El algoritmo de Kruskal es un ejemplo de algoritmo voraz que funciona de la siguiente manera:   

Se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado. Se crea un conjunto C que contenga a todas las aristas del grafo. Mientras C es no vacío. o Eliminar una arista de peso mínimo de C.

o Si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol. o En caso contrario, se desecha la arista. Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo. En un árbol de expansión mínimo se cumple:

o La cantidad de aristas del árbol es la cantidad de nodos menos uno (1). Ejemplo.

Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.

AD y CE son las aristas más cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta.

Sin embargo, ahora es CE la arista más pequeña que no forma ciclos, con peso 5, por lo que se resalta como segunda arista.

La siguiente arista, DF con peso 6, ha sido resaltada utilizando el mismo método.

Las siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.

El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).

Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol expandido mínimo con peso total de 39.

Árbol con Raíz. Sea A un conjunto y T una relación en A. Se dice que T es un árbol si posee un vértice vo en A con la propiedad de que existe una única trayectoria de vo hacia cualquier otro vértice de A pero no existe una trayectoria de vo a vo. Notación:  Se dice que T es un árbol con raíz y se denota (T, vo)  vo se denomina raíz del árbol T  Cualquier otro elemento de A es un vértice en T. Observación: T se representa por su Digrafo Un árbol ordenado (ordened tree) se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En un árbol ordenado podemos hablar del primero, segundo o último hijo de un nodo particular. El primer hijo de un nodo, en un árbol ordenado, se denomina con frecuencia el hijo más viejo de este nodo y el último hijo, se denomina el hijo más joven.

Árbol de Decisión. Un árbol de decisión es un mapa de los posibles resultados de una serie de decisiones relacionadas. Permite que un individuo o una organización comparen posibles acciones entre sí según sus costos, probabilidades y beneficios. Se pueden usar para dirigir un intercambio de ideas informal o trazar un algoritmo que anticipe matemáticamente la mejor opción. Un árbol de decisión, por lo general, comienza con un único nodo y luego se ramifica en resultados posibles. Cada uno de esos resultados crea nodos adicionales, que se ramifican en otras posibilidades. Esto le da una forma similar a la de un árbol. Hay tres tipos diferentes de nodos: nodos de probabilidad, nodos de decisión y nodos terminales. Un nodo de probabilidad, representado con un círculo, muestra las probabilidades de ciertos resultados. Un nodo de decisión, representado con un cuadrado, muestra una decisión que se tomará, y un nodo terminal muestra el resultado definitivo de una ruta de decisión.

Los árboles de decisión también se pueden dibujar con símbolos de diagramas de flujo, que a algunas personas les parecen más fáciles de leer y comprender. Símbolos de los Árboles de Decisión. Figura

Nombre

Significado

Nodo de decisión

Indica una decisión que se tomará

Nodo de probabilidad

Muestra múltiples resultados inciertos

Ramificaciones alternativas

Cada ramificación indica un posible resultado o acción

Alternativa rechazada

Muestra una alternativa que no estaba seleccionada

Nodo terminal

Indica un resultado definitivo

Árbol Binario. En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman. Definición de Teoría de Grafos.

Un árbol binario sencillo de tamaño 9, 3 niveles (nivel 0 hasta nivel 3) y altura 3 (altura = máximo nivel), con un nodo raíz cuyo valor es 2.

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 2». De esta forma solo existe un camino entre un par de nodos. Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque'. Tipos de Árboles Binarios. Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho. Existen tipos de árboles binarios que suelen usarse para fines específicos, como:  

Árbol binario de búsqueda Árbol de Fibonacci