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.

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 y no dirigido, un árbol recubridor mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.

Un ejemplo sería una compañía de cable trazando cable a una nueva vecindad. Si está limitada a trazar el cable por ciertos caminos, entonces se hará un grafo que represente los puntos conectados por esos caminos. Algunos de estos caminos podrán ser más caros que otros, por ser más largos. Estos caminos serían representados por las aristas con mayores pesos. Un árbol recubridor para este grafo sería un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas. Puede haber más de un árbol recubridor posible. El árbol recubridor mínimo será el de menos coste.

En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer porinducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores.

Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.

ARBOLES DE EXPANSION

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.

ARBOLES

Arboles:

Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.

Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.

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.

Ejemplo de árbol raíz:

Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.

Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.

En cualquier árbol R= (V,A), |V| = |A| + 1.

Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.

Sea G un grafo simple con v vértices, entonces se puede decir:

• G es un árbol.
• G es conexo y no contiene circuitos.
• G es conexo y tiene (n-1) lados.
• G no contiene circuitos y tiene (n-1) lados.

Arboles con Raíz

Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.

Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, ..., vn), es un camino en G.

• V(n-1) es el padre de v(n).
• V0, v1, ..., v(n-1) son los antepasados de v(n).
• V(n) es el hijo de v(n-1).
• Si x es un antepasado de y, entonces y es un descendiente de x.
• Si x e y son hijos de z entonces x e y son hermanos.
• Si x no tiene hijos entonces x es un vértice terminal.
• Si x no es un vértice terminal, entonces x es un vértice interno.
• El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.

Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si |V| > 1, sean R1, R2, R3, ...., Rk los subarboles de R según se va de izquierda a derecha.

El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.

El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,...., Rk en orden simétrico.

El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,...., Rk en orden posterior y a continuación por la raíz.

Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.

Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.

Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.

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érticesu 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

La determinación de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no, se conoce como el problema del isomorfismo de grafos. Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n! biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, al menos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a O(eⁿ).

El problema del isomorfismo de grafos presenta una curiosidad en teoría de complejidad computacional al ser uno de los pocos problemas citados por Garey y Johnson en 1979 pertenecientes a NP de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo (actualmente está en revisión la demostración de que el problema está en P)

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.

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  también es aplanable ya que puede dibujarse como se muestra en el grafo 

CAMINOS Y CICLOS

En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota C_n. El número de vértices en un grafo C_n es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes.

si  es un ciclo C_n, el grafo tiene n vértices  y n aristas formadas de la siguiente manera:

Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su recorrido. Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último. La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2..
Un caminoeuleriano recorre todas las aristas exactamente una vez (puede repetir vértices).	Camino euleriano Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es dual a la de camino hamiltoniano.
Un camino hamiltonianorecorre todos los vértices exactamente una vez.	Camino hamiltoniano Existe un concepto dual al de camino/ciclo Euleriano. Un camino hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez.
Orden en que se recorre un grafo en una búsqueda en profundidad.	Ciclo Un Ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 se denominan lazos o bucles. Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final.
Un ciclo euleriano pasa por todas las aristas exactamente una vez, regresando al punto de partida.	Ciclo euleriano Un ciclo euleriano en un grafo es un ciclo que usa cada arista una y sólo una vez.
Un ciclo hamiltoniano pasa por todos los vértices exactamente una vez, regresando al punto de partida.	Ciclo hamiltoniano Un ciclo hamiltoniano en un grafo es un cic

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 computadoraspuede 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 sercables 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.

PROBLEMAS DE LOS PUENTES DE KOINSBERG

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?

Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.

De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como «grado» al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par

APLICACION AL ANALISIS 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).

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.

Para resolver una relación de recurrencia asociada a la sucesión:  por iteración, utilizamos la relación de recurrencia para escribir el n-ésimo término  en términos de algunos de sus predecesores. Luego utilizamos de manera sucesiva la relación de recurrencia para reemplazar cada uno de los términos por algunos de sus predecesores. Continuamos hasta llegar a alguno de los casos base.

coeficiente binomiales y teorema de binomios

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.

Se tiene un conjunto con 6 objetos diferentes {A,B,C,D,E,F}, de los cuales se desea escoger 2 (sin importar el orden de elección). Existen 15 formas de efectuar tal elección

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

El número de formas de escoger k elementos a partir de un conjunto de n, puede denotarse de varias formas:^{nota 2} , , , o . Así, en el ejemplo anterior se tiene entonces que C(6,2)=15, puesto que hay 15 formas de escoger 2 objetos a partir de un conjunto con 6 elementos.

Los números C(n,k) se conocen como «coeficientes binomiales», pero es frecuente referirse a ellos como «combinaciones de n en k», o simplemente «n en k». Por tanto, la primera definición es:

El coeficiente binomial  es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

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 lapotencia (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).

PRINCIPIOS DE CONTEO, COMBINACIONES, PERMUTACIONES

Hay dos principios básicos de conteo, uno comprende la adición y otro la multiplicación. 1.- Principio de la suma o adición: Supongamos que un evento E puede ocurrir en m formas y un segundo evento F puede ocurrir en n formas, y supongamos que ambos eventos no pueden ocurrir en forma simultánea (disjuntos o mutuamente excluyentes).

 Entonces E o F pueden ocurrir de m+n formas. 2.- Principio de la multiplicación: Supongamos que un evento E puede ocurrir en m formas e independientemente de este evento, un evento F puede ocurrir en n formas.

 Entonces las combinaciones de los eventos E y F pueden ocurrir en mn formas.

 COMBINACIONES: Una combinación es un arreglo donde el orden NO es importante. La notación para las combinaciones es C(n,r) que es la cantidad de combinaciones de "n" elementos seleccionados, "r" a la vez.

Es igual a la cantidad de permutaciones de "n" elementos tomados "r" a la vez dividido por "r" factorial.. Esto sería P(n,r)/r! en notación matemática . Ejemplo: Si se seleccionan cinco cartas de un grupo de nueve,¿cuántas combinaciones de cinco cartas habría? La cantidad de combinaciones sería: P(9,5)/5! = (9*8*7*6*5) (5*4*3*2*1) = 126 combinaciones posibles.

 PERMUTACIONES: Dado de un conjunto de n elementos, se denomina permutación a cada uno de los conjuntos que se pueden formar con estos elementos tales que cada uno de ellos difiere de otro en el orden en que son considerados los elementos.

 Ejemplo:

 Un grupo de 5 personas va a sentarse en fila para una foto. ¿Cuántas disposiciones son posibles? 1a pos: 5 2a pos: 4 3a pos: 3 4a pos: 2 5a pos :1 Cualquiera de las cinco personas puede ocupar la primera posición de la fila. Para la segunda posición podemos elegir entre cuatro personas.

Continuando de esta manera, sólo tenemos una persona para ocupar la quinta posición.
 Esto produce un total de 5.4.3.2.1 = 120 dispociones posibles de la cinco personas. Se obtiene exactamente la misma respuesta si las posiciones se ocupan de otro orden.

RELACIONES

Relación matemática, se trata de la correspondencia que existe entre dos conjuntos: a cada elemento del primer conjunto le corresponde al menos un elemento del segundo conjunto.

Cuando a cada elemento de un conjunto le corresponde solo uno del otro, se habla de función. Esto quiere decir que las funciones matemáticas siempre son, a su vez, relaciones matemáticas, pero que las relaciones no siempre son funciones.

En una relación matemática, al primer conjunto se lo conoce como dominio, mientras que el segundo conjunto recibe el nombre de rango o recorrido. Las relaciones matemáticas existentes entre ellos se pueden graficar en el esquema llamado plano cartesiano.

 Supongamos que el dominio se llama M y el rango, N. Una relación matemática de M en N será un subconjunto del producto cartesiano M x N. Las relaciones, en otras palabras, serán pares ordenados que vinculen elementos de M con elementos de N. Si M = {5, 7} y N = {3, 6, 8}, el producto cartesiano de M x N serán los siguientes pares ordenados: M x N = {(5, 3), (5, 6), (5, 8), (7, 3), (7, 6), (7, 8)}

 Con este producto cartesiano, se pueden definir diferentes relaciones. La relación matemática del conjunto de pares cuyo segundo elemento es menor a 7 es R = {(5, 3), (5, 6), (7, 3), (7, 6)} Otra relación matemática que puede definirse es aquella del conjunto de pares cuyo segundo elemento es par: R = {(5, 6), (5, 8), (7, 6), (7, 8)} Las aplicaciones de las relaciones matemáticas trascienden los límites de la ciencia, ya que en nuestra vida cotidiana solemos hacer uso de sus principios, muchas veces de manera inconsciente.

Seres humanos, edificios, electrodomésticos, películas y amigos, entre otros muchos, son algunos de los conjuntos más comunes de interés para nuestra especie, y a diario establecemos relaciones entre ellos para organizarnos y participar de nuestras actividades.

 De acuerdo con el número de conjuntos que participen del producto cartesiano, es posible reconocer diversos tipos de relación matemática, algunos de los cuales se definen brevemente a continuación.