Aplicaciones de grafos

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.

Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las aristas (o "edges" en inglés) representa los senderos de los animales o las migraciónes. Con esta información, los científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.
Aplicaciones de árboles.

Un árbol binario 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).

Para saber el contenido de todos los nodos en un árbol es necesario recorrer el árbol. Esto es debido a que solo tenemos conocimiento del contenido de la dirección de un nodo a la vez. Al recorrer el árbol es necesario tener la dirección de cada nodo, no necesariamente todos al mismo tiempo, de hecho normalmente se tiene la dirección de uno o dos nodos a la vez; de manera que cuando se tiene la dirección de un nodo, se dice que sevisita ese nodo.
Aunque hay un orden preestablecido (la enumeración de los nodos) no siempre es bueno recorrer el árbol en ese orden, porque el manejo de los apuntadores se vuelve más complejo. En su lugar se han adoptado tres criterios principales para recorrer un árbol binario, sin que de omita cualquier otro criterio diferente.
Los tres criterios principales para recorrer un árbol binario y visitar todos sus nodos son, recorrer el árbol en:
preorden:

Se ejecutan las operaciones:
1. Visitar la raíz
2. recorrer el subárbol izquierdo en preorden
3. recorrer el subárbol derecho en preorden
entreorden:
Se ejecutan las operaciones:
1. recorrer el subárbol izquierdo en entreorden
2. Visitar la raíz
3. recorrer el subárbol derecho en entreorden

postorden:

Se ejecutan las operaciones:
1. recorrer el subárbol izquierdo en postorden
2. recorrer el subárbol derecho en postorden
3. Visitar la raíz
Al considerar el árbol binario que se muestra en la figura 28 usando cada uno de los tres criterios para recorrer el árbol se tienen las siguientes secuencias de nodos:
En preorden: 
En entreorden: 
En postorden: 
Esto nos lleva a pensar en otra aplicación, el ordenamiento de los elementos de un arreglo.
Para ordenar los elementos de un arreglo en sentido ascendente, se debe construir un árbol similar al árbol binario de búsqueda, pero sin omitir las coincidencias.
El arreglo usado para crear el árbol binario de búsqueda fue
<14,15,4,9,7,18,3,5,16,4,20,17,9,14,5>

         EJEMPLO:

DEFINICION:
E  2  1  3  4
S  4  1  3  2
Si R es un conjunto finito y R es una relación se podrá representar a (F) gráficamente.
Se dibuja un circulo para cada elemento de x y se etiqueta el circulo con el elemento correspondiente de x estos círculos son llamados vestices o dados. Se dibuja una línea con dirección arista o flecha del vértice x que al vértice T  J si solo si , x i esta relacionado con y , j  (x, i R , j) la grafica de R de la representación resultante llama grafo dirigido de R.

1) Enlistar todas las trayectorias de longitud 1:
2) Enlistar todas las trayectorias de longitud 2 que inicien en el vértice 1:
3) Enlistar todas las trayectorias de longitud 3 que inicien en el vértice 2:
4) Encontrar un ciclo que inicie en el vértice 4:
5) Encontrar un ciclo que inicie en el vértice 1:
6) Encontrar un ciclo que inicie en el vértice:1

TEORIA DE LOS GRAFOS
Definición:   E  2  1  3  4
                       S  4  1  3  2

 

Ejemplo:
a) sea X = {a, b, c, d}   R= {(a, a) (a,b) (a,d) (a,c)( b,d)(d,d)(d,c)(c,a)(c,c)(c,d)}
b) sea X = { G,P,R,C}  R= {(G,P) (R,G) (C,G) (P,P) (C,R) (A,P) (G,C)}
c) Hacer la relación y el grafo sea X= {1, 2, 3,4} para todo (x, y) E R, si x ≤ y
d) X = {2, 4, 6, 8,16} para todo para todo (x,y) E R , si x > y

 

GRAFO DIRIGIDO

Problemas de los puentes de konusbero

El grafo dirigido esta indicando con flecha y aristas el lado e,i está asociado con el par ordenado de vértices e1,v2 y el lado e7 con el par ordenado de vértices v6,v6 y el lado e2 con el par ordenado de vértices v2,v5 o viceversa.
La primera publicación en la teoría de los grafos fue hecha por Leonardo de Eure en 1736, tal publicación concluye una solución conocida como problemas de los puentes de conisberg.
El problema consiste en partir de cualquier lugar (a, b, c, d); seguir caminando y pasar por cada uno de los puentes exactamente una sola vez y luego volver a pasar al punto de partida. La ruta se llama circuito o recorrido de Eure.
Una de las operaciones más importantes a realzar en un árbol binario es el recorrido de los mismos. Recorrer significa visitar los nodos o vértices del árbol de forma sistemática de tal manera que todos los nodos del mismo sean visitados una sola vez.
Recorrido de un árbol.
1) Pre orden: raíz
                  Izquierda
                  Derecha
2) Post orden: Izquierda
                        Derecha
               Raíz
2) Inorden:  Izquierda
                   Raíz
                Derecha

EJEMPLO:                                                             
PREORDEN:  50,20,10,5,15,30,80,60,55,70,100,90,120.
POSTORDEN: 5,15,10,30,20,55,70,60,90,120,100,80,50.
INORDEN:       5,10,15,20,30,50,80,55,60,70,90,100,120.
                                50
                     
                  20                      80
             
         10           30      50             100
   
5              15         55         70   90      120

ARBOLES BINARIOS DE BUSQUEDA

Ejemplo a):
Claves:   95, 80, 72, 60, 82, 81, 88, 100, 110, 106

              9                                            1                                                           15
         4      15                                  2       4                                               80         100
      3   6          20                     7      9  13    15                                    72   82              110
1           8   17    30                            8      3     5                          60      81   88      106
          7                                           19   20
 

Ejemplo:   
                                              A
                                     B      C    D   E
                              F       G     H I   J  K
                         L        M   N      O  P  Q
    
    
A) El padre de “i” es=    D
B) Los antepasados de “q” son=  K,D,E.
C)  Los hijos de “a” son=  B,C,D,E
D) Los descendientes de “b” son=  F,G.
E) “P” Y “q”   son= Hijos de K.
F) Los vértices terminales son=  L, M, N, O, P, Q.
G) Los vértices internos son= F, G, H, I, J, K.                                  
H) El subárbol con raíz en “g” es:  M, N.
I) Los hijos de “m” son=  Ninguno
J) El antecesor de “f” es= B.
K) Los vástagos de “k” son= P, Q.

          El árbol binario de búsqueda es una estructura sobre la cual se puede realizar eficientemente las operaciones de búsqueda inserción y eliminación. La inserción es una operación que se puede realizar eficientemente en un árbol binario de búsqueda la estructura crece conforme se disertan los elementos en el árbol. Los pasos se deben de realizar para insertar un elemento a un árbol binario de búsqueda son los siguientes:
1) Debe compararse la clave a insertar con la raíz del árbol. Si es mayor debe avanzar hacia su árbol derecho. Si es menor debe avanzar hacia su árbol izquierdo.
2) Repetir sucesivamente el paso 1 hasta que se cumplan las condiciones.

EJEMPLO a)

Claves:   95, 80, 72, 60, 82, 81, 88, 100, 110, 106

              9                                            1                                                           15
         4      15                                  2       4                                               80         100
      3   6          20                     7      9  13    15                                    72   82              110
1           8   17    30                            8      3     5                          60      81   88      106
          7                                           19   20
  

CLAVES:
b) 14,15,4,9,7,18,3,16,25,17.
C) 60,90,40,45,85,100,80,87,110.
d) 65,39,23,10,50,43,59,70,68,66,82
e) 50,20,10,15,80,60,30,100,5,55,90,120,70.
f)9,15,20,4,17,6,30,8,3,7.