Fatima Arellano

5.1 Elementos características y componentes de los grafos

5.1 Elementos y Características de los Grafos

A partir de esta figura se definen los siguientes elementos:

Vértices (nodos) 

Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a, b, c, d}.

Lados (ramas o aristas)

Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son:

L= {1, 2, 3, 4, 5, 6}.

Lados paralelos

Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P= {2,3}.

Lazo

Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6}

Valencia de un vértice

Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2

Valencia (b)=4

Valencia (c)=2

Valencia (d)=3

Aristas:

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

• 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. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un 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.

Matematicas Discretas. (s.f.). Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-1-elementos-y-caracteristicas-de-los-grafos

Matematicas Discretas. (s.f.). Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-1-1-componentes-de-un-grafo

5.3.3 En profundidad

5.3.3 En profundidad

Una Búsqueda en profundidad es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado..  

Pseudocodigo algoritmo búsqueda en profundidad

funcion buscar_en_hijos(Nodo:n)

variable encontrado=boolean

inicio

    si solucion(n->hijo)

    retornar n->hijo

    

    sino

    n1=n->hijo

    encontrado=falso    

        mientras no (encontrado)

        n1=n1->hermano

        sisolucion(n1)

        retornar n1

        

        sino

            n1=null

            romper ciclo

    

            buscar_en_hijos(n->hijo)

            n2->n->hijo

    

                mientras(n2->hermano!=null)

                n2=n2->hermano

                buscar_en_hijos(n2)

        fin si

    fin mientras

fin función

GOMEZ, D. R. (s.f.). Inteligencia Artificial. Obtenido de Inteligencia Artificial: https://sites.google.com/a/utp.edu.co/inteligencia-artificial/algoritmo-busqueda-en-profundidad

5.3.2 A lo ancho

5.3.2 A lo ancho

En ciencias de la computación, A * (pronunciado “Una estrella” (escuchar)) 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. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.) 

Ejemplo:

Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino: 

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visited 

Nota: En este ejemplo se utiliza una coma como separador decimal. 

Ilustración de la búsqueda A * para la búsqueda de ruta desde un nodo de inicio a un nodo objetivo en un robot de planificación de movimientos problema. 

Una búsqueda de * que utiliza una heurística que es de 5,0 (= ε) veces a la heurística consistente, y obtiene una ruta subóptima. 

SAUCEDO, F. E. (s.f.). Matematicas Discretas. Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/ 6-3-2-a-lo-ancho

5.3.1 El camino mas corto

5.3.1 El camino más corto

El problema de los caminos más cortos es el problema que 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 la teoría de grafos, el problema del camino más corto es el problema que 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. Un ejemplo de esto es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representarían las ciudades y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. Lo constituyen es mínima.

Ejemplo:

Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino: 

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visited 

Nota: En este ejemplo se utiliza una coma como separador decimal

SAUCEDO, F. E. (s.f.). Matematicas Discretas. Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-3-1-el-camino-mas-corto

5.3 Algoritmo de recorrido y busqueda

 5.3 Algoritmo de recorrida y busqueda

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido EN-ORDEN

• Recorrer el subárbol izquierdo en en-orden• Visitar el raíz• Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el raíz

Recorridos

Si T es un árbol con raíz n y subárboles T1, T2, . . . , Tk, entonces, El listado pre-orden de los nodos de T es la raíz n, seguida por los nodos de T1 en pre-orden, después los nodos de T2 en preorden, y así, hasta los nodos de Tk en pre-orden.

El listado post-orden de los nodos de T es los nodos de T1 en postorden, seguidos de los nodos de T2 en post-orden, y así hasta los nodos de Tk en post-orden, todos ellos seguidos de n. El listado en-orden de los nodos de T es los nodos de T1 en-orden, seguidos por n, seguidos por los nodos de T2, . . . , Tk, cada grupo.

Recorreremos el Árbol Siguiente:

Recorrido Pre Orden (RID)

El recorrido en Pre Orden del árbol es el siguiente: 15, 6, 4, 10, 20, 17, 22

Recorrido En Orden(IRD)

El recorrido en En Orden del árbol es el siguiente: 4, 6, 10, 15, 17, 20, 22

Recorrido Post Orden(IDR)

El recorrido en Post Orden del árbol es el siguiente: 4, 10, 6, 17, 22, 20, 15

En este tema trataremos las diferentes formas de hacer recorridos de un árbol de una expresión algebraica, con el fin de poder cambiar de manera algorítmica una expresión en sufijo a forma de prefijo o posfijo.

Se llama recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los elementos del árbol para examinar el conjunto completo. Primeramente 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 esta dada en prefijo o posfijo.

Recorridos

Al visitar los elementos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente. Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

Los algoritmos de recorrido de un árbol presentan tres tipos de actividades

• visitar el nodo raíz
•  recorrer el subárbol izquierdo
• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PREFIJO:

• Visitar la raíz
• Recorrer el subárbol izquierdo en prefijo
• Recorrer el subárbol derecho en prefijo

Recorrido SUFIJO:

• Recorrer el subárbol izquierdo en sufijo
• Visitar la raíz
• Recorrer el subárbol derecho en sufijo

Recorrido en POSFIJO:

• Recorrer el subárbol izquierdo en postfijo
• Recorrer el subárbol derecho en postfijo
• Visitar la raíz
• 
  

Flores, I. (22 de 11 de 2014). Relaciones y teoría de grafos. Obtenido de Relaciones y teoría de grafos.: http://equipo1mditq.blogspot.mx/2014/11/63-algoritmos-de-recorrido-y-busqueda.html 

5.2.2 Computacional

5.2.2 Computacional

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos, usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices y aunque frecuentemente se usa una combinación de ambos. 

SAUCEDO, F. E. (s.f.). Matematicas Discretas. Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-2-2-computacional