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