Aplicaciones De Grafos

Aplicaciones De Grafos

!!! APLICACIONES DE LOS GRAFOS Y ARBOLES

APLICACION DE LOS GRAFOS

Una de las aplicaciones mas importantes es de hallar el camino mas corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de árboles, sirve para la representación de algoritmos, etc. Un ejemplo de esto es la tarea de freír un huevo.

Los grafos pueden ser utilizados como la estructura básica para múltiples aplicaciones en el área de la Computación. Un grafo G (N, A, f) es un conjunto no vacío, donde:•N={n1, n2, … ,nM) es el conjunto de nodos o vértices•A={a1, a2, …, a K} es el conjunto de aristas y•La función f : R →Μ×Μindica los pares de nodos que están relacionados.•Grafos Dirigidos (Dígrafos) En estos grafos, las aristas que comunican dos nodos tienen un único sentido, una arista puede ir de x a y, pero no de y a x. Se expresa gráficamente con flechas que indican el sentido de la relación entre cada par de nodos.

Grafos•Grafos no dirigidos En estos grafos, las aristas que comunican dos nodos tienen dos sentidos. Si una arista va de x a y, la misma arista va de y a x. Se expresa gráficamente por líneas. La representación gráfica de un grafo se define con un círculo o rectángulo para los nodos y las relaciones con líneas o flechas según sea un grafo no dirigido o un dígrafo, respectivamente.

APLICACION DE LOS ARBOLES

Un árbol es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.

Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene elementos, se deben hacer comparaciones, claro, no es mucho problema si es un número pequeño, pero el problema se va complicando más a medida que aumenta.

Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo.

El primer número del arreglo se coloca en la raíz del árbol (como en este ejemplo siempre vamos a trabajar con árboles binarios, simplemente diremos árbol, para referirnos a un árbol binario) con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:

Si el elemento del arreglo es igual que la información del nodo raíz, entonces notificar duplicidad. Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijo izquierdo. Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho. Una vez que ya está creado el árbol, se pueden buscar los elementos repetidos. Si x el elemento buscado, se debe recorrer el árbol del siguiente modo:

Sea k la información del nodo actual p. Si entonces cambiar el nodo actual a right(p), en caso contrario, en caso de que informar una ocurrencia duplicada y en caso de que cambiar el nodo actual a left(p).

El siguiente algoritmo

leer numero buscado >> n tree=makeTree(n) while(hay numeros en el arreglo){

  leeSiguienteNumero >> k
  p=q=tree;
  while(k!=info(p)&&q!=NULL){
    p=q
    if(k<info(p))
       q=left(p)
      else
       q=right(p) 
  }
  if(k==info(p))
    despliega<<” el numero es duplicado”;
   else
     if (k<info(p))
       setLeft(p,k)
      else
       setRight(p,k)  

}

INSTITUTO TECNOLOGICO DE TAPACHULA


Mis sitios nuevos:
Emprendedores
Politica de Privacidad