Flor

INTRODUCCION

Se expresa cómo ha progresado el desarrollo de un software y cuánto desarrollo puede requerir, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Un tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es un modelo matemático compuesto poruna colección de operaciones definidas sobre un conjunto de datos para el modelo.

INDICE

Pág.

Introduccion………………………………………………………… 2

Concepto de Grafo…………………………………………………….. 4-5

Representación de Equipo TDD Grafo……………………………….. 5-7

Motriz Camino………………………………………………………… 7-9

Algoritmos Fundamentales conGrafos……………………………….. 9-17

Aplicaciones…………………………………………………………… 17

Conclusión…………………………………………………………….. 18

GRAFO

Un grafo (del griego grafos: dibujo, imagen) o gráfica es el principal objeto de estudio de la teoría de grafos.

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relacionesbinarias entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual losvértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Ejemplo

[pic]

Definiciones

Un grafo G es un par ordenado G = (V, E), donde:

Ves un conjunto de vértices o nodos, y

E es un conjunto de arcos o aristas, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V |.

REPRESENTACION DE TAD GRAFOS

• Tad

Un tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es unmodelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.

Ejemplos de utilización de TDA

Algunos ejemplos de utilización de TDA en programación son:

• Conjuntos: Implementación de conjuntos con sus operaciones básicas (unión, intersección y diferencia), operaciones de inserción, borrado, búsqueda...

• Árboles Binarios deBúsqueda: Implementación de árboles de elementos, utilizados para la representación interna de datos complejos. Aunque siempre se los toma como un TDA separado son parte de la familia de los grafos.

• Pilas y Colas: Implementación de los algoritmos FIFO y LIFO.

• Grafos: Implementación de grafos; una serie de vértices unidos mediante una serie de arcos o aristas.

Grafo nodirigido:

[pic]

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:
• [pic]
• [pic]es un conjunto de pares no ordenados de elementos de [pic].
Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por[pic].

Grafo dirigido:[pic]

Un grafo dirigido o dígrafo es un grafo G = (V,E) donde:
• [pic]
• [pic]es un conjunto de pares ordenados de elementos de [pic].
Dada una arista (a, b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
MATRIZ DE CAMINOS
 
La matriz de caminos M indica los caminos de longitud 1 desde un vértice dado a otro, y el...