Grafos

GRAFOS


1. Definiciones básicas:

Un grafo es la representación por medio de conjuntos de relaciones arbitrarias entre objetos. Existen dos tipos de grafos según la relación entre los objetos sea unívoca o biunívoca. Los primeros forman los grafos dirigidos o dígrafos y los segundos los grafos no dirigidos o simplemente grafos. En la mayor parte de los algoritmos que serán nuestroobjeto de estudio se hace referencia a la termología básica que se propone a continuación. Dicha terminología; por desgracia, no es estándar y puede llegar a variar en los distintos textos que existen en la materia. Cuando exista ambigüedad se harán las aclaraciones según sea necesario.


Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A. Los vérticesse denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación unívoca aRb pero no bRa. De modo que los arcos se representan comúnmente por medio de pares ordenados (a,b), donde se dice que a es la cabeza y b la cola del arco y a menudo se representa también por medio de una flecha, tal como se muestra enla figura 1.










Figura 1 Grafo dirigido
[pic] donde [pic] , [pic] y [pic] tal que [pic]. En dicho grafo se entiende que [pic] y en muchos casos solo existe uno de los pares de vértices.
Un vértice que solo tiene arcos saliendo de él se denomina fuente y un vértice que solo tiene arcos dirigidos hacia él se denomina sumidero. Dicha nomenclatura es importantecuando los dígrafos se usan para resolver problemas de flujos.


Un grafo no dirigido, o grafo, al igual que un dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A. La diferencia consiste en que la existencia de aRb presupone que bRa también existe y además que son iguales. De este modo es indistinto hablar del arco (a,b) o (b,a), tampoco tiene sentido hablar de lacabeza o la cola del arco. Los grafos representan como lo indica la figura 2, donde los círculos representan los vértices y las líneas representan los arcos.










Figura 2 Grafo no dirigido


[pic] donde [pic] , [pic] y [pic] tal que [pic]. En dicho grafo se entiende que [pic] y además [pic], donde ambos pares de vértices representan el mismo arco.


Existenademás grafos en donde los arcos tienen asociado algún valor en cuyo caso hablamos de grafos ponderados y ahora se representan los arcos como tripletas. Sigue existiendo la información de los vértices unidos por dicho arco además de la información del peso de dicho arco. Así pues el arco se representa como [pic] donde [pic] son el origen y destino y [pic] es el peso respectivamente.


Un nodob se dice que es adyacente al nodo a si existe el arco (a, b), tómese en cuenta que para un grafo no dirigido necesariamente a es también adyacente a b. Esto no ocurre en los grafos dirigidos donde la existencia de (a, b) no implica que (b, a) también existe. Este concepto es de particular importancia dado que los grafos suelen representarse en la computadora por medio de listas o matrices deadyacencias.
Un arco (a,b) incide en el nodo b, de igual modo en grafo no dirigido dicho arco también incide en el nodo a debido a que también existe (b, a). El número de arcos que inciden en un nodo le otorga el grado a dicho nodo. El nodo con mayor grado en el grafo le indica el grado de dicho grafo. También se acostumbra representar a un grafo por medio de listas o matrices de incidencias.Existen otras definiciones que son útiles para explicar el funcionamiento de un algoritmo en particular, se definirán los conceptos en su momento.



2. Métodos de representación en computadora

Tal como se adelanto en el apartado anterior, existen varias formas de representar un grafo en la computadora y cada una tiene sus ventajas y desventajas. Mostraremos las más...