Matematica Discreta Proyecto UMG

Un árbol binario es un tipo de árbol en que cada vértice máximo puede tener dos hijos; su nodo raíz está enlazado a dos subárboles binarios disjuntos denominados subárbol izquierdo y subárbol derecho. Los árboles binarios no son vacíos ya que como mínimo tienen el nodo raíz. Árbol Binario Lleno Es aquel árbol en el que los nodos de cada nivel tienen sus dos hijos o ninguno (si es hoja). Árbol binario completo Es aquel árbol binario lleno en que todas sus hojas están en el nivel n o n-1 considerando que para un hijo derecho hay siempre un hijo izquierdo. Por lo tanto, todo árbol binario lleno es completo, pero no la viceversa. Propiedades de Árboles Binarios Recorrido de un Árbol binario Un recorrido en un árbol binario es Una operación que consiste en visitar todos sus vértices o nodos, de tal manera que cada vértice se visite una sola vez. Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN.   En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su n...

  Definición Desde el punto de vista conceptual, un árbol es un caso particular de grafo, es un objeto que comienza con una raíz y se extiende en ramificaciones o lineas que terminan en un nodo.   Representan la estructura no-lineal y dinámica de datos más importante en computación. Dinámica porque puede cambiar durante la ejecución de un programa y no-lineal porque a cada elemento del árbol pueden seguirle varios elementos. Un árbol es una estructura jerárquica aplicada a un conjunto de elementos llamados nodos, uno de los cuales es conocido como raíz. Además, se crea una relación o parentesco entre los nodos que da lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro.   En ciencias de la computación, un árbol es una estructura de datos comúnmente usada, que emula la estructura de un árbol con un conjunto de nodos conectados.   Cada uno de los nodos de un árbol tiene cero o más nodos hijos, que están por debajo de él (en ciencias de la computació...

El grado de un vértice se puede definir como la cantidad de aristas que parten desde o hacia un mismo vértice Rutas y Circuitos de Euler Ruta de Euler: Una ruta o camino de Euler es una trayectoria que contiene todas las aristas del grafo y recorre una arista exactamente una vez   Condiciones: El Grafo debe de ser conexo Exactamente 2 vértices son de grado impar, todos los demás deben de ser de grado par Se comienza en uno de los vértices de grado impar y se termina en el otro vértice impar Circuito de Euler Un circuito de Euler es un Camino de Euler con la diferencia que empieza y termina en el mismo vértice es decir es un camino cerrado que recorre cada arista exactamente una vez   Condiciones: El grafo es conexo Todos los vértices son de grado par Se comienza y se termina en el mismo vertice Ciclos y Caminos Hamiltonianos 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 ...

  En matemáticas y en ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos. Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas). Complementos del Grafo Tipos de Grafos Un grafo dirigido o grafo orientado, es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no. Grafo simple o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo. No contiene aristas paralelas, lazos ni aristas dirigidos. Un grafo se dice conexo si, p...

El mínimo común múltiplo (mcm) es el número positivo más pequeño que es múltiplo de dos o más números. Múltiplo Los múltiplos de un número son los que obtienes cuando lo multiplicas por otros números. Múltiplo Común Mínimo Común Múltiplo Números Primos Se dice que todo número natural mayor que uno (n ∈ N, n > 1) es un número primo, si sus únicos divisores en el conjunto de los números naturales (N) son 1 y “n”. De este modo se dice también que todo número no primo es un número compuesto. Teorema Fundamental de la Aritmética Todo número entero mayor que uno (n ∈ Z, n > 1), se descompone, como producto de números primos, de manera única salvo el orden de los factores. Teorema de la División Dados enteros a, b con b diferente a 0,  existen enteros q y r tales que a = b q + r   y   0 <=  r  < |b| Al número a se le llama dividendo. Al número b se le llama divisor. Al número q se le llama cociente. Al número r se le llama residuo. Si queremos hallar el res...

La inducción matemática es un método de demostración que se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones. El método es bastante natural para usarse en una variedad de situaciones en la ciencia de la computación. Los números naturales se definen de manera inductiva. Es decir, incluso hablando muy informalmente, al describir los números naturales no podemos nombrar a todos los números naturales puesto que son infinitos, lo que hacemos normalmente es decir algo como “1 es un número natural, también 2 y 3 y 4 y así te sigues, si le sumas 1 a un número natural te da otro número natural”. Base Inducción Matemática Analogía de los Dominós Si ponemos todos nuestros dominós parados en una fila, necesitamos sólo asegurarnos de dos cosas para que se caigan: a) Que exista al menos un dominó que se caiga. b) Que si un dominó cae, empuja al siguiente.    Para la primera parte, no tiene que ser el primer dominó. Si tiramos el primero, queremos que...