5.3 Algoritmos de recorrido y búsqueda

5.3 Algoritmos de recorrido y búsqueda

Existen algunas maneras útiles en las cuales se pueden ordenar sistemáticamente los nodos de un árbol. Los más importantes son: pre orden, post-orden y en-orden.

Pre orden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en pre orden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

    1. Visite la raíz

    2. Atraviese el sub-árbol izquierdo

    3. Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

    1. Atraviese el sub-árbol izquierdo

    2. Visite la raíz

    3. Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

    1. Atraviese el sub-árbol izquierdo

    2. Atraviese el sub-árbol derecho

    3. Visite la raíz

Se llama recorrido de un árbol al proceso que permite accede una vez a cada uno de los elementos de un árbol para examinar el conjunto completo. Primero se ven los algoritmos para construir el árbol, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está correcta cuando está dada en prefijo o posfijo.

Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

·         Recorrido en PREFIJO:

     1.  Visitar la raíz

     2.  Recorrer el subárbol izquierdo en prefijo

     3.  Recorrer el subárbol derecho en prefijo

·         Recorrido SUFIJO:

     1.  Recorrer el subárbol izquierdo en sufijo

     2.  Visitar la raíz

     3.  Recorrer el subárbol derecho en sufijo

·          Recorrido en POSFIJO:

     1.  Recorrer el subárbol izquierdo en postfijo

     2.  Recorrer el subárbol derecho en postfijo 

     3.  Visitar la raíz

5.3.1 El camino más corto

En la Teoría de Grafos, uno de los problemas más conocido es el del camino más corto.

El problema consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

En el grafo siguiente, Luisa y Pedro tienen que encontrar el camino más corto (en el sentido de menos “pesado”) entre los vértices a y e.

La solución es el camino abce.

5.3.2 A lo ancho

En ciencias de la computación, A *es un algoritmo informático que se utiliza amplia mente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos.

5.2.3 En profundidad

En ciencias de la computación, recorrido del grafo es el problema de visitar todos los nodos en un gráfico de una manera particular, actualización y / o control de sus valores a lo largo del camino, recorrido del árbol es un caso especial del recorrido del grafo. 

Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un grafo finito. DFS visitas los nodos secundarios antes de visitar los nodos del mismo nivel, es decir, que atraviesa la profundidad de cualquier camino en particular antes de explorar su amplitud.

El algoritmo comienza con un nodo “raíz” elegida, entonces iterativamente transiciones desde el nodo actual a una, el nodo no visitado adyacente, hasta que ya no puede encontrar un nodo inexplorado para la transición a partir de su ubicación actual.

Fuentes:

·       * Karen Nohemi Morales Galindo (s.f), 6.3 Algoritmos de recorrido y búsqueda, recuperado de: https://sites.google.com/site/matematicasmoralesgalindo/6-3-algoritmos-de-recorrido-y-busqueda

·       * 3.1. El camino más corto (s.f), de DEMO E-DUCATIVA CATEDU, recuperado de: http://e-ducativa.catedu.es/44700165/aula/archivos/repositorio//4500/4724/html/31_el_camino_ms_corto.html

* Alejandro De J. López Ortegón, Esmeralda Zurita Gallegos, Cesar A. Pech Interian, Russel Chuc Aguilar, Alinda E. Chan May, Micaela Baas Dzul (s.f), Teoria de grafos, recuperado de: http://mate-discretasj2.blogspot.mx/p/blog-page.html

5.2 Representación de los grafos

5.2 Representación de los grafos 

Los grafos pueden representarse estructuras de datos distintas.

Sea G = (V, E) un grafo simple con n=|V|, m=|E|. Definiremos la densidad del grafo como

Notar que 0 ≤ d ≤ 1, donde d=0 si todos los vértices son aislados y d=1 si el grafo es completo. Si d es cercano a cero se dice que el grafo es disperso y si d es cercano a 1 se dice que el grafo es denso.

a.       Representación por matriz de adyacencia

La matriz de adyacencia es la forma más común de representación y la más directa. Consiste en una tabla de tamaño nxn, en que la que aij tendrá como valor 1 si existe una arista del vértice i al vértice j. En caso contrario, el valor será 0. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 tanto la entrada aij como la entrada aji, puesto que se puede recorrer en ambos sentidos.

b.   Representación por listas de adyacencias

Una lista de adyacencia consiste de una lista de los vértices del grafo y para cada vértice de una lista de sus vértices vecinos.

5.2.1 Matemáticas

Por medio de la teoría de los grafos podemos resolver diversos problemas, como la síntesis para circuitos secuenciales, contadores, o sistemas de apertura. Se utiliza en diferentes áreas por ejemplo, en las áreas de Sistemas y Computación, en áreas de ingeniería.

Un grafo G es un par (V,E) donde:

o   V ={v1,…,vn} es un conjunto de vértices

o   E = {e1,…,em} es un conjunto de aristas,

o   Con cada ek Î {vi, vj}, con  vi, vj Î V, vi ≠ vj

·         Los vértices se representan como puntos y las aristas como líneas entre vértices

·         Ejemplo:

o   G = (V,E)

o   V = {a,b,c,d }

o   E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }

·         Proponer otro recorrido:

 

5.2.2 Computacional

Representación mediante matrices: La forma más fácil de guardar datos en nodos es mediante la utilización de un vector que indique los nodos, de manera que aristas entre los nodos se puedan ver como relaciones entre los índices.

Sintaxis:

Tipo_de_variable[ ][ ]… [ ]   Nombre_del_array = new  Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];

Arreglos Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0. Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo.

Sintaxis:

TipoDato nombre []=new TipoDato[Total de elementos];

Fuentes:

*6.2.1 Representación Matemática de los grafos (s.f), recuperado de: https://sites.google.com/site/matematicasmoralesgalindo/6-2-representacion-de-los-grafos/6-2-1-representacion-matematica-de-los-grafos

*6.2.2 Representación Computacional de los grafos (s.f), recuperado de: https://sites.google.com/site/matematicasmoralesgalindo/6-2-representacion-de-los-grafos/6-2-2-representacion-computacional-de-los-grafos

*1.5. Representación de grafos en el computador (s.f), recuperado de: http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_RepresentacionComputador.pdf

5.1 Elementos, características y componentes de los grafos

5.1 Elementos, características y componentes de los grafos

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. "La notación G = (V, A) se utiliza comúnmente para identificar un grafo. 

 Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. 

*  Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

*Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

*Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

*Cruce: Son dos aristas que cruzan en un punto. 

 Vértices

Son los puntos o nodos con los que está conformado un grafo. 

*Vértices Adyacentes: si tenemos un par de vértices de un grafo (U,V) y si tenemos una arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

*Vértice Aislado: Es un vértice de grado cero.

*Vértice Terminal: Es un vértice de grado 1.

Lados paralelos

Son aquellas aristas que tienen relación con un mismo par de vértices.

Lazo

Es aquella arista que sale de un vértice y regresa al mismo vértice.

Valencia de un vértice

Es el número de lados que salen o entran a un vértice.

5.1.1 Tipos de grafos

Grafo simple

Un grafo simple G = (V, A) costa de un conjunto no vacío de vértices V y de un conjunto A de pares no ordenados de elementos distintos de V, a estos pares se les llama aristas. En otras palabras, un grafo simple es un grafo en los que existe a lo más una arista que une dos vértices distintos.

Multígrafos

Un multígrafo G = (V, A) consta de un conjunto V de vértices, un conjunto A de aristas y una función f de A hacia {{u, v} | u, v ꞓ V, u ≠ v}. Se dice que las aristas a1 y a2 son aristas múltiples o paralelas si f (a1) = f (a2).

Pseudografos

Un pseudografo G = (V, A) consta de un conjunto V de vértices, un conjunto A de aristas y una función f de A hacia {{u, v} | u, v ꞓ V}. Una arista a es un bucle o lazo, si f(a) = {u; u} = {u} para algún u ꞓ V.

Grafo dirigido

Un grafo dirigido G, también llamado digrafo, es lo mismo que un multigrafo, solo que cada arista e de G tiene una dirección asignada o, en otras palabras, cada arista e está identificada por un par ordenado (u, v) de nodos G en vez del par desordenado [u. v].

Multigrafo dirigido

Un multigrafo dirigido G = (V, A) consta de un conjunto V de vértices, un conjunto A de aristas y una función f de A hacia {〈u, v 〉 | u, v ꞓ V}. Se dice que las aristas a1 y a2 son aristas múltiples o paralelas si f (a1) = f (a2).

Grafo completo

Un grafo completo es un grafo simple que tiene una arista entre cada par de vértices distintos. Es decir es aquel en el que cada par de sus vértices está interconectado entre sí.

Fuentes:

*Enrique Chávez (s.f), Elementos y Características de Los Grafos, recuperado de: https://es.scribd.com/document/310274082/Elementos-y-Caracteristicas-de-Los-Grafos

*Grafos (s.f), de Wikimedia, recuperado de: https://upload.wikimedia.org/wikipedia/.../Introducción_a_la_Teoría_de_Grafos.pdf

5. Teoría de grafos

5. TEORÍA DE GRAFOS

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). 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).

Fuentes:

* Teoría de grafos (s.f) de Universidad de Pamplona, recuperado de: http://www.unipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general/11072012/grafo3.pdf

Diagráficas

Diagráficas (grafos)

Los grafos pueden ser de dos tipos: "dirigidos” , en el que los nodos están relacionados por medio de una flecha que indica la relación, o “no dirigidos” ,  en el que no existe direccionamiento

Ejemplos:

Fuente: 

• José Alfredo Jiménez Murillo (2008), Matemáticas para la computación, Alfaomega Grupo Editor, S.A. de C. V., México

En los ejercicios 9 al 12 dibuje la digrafíca de relación:

9. La relación de ejercicio 4 en {a. b, c}

10. La relación R={ (1, 2), (2, 1), (3, 3), (1, 1), (2. 2) sobre x= {1, 2, 3}

11. La relación R={ (1, 2), (2, 3), (3, 4), (4, 1)  en {1, 2, 3, 4}

12. La relación con el ejercicio 7 (Relaciones)

En los ejercicios 13 al 16 escribe la relación de par ordenado:
13.  

R={ (a, b), (b, a), (b, d), (a, c), (c, c), (c, d)}

14.

R= {(1,1), (2,2), (3,3), (3,5), (4,3), (4,4), (5,4), (5,5)}

15.                     1                     2                          R = {0}

                                                                               R = {1,2}

16.

R = { (b, c), (c, b), (d, d)} en {a, b, c, d}

Relaciones

Relaciones

Dados 2 conjuntos no vacios A y B, una relación R es un conjunto de pares ordenados en donde el primer elemento a esta relacionado con el segundo elemento b por medio de cierta propiedad o caracteristica.

a R b

Las relaciones se forman si se cumple cierta proposición, esa proposición puede ser textual, como en el caso anterior ( “Imparten la materia” ), pero: también puede ser planteada en lenguaje matemático.

Fuente:

• José Alfredo Jiménez Murillo (2008), Matemáticas para la computación, Alfaomega Grupo Editor, S.A. de C. V., México

En los ejercicios 1 al 4, escriba la relación como un conjunto de pares ordenados

1. 8840    Martillo
        9921    Tenazas              
          452    Pintura
        2207    Alfombra   
R={(8840,Martillo), (9921,Tenazas), (452,Pintura), (2207,Alfombra)}

2. a      3
        b      1                             R= { (a,3), (b,1), (b,4), (c,1) }
        b      4
        c      1

3. Susana    Matemáticas
            Ruth    Física            
       Samuel     Economía
R= { (Susana, Matemáticas), (Ruth, Física), (Samuel, Economía)}

4. a       a
        b       b                          R={ (a,a), (b,b) }

En los ejercicios 5 al 8, escriba la relación como tabla.

5. R={(a,6), (b,2), (a,1), (c,1)}

        a     6

        b     2

        a     1

        c     1

6. R= { (Rogelio, Música), (Patricia, Historia), (Benjamín, Matemáticas), (Patricia, Ciencias Políticas)}

                Rogelio       Música

                Patricia       Historia

             Benjamín       Matemáticas

                Patricia       Ciencias Politicas

7.  La relación R en {1, 2, 3, 4} definidos por (x, y) Є  R   f x^2 >= y

         1    1

         2    1

         2    2

         2    3

         2    4

         3    1

         3    2

         3    3

         3    4

         4    1

         4    2

         4    3

         4    4

8. La relación R del conjunto X de planetas al conjunto Y de enteros definida por (x, y) Є R, si x está en la posición y respecto al sol ( El más cercano al sol en la posición en la 1, el segundo más cercano al sol en la posición 2 y así sucesivamente).

       1     Mercurio

       2     Venus

       3     Tierra

       4     Marte

       5     Júpiter

       6     Saturno

       7     Urano

       8     Neptuno

(Del ejercicio 9 en adelante en el tema diagraficas)

Diagramas de Venn

Diagramas de Venn

Los diagramas de Venn son representaciones gráficas para mostrar la relación entre los elementos de los conjuntos. Por lo general cada conjunto se representa por medio de un círculo, óvalo o rectángulo, y la forma en que se entrelazan las figuras que representan a los conjuntos muestra la relación que existe entre los elementos de los respectivos conjuntos.

Fuentes:

• José Alfredo Jiménez Murillo (2008), Matemáticas para la computación, Alfaomega Grupo Editor, S.A. de C. V., México.

Ejercicios: Establezca el universo como el conjunto U={1,2,3.....10}. Sea A= {1,4,7,10}, B={1,2,3,4,5} y C={2,4,6,8}.Liste los elementos de cada conjunto.

Ejemplo 3.17. De 34 programas revisados en programación "C++", 23 marcaron error en la compilación, 12 tuvieron fallas en lógica y 5 en lógica y compilación ¿Cuántos programas tuvieron al menos un tipo de error?

U=34 programas

A-Compilación-23

B-Lógica-12

                                                            

Ejemplo 3.18. En la biblioteca existen 103 libros de ciencias de la computación que tratan en cierta medida los siguientes temas:

• Compiladores
• Estructura de datos
• Redes

Del total, 50 libros tienen información sobre compiladores, 54 sobre estructuras de datos, 51 sobre redes, 30 sobre compiladores y estructuras de datos, 32 sobre compiladores y redes, 35 sobre estructuras de datos y redes, 19 sobre los tres temas.

                              COMPILADORES                A=50

                                                                                       30

               ESTRUCTURA DE DATOS                B=54       19

                                                                                       32

                                                REDES                 C=30

a) ¿Cuantos libros contienen material exactamente sobre uno de los tres temas? 19

b) ¿Cuantos no tienen material de redes? 11

c) ¿Cuantos no tiene material sobre ninguno de los temas? 26

d) ¿Cuantos libros contienen material de compiladores y redes pero no de estructura de datos? 13

Poner en el paréntesis de cada uno de los incisos una "V" si la aseveración es verdadera o bien una "F" si es falsa.

    

Introducción

Tema 2. Conjuntos y Relaciones

Un conjunto es una colección de elementos distinguibles entre sí, que tienen, por lo menos, una característica en común.

En matemáticas, los conjuntos son elaborados con la notación de colección y agrupamiento de objetos, esto es, simplemente utilizando elementos y pertenencia; sin embargo podemos decir que:

Un conjunto es una colección definida de elementos

Lo distintivo de los conjuntos es su delimitación; es decir, que dado un objeto se determina si éste pertenece o no al conjunto. Por ejemplo: en el conjunto de manzanas, la piña no pertenece al conjunto.

Los conjuntos se indican por medio de una letra mayúscula y los elementos de un conjunto por medio de letras minúsculas, números o combinación de ambos. Los elementos se colocan entre llaves, { }, separados por comas.

SUBCONJUNTOS

Si todos los elementos de A también son elementos de B, se dice que A es subconjunto de B o que A está contenido en B.

Fuentes:

• Matemáticas discretas (s.f), Unidad 2. lógica y teoría de conjuntos, sitio web: https://sites.google.com/site/discretas27/unidad-2-logica-y-teoria-de-conjuntos
•          José Alfredo Jiménez Murillo (2008), Matemáticas para la computación, Alfaomega Grupo Editor, S.A. de C. V., México.

  
  

PRESENTACIÓN

INSTITUTO TECNOLÓGICO SUPERIOR DE JEREZ

ALUMNA:

GUADALUPE VÁZQUEZ DE LA TORRE

NUMERO DE CONTROL:

S17070158

CARRERA:

INGENIERÍA EN SISTEMAS COMPUTACIONALES

NOMBRE DE LA MATERIA:

MATEMÁTICAS DISCRETAS

PRIMER SEMESTRE

DOCENTE:

RICARDO SALDIVAR QUEZADA