ELEMENTOS Y CARACTERÍSTICAS DE UN GRAFO

ELEMENTOS Y CARACTERÍSTICAS DE UN GRAFO

Llamaremos grafo, G, al par ordenado formado por un conjunto finito no vacío, V, y un conjunto, A, de pares no ordenados de elementos del mismo.

V es el conjunto de los vértices o nodos del grafo.

A sera el conjunto de las aristas o arcos del grafo.

Utilizaremos la notación G = (V,A) para designar al grafo cuyos conjuntos de vértices y aristas son, Respectivamente, V y A.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

Grafos Dirigidos.

Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

Representación de grafos

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos 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, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Árboles.

Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también a cíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).

Aplicaciones de los dígrafos

Una de las aplicaciones más importantes es de hallar el camino más 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.

ALGORITMOS DE RECORRIDOS Y DE 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.

lgoritmo de búsqueda

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

APLICACIONES DE GRAFOS Y ARBOLES

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que . Para simplificar, notaremos

...