Algoritmo de recorrido y búsqueda

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodos de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad.

Así, para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas.

·         Recorrido en profundidad (DFS)

·         Recorrido en anchura (BFS)

Recorrido en anchura

El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial.

Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también un vector de cola auxiliar para gestionar los vértices no visitados.

En muchos casos es necesario ejecutar este algoritmo empezando en los nodos más alejados del nodo escogido como nodo inicial.

Recorrido en profundidad

El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente. De esta forma se va "profundizando" en el grafo, es decir, alejándose progresivamente del nodo inicial [2]. Esta estrategia admite una implementación simple en forma recursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido.

ALGORITMO DE BUSQUEDA

Un algoritmo de búsqueda es un algoritmo cuyo propósito es encontrar todos los vértices de un grafo G= (V, E) que satisfacen un propiedad particular. Diferentes variables de un algoritmo de búsqueda aparecen en una gran variedad de problemas. Un vértice está marcado si se sabe que es alcanzable desde el origen. Sea X el conjunto de los vértices marcados  y  Y el conjunto de los vértices no marcados (Y= V- X). Inicialmente X consta de solamente del vértice “r”. Se observa que si uE Y y uV E e, entonces se pueden marcar v. Un algoritmo de búsqueda recorre los vértices marcados en cierto orden. Se escribe ord (u) para indicar el orden de u en el recorrido.

El camino más corto

Una gráfica con pesos es una gráfica en la cual se asignan valores a las aristas y que la longitud de una ruta (camino) en una gráfica de pesos es la suma de los pesos de las aristas en la ruta. Sea w (i, j) el peso de la arista (i, j). En la graficas con pesos, con frecuencias queremos determinar la ruta más corta(es decir, un camino de longitud mínima) entre dos vértices dados.

Algoritmo de Dijkstra

El algoritmo de Dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:

§  Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.

§  Si los pesos de mis aristas son negativos no puedo usar el algoritmo de Dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Referencias:

Callejas Aboytes Ariana, S. V. (n.d.). Algoritmos de Recorrido y Búsqueda. Retrieved from Instituto Tecnológico de Querétaro, Matemáticas Discretas: http://trabajoenequipoitq.wixsite.com/matematicas-discreta/63-algoritmos-de-bsqueda

Hernandez, B. C. (n.d.). Algoritmos de recorrido y busqueda. Retrieved from SCRIBD: https://www.scribd.com/document/190139396/Algoritmo-de-recorrido-y-busqueda

Representación de los grafos

                          

El uso de matrices para representar sistemas de ecuaciones, relaciones  o grafos permite una rápida y clara manipulación de la información, así como el determinar algunas propiedades de los grafos que de otra manera serían más difíciles de obtener. Además de esto se tiene que en la computadora es más fácil el manejo de matrices, ya que se pueden tratar como arreglos o listas doblemente ligadas.

A continuación se describen las representaciones matriciales de los grafos.

•          Matriz de adyacencia (Ma)

Es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz. Se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.

•          Matriz de incidencia (Mi)

En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.

Representación Matemática y Computacional de los grafos

En matemáticas y 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 llamados graficas) Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas. 

Matemáticamente, la representación de un grafo G (V, A) es a través de una matriz M, de n x n con lo cual representamos el valor ponderado de la aristas a_ij en la entrada (i, j) de la matriz M. 

Computacionalmente un grafo se representa como una matriz de ceros y unos. Donde un cero en la posición (i, j) representa que hay camino del vértice i al vértice j y un uno, que si hay camino. En programación, una matriz se representa como un arreglo bidimensional.

Referencias:

MURILLO, J. A. (2009). Grafos. In J. A. MURILLO, Matemáticas para la computación (pp. 292-294). México: Alfaomega.

Ramírez, M. (2005, Septiembre 01). Retrieved from http://www.cimat.mx/~amor/Omi/Entrenamiento/Grafos/Capitulo1.htm

Elementos, características y componentes de los grafos

¿Qué es…?

Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es, pues, un subconjunto {a, b}, con a, b ∈ V, a = b.

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

•          Vértices (nodos)

Se indican por medio de un pequeño círculo y se les asigna un número o letra.

•          Lados (ramas o aristas)

Son las líneas que unen un vértice con otro y se les asigna una letra, número o una combinación de ambos.

•          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.

Tipo de Grafos

•          Grafos simples

Son aquellos grafos que no tienen lazos ni lados paralelos.

•          Grafo completo de n vértices (Kn)

Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

•          Complemento de un grafo (G ')

Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.

•          Grafo bipartido

Es el grafo que está compuesto por dos conjuntos de vértices, A = {a1, a2, a3..., an} y B = {b1, b2,…., bm} en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.

•          Grafo bipartido completo (Kn> m)

Es el grafo que está compuesto por dos conjuntos de vértices, uno de ellos

A = {a1, a2, a3,..., an} y otro B = {b1, b2,..., bm], y en el que cada vértice de A esta unido con todos los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se índice como Knm.

Referencias:

Murillo, J. A. (n.d.). Matemáticas para la computación. In J. A. Murillo, Matemáticas para la computación (pp. 287-292). México: Alfaomega.

RELACIONES DE CONJUNTOS

RELACIONES

Dado dos conjuntos no vacíos A y B, una relación R es un conjunto de pares ordenados en donde el primer elemento “a” está relacionado con el segundo elemento “b” por medio de cierta propiedad o característica.

aRb ®Notación

Ejemplo:

x = {a, b, c, d}

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

EJERCICIOS

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

1.-           (A)                          (B)

                8840     -------      Martillo

                9421       -------    Tenazas                

                452         --------   Pintura

                2207       -------    Alfombra

b= { (8840, Martillo), (9421, Tenazas), (2207, Alfombra) }

2.-           (A)                          (B)

                a      ---------         3

                b      --------          1           

                b      ---------        4

                c     ----------        1

   B={ (a,3), (b,1), (b,4), (c,1) }

3.-           (A)                          (B)

                Susana --------   Matemáticas

                Ruth      -------    Física                   

                Samuel --------   Economía

  B= { (Susana, Matemáticas), (Rut, Física), (Samuel, Economía) }

4.-           (A)                          (B)

                a    ------------      a

                b    ------------     b                            

 B= { (a, a), (b, b) }

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

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

                                                                      (A)                                      (B)

                                                                       a       ---------         6

                                                                       b        ------           2

                                                                       a      ---------         1

                                                                       c      ----------       1

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

                                                                    (A)                          (B)

                                                                    Rogelio   ------    Música

                                                                    Patricia    ------   Historia

                                                                    Benjamín ------  Matemáticas

                                                                    Patricia    ------   Ciencias Políticas

7.- La relación B en {  1, 2, 3, 4 } definida por

X= {  1, 2, 3, 4 }                           B7= { (1,1), (2, 1) …

Y= { 1, 2, 3, 4 }

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

               X (planeta)                          Y (posición)

                Mercurio     --------------------        1

                Venus      ------------------------       2

                Tierra      -------------------------     3

                Marte     ------------------------       4

                Júpiter    ------------------------       5

                Saturno   ------------------------      6

                Urano   ------------------------        7

                Neptuno   ----------------------       8

En los ejercicios 9 al 12 dibuje la digrafica de la relación.

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

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

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

12.- La relación del ejercicio 4

En los ejercicios 13 al 16, escriba la relación como conjunto de pares ordenados.

                             13.-

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

                             14.- 

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

                           15.-    

                                                                            B= { Ø  }

                              16.- 

                                                            B= { (b, c), (c, b), (d, d) }

REFERENCIAS:

Murillo, J. A. (2008). Matemáticas para la Computación. In J. A. Murillo, Matemáticas para la Computación (p. capitulo 3). Alfaomega.

Conjuntos

Conjuntos

Un conjunto es una colección bien definida de objetos llamados elementos o miembros del conjunto. (Georg Cantor)

Siempre se representan con una letra mayúscula.

 Por ejemplo: “Mandarina”

A= {m,a,n,d,r,i}

 A= {a,d,i,m,n,r}

Para conjuntos muy extensos se utiliza  “|” --> (tal que)

               A= {x | p(x)}

   Ejemplo:

B= {x | x es una palabra del idioma español que comienza con “e”}

Subconjuntos

Si todos los elementos de A también son elementos de B, se dice que A es subconjunto de B o que A esta contenido en B, y esto se denota como

                            A ÍB

Si A no es subconjunto de B se escribe:

A Ë B

Por otro lado, se dice que dos conjuntos A y B son iguales si tienen los mismos elementos, es decir, si se cumple que

                 A Í B y B Í A

Sean

A = {Rojo, Amarillo, Azul}

B = {Azul, Rojo, Amarillo}

Entonces

                 A = B

Ejemplo:

Considérense los siguientes conjuntos:

A = {x | xÎz;10 ≤ x ≤ 100}

B = {2, 3, 5, 11, 12, 15, 21, 30, 45, 82}

C = {12, 15, 45}

Entonces se tiene que:

C ÍB     A ËB

C ÍA     A Ë C

B ËA     B Ë C

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 circulo, ovalo o rectángulo, y la forma enque se entrelazan las figuras que representan a los conjuntos muestra la relación que existe entre los elementos de los respectivos conjuntos.

Operaciones y leyes de conjuntos

•            

• 
  

  • 
    
• Unión (A U B)

La unión del conjunto A y el conjunto B es el conjunto que contiene a todos los elementos del

conjunto A y del conjunto B.

 Intersección (A ∩ B)

 La intersección del conjunto A y el conjunto B es el conjunto que contienea todos los elementos que son comunes a los conjuntos A y B.

Complemento A’

El complemento de un conjunto A, que se denota como A', es el conjunto que contiene a todos los elementos del conjunto universo que no pertenecen al conjunto A.

    

   Diferencia (A - B)

La diferencia entre dos conjuntos arbitrarios A y B es el conjunto que condenea todos los elementos del conjunto A que no se encuentran en B.

Diferencia Simétrica (A ⊕ B)

Es el conjunto que contiene a todos los elementos que se encuentran en el conjunto A pero no están en el conjunto B y también a los elementosdel conjunto B que no están en A.

Ejercicios:

U= {1, 2, 3,…10}

A= {1, 4, 7, 10}

B= {1, 2, 3, 4, 5}

C= {2, 4, 6, 8}

        Ejercicios: 

    Instrucciones.- contesta lo que se te pida y realiza el diagrama de Venn para cada ejercicio

1    1.-  De 34 programas revisados  en programación “ctt”, 23 marcan 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?  25   

U = 34

A = 23 (compiladores)

B = 12 (lógica)       

      A Ç B = 5 

A Å B = 20

     2.-   En la biblioteca existen  libros de ciencias de la computación que tratan en ciertas medidas los siguientes temas:

• 
  
•          Compiladores
•       Estructura de datos
•          Redes

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

a)    ¿Cuántos libros contienen material exactamente sobre uno de los tres temas? 18

b)    ¿Cuántos no tienen material de redes? 26

c)     ¿Cuántos no tienen material sobre ninguno de los temas? 26

d)  ¿Cuántos libros contienen material de compiladores y redes pero no de estructuras de datos? 23         

U = 103

A = 50 (compiladores)

B = 54 (estructura de datos)

C = 51 (redes)

A Ç B = 30

A Ç C = 32

B Ç C = 35

A Ç B Ç C = 19

      3.- Pon en el paréntesis de cada uno de los incisos una “V” si la aseveración es verdadera o bien una “F” si es falso.

               a)  F Í (C-D)                                               (V)

               b) E Í D                                                     (V)

               c) E Í (C Ç D)                                             (V)

               d) (A Ç B) = 0                                              (F)

               e) (D – C) Í (B – A)                                       (F)

               f) (C  Ç D) Í U                                             (V)

               g) D = {1, 2, 3, 5, 6, 7, 8, 13, 14}                  (V)

               h) B Í A                                                       (F)

               i) U – (C  Ç D) = {4, 15, 16}                          (F)

               j) E = (C  Ç D)                                               (F)

                k) (C Å D) = {1, 2, 3, 5, 9, 10, 11, 12, 14}      (F)

                l) D – U = O                                                  (V)

                m) B – A = {5, 8}                                          (V)

 REFERENCIAS:

Murillo, J. A. (2008). Matemáticas para la Computación. In J. A. Murillo, Matemáticas para la Computación (p. capitulo 3). Alfaomega.