Representacion Computacional de los Grafos

Representación de grafos en el ordenador
Los grafos pueden representarse estructuras de datos distintas. Los algoritmos que se aplican sobre ellos adoptan tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso (cuando tiene muchas aristas) o disperso (muy pocas aristas).
Sea G = (V, E) un grafo simple con n=|V|, m=|E|. Definiremos la densidad del grafo como

Notar que 0 < d < 1, donde d=0 si todos los vértices son aislados y d=1 si el grafo es completo. Si d es cercano a cero se dice que el grafo es disperso y si d es cercano a 1 se dice que el grafo es denso.
Las representaciones más utilizadas de representación de los grafos son:
a. Representación por matriz de adyacencia
b. Representación por listas de adyacencias
La matriz de adyacencia es la forma más común de representación y la más directa. Consiste en una tabla de tamaño nxn, en que la que aij tendrá como valor 1 si existe una arista del vértice i al vértice j. En caso contrario, el valor será 0. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 tanto la entrada aij como la entrada aji, puesto que se puede recorrer en ambos sentidos.
Como se puede apreciar, la matriz de adyacencia siempre ocupa un espacio de n2, es decir, depende solamente del número de nodos y no del de aristas, por lo que será útil para representar grafos densos.
Una lista de adyacencia consiste de una lista de los vértices del grafo y para cada vértice de una lista de sus vértices vecinos.
Ejemplo 

Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un vértice i tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al vértice j si i y j tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de j aparecerá la correspondiente referencia al vértice i. En este caso el espacio ocupado es nm, muy distinto del necesario en la matriz de adyacencia, que era de n2. La representación por listas de adyacencia, por tanto, será más adecuada para grafos dispersos.
Un aspecto importante es que la implementación con listas de adyacencias determina fuertemente el tratamiento del grafo posterior. Una consecuencia de esto es que si un problema tiene varias soluciones la primera que se encuentre dependerá de la entrada dada. Podría presentarse el caso de tener varias soluciones y tener que mostrarlas siguiendo un determinado orden. Ante una situación así podría ser conveniente modificar la forma de meter los nodos en la lista de manera que el algoritmo mismo diera las soluciones ya ordenadas.

Representacion en los Grafos

Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n?n, A(G)=(aij) donde aij es el número de aristas que unen los vértices vi y vj.
Ejemplo

La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.
 Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.
Ejemplo

La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.

Dado un grafo dirigido o dígrafo D = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n?n, A(D)=(aij) donde aij es el número de arcos que tienen a vi como extremo inicial y a vj como extremo final.
Ejemplo 

La matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice y el número de unos que aparecen en una determinada columna es igual al grado de entrada del correspondiente vértice.

Tipos de Grafos

Se dice que el grafo G = (V, E) es

a)      un grafo regular de grado n si todos sus vértices tienen grado n.

Grafos regulares de grado 2.

Grafos regulares de grado 3.

b)      un grafo completo si cada par de vértices está unido por una arista. Se denota por K_n al grafo completo de n vértices

c)      un ciclo si V = {v₁, v₂, . . . v_n},  n³> 3, y  E = {(v₁, v₂), (v₂, v₃), . . . , (v_n, v₁)}. Se denota por C_n al ciclo de n vértices

d)      una rueda si V = {v₀, v1, v₂, . . . v_n}, n n> 3, y E = {(v₁, v₂), (v₂, v₃), . . . , (v_n, v₁), {(v₁, v₀), (v₂, v₀), . . . , (v_n, v₀) }. Se denota por W_n a la rueda de n+1 vértices

e)      un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Q_n al cubo asociado al cubo n-dimensional.

f)        un grafo bipartido si V=V₁UV₂ y cada arista de E une un vértice de V₁ y otro de V₂

g)      un grafo bipartido completo si V=V₁UV₂ y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V₁ y el otro en V₂. Se denota por K_r,s al grafo bipartido completo donde V₁ tiene r vértices y V₂tiene s vértices

Ejemplo  Una red de n ordenadores conectados a una unidad central estarían dispuestos formando un grafo del tipo W_n. Por otra parte, en un ordenador que tenga múltiples procesadores para efectuar procesamiento en paralelo, en el caso de que tenga n² procesadores, estos se pueden conectar formando una red en forma de cuadrilátero, aunque una de las formas de conexión más importantes es la de 2ⁿ ordenadores según el grafo Q_n.

Un digrafo o grafo dirigido es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados de vértices a cuyos elementos llamaremos aristas o arcos.

Al par (u, v)eE lo denotaremos por uv y diremos que u es el extremo inicial y que v es el extremo final.

V={u, v, w, x, y, z}

E={ uu, vu, vw, vy, xv, xw, yz, zy }

Un digrafo simple es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados distintos de vértices distintos a cuyos elementos llamaremos aristas o arcos.

Dado un digrafo D = (V, E), se llama grado de entrada de un vértice al número de arcos que lo tienen por extremo final y se llama grado de salida de un vértice al numero de arcos que lo tienen por extremo inicial.

Elementos y Caracteristicas de los Grafos

La teoría de grafos tiene su origen en el problema de los siete puentes de Königsberg resuelto por Leonhard Euler.

Más tarde, otros problemas influyeron en el desarrollo de la teoría de grafos como el estudio de las redes eléctricas, la enumeración de isómeros de hidrocarburos, etc.

Hoy en día es rara la disciplina científica o humanística que no utiliza la teoría de grafos. Como ejemplos podemos citar la psicología en dinámica de grupos, la sociología en los sociogramas, la física teórica, que usa los diagramas de Feynmann, donde se representan mediante líneas las partículas elementales, el estudio de flujos en redes en programación lineal e investigación operativa, los cambios de variable en el cálculo diferencial...

Dibujar un grafo para resolver un problema es un reflejo muy común, que no precisa conocimientos matemáticos. Un grafo se parece a la figura siguiente, y consta de vértices y de aristas que reúnen algunos de ellos.

En la teoría de los grafos, sólo se queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importan sus extremidades (o cabos); la posición de los vertices tampoco, y se puede variar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy leíbles.

Grafo etiquetado con 6 vertices y 7 aristas

Grafo. Un conjunto de vértices V y de aristas E, tal que cada arista se asocia a un par de vértices.

:

Bucle o Lazo: Es una arista incidente en un sólo vértice. 

Aristas paralelas. Cuando dos o más aristas están asociadas con el mismo par de vértices.

Grado o valencia de un vértice “v”. Es el número de aristas incidentes en “v”. Ejemplo:

Grado o Valencia de la Figura 2

V1	V2	V3	V4	V5
3	3	5	1	3

Subgrafos. Parte de un grafo.

Introduccion a la Teoria de Grafos

 La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelizar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.