RECORRIDOS DE UN ÁRBOL

En ciencias de la computación, el recorrido de árboles refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles.

Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados define el tipo de recorrido. Estos pasos (en ningún orden particular) son: ejecución de una acción en el nodo actual (referido como “visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. Así el proceso más fácilmente descrito a través de la recursión.

Los nombres dados para un estilo particular de recorrido vienen de la posición del elemento de raíz con respecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).

Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos. Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los métodos de recorrido.

ARBOLES BINARIOS

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.

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 3. 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'.

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.

ARBOLES DE EXPANSIÓN MÍNIMA

Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).

ARBOLES DE EXPANSIÓN 

En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. 

Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T.

Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.

En ciertos campos de la teoría de grafos es útil encontrar el mínimo árbol de expansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos k vértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas (estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol de expansión de mínimo diámetro o el árbol de expansión de la mínima dilación.

TERMINOLOGÍA Y CARACTERIZACIÓN

TERMINOLOGÍA 

Ademas del nodo raíz, existen muchos términos utilizados en la descripción  de los atributos de un árbol, por ejemplo un nodo que tiene arboletes se conoce como padre de ellos, y los nodos sucesores se llaman hijos. De este modo los hijos de un nodo y los hijos de este se denominan descendientes asi como el padre y los abuelos se conoce como ascendentes. Los nodos del mismo padre suelen llamarse hermanos y los nodos  que no tiene desentiendes de conocen como hojas.



CARACTERIZACIÓN

• Todo arbol que no es vacio, tiene un unico nodo raiz.
• Un nodo X es desendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y.
• En este caso es común utlilizar la expresión X es hijo de Y.
• Un nodo X es antecesor directo de un nodo Y, si en nodo apunta al nodo Y.

UNIDAD 5

ARBOLES

Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.

Ejemplo de árbol:

En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo.

Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.

En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.

GRAFOS APLANABLES 

Este tipo de grafos, además de aparecer con mucha frecuencia también cuentan con muchas propiedades interesante. Se analizarán algunas de las más importantes.

Definición:
Diremos que un grafo es aplanable si puede ser dibujado sobre un plano de tal manera tal que ninguna arista se cruce con otra excepto, desde luego, en los vértices comunes. El siguiente es un grafo aplanable:

el grafo i) también es aplanable ya que puede dibujarse como se muestra en el grafo ii)

Ejemplo:
La siguiente figura es un grafo no aplanable que a decir verdad corresponde al problema de determinar si es posible conectar las casas 1, 2, 3 a los servicios de Luz, Agua y Drenaje, de tal manera que no haya 2 líneas de conexión que se crucen una con la otra.

ISOMORFISMO DE GRAFOS 

En teoría de grafos, un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices  que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:

Grafo G	Grafo H	Un isomorfismo entre G y H

Dos grafos con matrices de adyacencia respectivas A y B serán isomofos si y solo si existe una matriz permutación P tal que B = P A P^t.

REPRESENTACIÓN DE GRAFOS 

Representación de grafos. Matriz de incidencia. Matriz de adyacencia. Definición 1.4.1. Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que unen los vértices vi y vj. 

Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros. 

CICLOS EULERIANOS

En la teoría de grafos, un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en el famoso problema de los puentes de Königsberg.

En la imagen,  es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

CICLOS HAMILTONIAMOS

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.

CAMINOS Y CICLOS 


CAMINOS

Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).

CICLO

Es un camino del nodo w al nodo w, esto es, un camino que regresa al mismo nodo de donde salió.

UNIDAD 4

GRAFOS 

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

APLICACIÓN AL ANÁLISIS DE ALGORITMOS  

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene 'n' elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log₂ N + 1 unidades de tiempo para devolver una respuesta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentre acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 dígitos cada uno).

UNIDAD 3

RELACIONES DE RECURRENCIA 

En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores

Una ecuación recurrente es un tipo específico de relación de recurrencia. Una relación de recurrencia para la sucesión  es una ecuación que relaciona  con alguno de sus predecesores . Las condiciones iniciales para la sucesión  son valores dados en forma explícita para un número finito de términos de la sucesión.¹

Resolver una relación de recurrencia consiste en determinar una fórmula explícita (cerrada) para el término general , es decir una función no recursiva de n.

Hay dos métodos para resolver relaciones recurrentes: iteración y un método especial que se aplica a las relaciones de recurrencia lineales homogéneas con coeficientes constantes.

Un ejemplo de una relación de recurrencia es el siguiente:

Algunas definiciones de recurrencia pueden tener relaciones muy complejas (caóticas), y sus comportamientos a veces son estudiados por los físicos y matemáticos en un campo conocido como análisis no lineal.

COEFICIENTES BINOMIALES Y TEOREMA DE BINOMIOS 


COEFICIENTE BINOMINALES 

Los coeficientes binomiales, números combinatorios o combinaciones son números estudiados en combinatoria que corresponden al número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado. Sin embargo, dependiendo del enfoque que tenga la exposición, se pueden usar otras definiciones equivalentes.

TEOREMA DE BINOMIOS

En matemática, el teorema del binomio es una fórmula que proporciona el desarrollo de la potencia n-ésima de n (siendo n, entero positivo) de un binomio. De acuerdo con el teorema, es posible expandir la potencia (x + y)ⁿ en una suma que implica términos de la forma ax^by^c, donde los exponentes b y c son números naturales con b + c = n, y el coeficiente a de cada término es un número entero positivo que depende de n y b. Cuando un exponente es cero, la correspondiente potencia es usualmente omitida del término. Por ejemplo,

El coeficiente a en los términos de x^by^c - x^cy^b es conocido como el coeficiente binomial  o  (los dos tienen el mismo valor).

PERMUTACIONES Y COMBINACIONES 

PERMUTACIONES

Se llama permutaciones de m elementos (m = n) a las diferentes agrupaciones de esos m elementos de forma que:

Sí entran todos los elementos.

Sí importa el orden.

No se repiten los elementos.

COMBINACIONES 

Se llama combinaciones de m elementos tomados de n en n (m ≥ n) a todas las agrupaciones posibles que pueden hacerse con los m elementos de forma que:

No entran todos los elementos.

No importa el orden.

No se repiten los elementos.

También podemos calcular las combinaciones mediante factoriales:

Las combinaciones se denotan por