Grafos

Solo disponible en BuenasTareas
  • Páginas : 8 (1798 palabras )
  • Descarga(s) : 0
  • Publicado : 7 de noviembre de 2012
Leer documento completo
Vista previa del texto
INTRODUCCIÓN
Los grafos son el mecanismo más general para la codificación de interrelaciones entre objetos.
En este trabajo se realizará un primer estudio de los grafos como Estructura de Datos No Lineal. Se enunciarán algunas definiciones y terminologías de la Teoría de Grafos, se abordarán las operaciones sobre el TDA Grafo, se explicarán dos de los recorridos que se pueden realizar sobre ungrafo, y dos de las representaciones más usadas para implementar el TDA Grafo.
DESARROLLO

1. Definición de grafo.
Intuitivamente se puede decir que un grafo es un conjunto de puntos que pueden estar conectados entre sí dos a dos mediante aristas. Los puntos representarían los elementos del problema, y las aristas representarían la existencia o no de la relación entre los puntos.
Un ejemplode las relaciones que se establecen en los grafos se muestra en tres personas cualesquiera, llamémosle A, B y C, se puede cumplir que A sea amigo de B, B sea amigo de C y C sea amigo de A, hechos que en la práctica pueden suceder como se muestra a continuación.


Una definición de grafo más formal es: Un grafo G es un par G = (V, A) donde V es un conjunto finito de elementos que se denominanVértices y A es un conjunto de pares no ordenados , donde xЄV y yЄV, denominados Aristas o Arcos.

Cuando se dice que A es un conjunto de pares no ordenados , significa que los pares y se referirán a una misma arista, la que conecta los vértices x e y.
A continuación se muestra un ejemplo de la forma en que se representarán los grafos gráficamente. Los vértices se representarán a través decírculos con el identificador del vértice contenido dentro del círculo, y las aristas se representarán a través de segmentos que conectan los círculos que representan los vértices.



Ejemplo de representación de un grafo.

Existen además otros varios tipos de grafos que se definen a continuación.
El grafo dirigido G es un par G = (V, A) donde V es un conjunto finito de elementos que sedenominan Vértices y A es un conjunto de pares ordenados , donde xЄV y yЄV, denominados Aristas o Arcos dirigidos.
Para los grafos dirigidos tiene relevancia el orden en que se enuncian los vértices para describir una arista. Es decir, los pares y se refieren a aristas distintas, a diferencia de la definición de grafo #1.

Ejemplo de representación de un grafo dirigido.

Es importanteseñalar que es un arco del grafo dirigido pero no lo es.
Otro tipo de grafo lo determina el conjunto de Grafos Ponderados donde un grafo ponderado G es un par G = (V, A) donde V es un conjunto finito de elementos que se denominan Vértices, A es un conjunto de pares no ordenados , donde xЄV y yЄV, denominados Aristas o Arcos, donde a cada elemento de A (a cada arista) se le asocia un valor realpositivo.

Ejemplo de representación de un grafo ponderado.

El peso asociado a cada arista puede interpretarse como el costo de trasladarse de un vértice a otro. Dicho costo puede ser costo en tiempo, distancia, costo en algún determinado recurso, etc. Esto posibilita que los grafos ponderados puedan ser aplicados en múltiples problemas.
De la combinación de las definiciones de Grafo Dirigido yGrafo Ponderado se puede llegar a la definición de Grafo Dirigido Ponderado, que es otro tipo de grafo. Los Grafos Dirigidos Ponderados son grafos dirigidos con valores reales positivos asociados a cada una de sus aristas.
Existen otras definiciones de grafos pero no serán expuestos en su totalidad en este trabajo.

2. Terminología.
Luego de haber visto las definiciones de Grafo, GrafoDirigido y Grafo Ponderado, se pasará a enunciar algunas terminologías de la Teoría de Grafos que se usan generalmente.
Vértices Adyacentes: En un grafo G = (V, A), un vértice y es adyacente a otro vértice x si el par es una arista del grafo G.

Ejemplo de Vértices Adyacentes y Vértices no Adyacentes.

Camino: En un grafo G = (V, A) un camino de longitud n (n ≥ 0) es una sucesión de...
tracking img