5.2 Representación de los grafos
Los grafos pueden representarse estructuras de
datos distintas.
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.
a. Representación por matriz de
adyacencia
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.
b. Representación por listas de
adyacencias
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.
5.2.1 Matemáticas
Por medio de la teoría
de los grafos podemos resolver diversos problemas, como la síntesis para
circuitos secuenciales, contadores, o sistemas de apertura. Se utiliza en
diferentes áreas por ejemplo, en las áreas de Sistemas y Computación, en áreas
de ingeniería.
Un grafo G es
un par (V,E) donde:
o V
={v1,…,vn} es un conjunto de vértices
o E =
{e1,…,em} es un conjunto de aristas,
o Con
cada ek Î {vi, vj}, con vi,
vj Î V, vi ≠ vj
· Los
vértices se representan como puntos y las aristas como líneas entre vértices
· Ejemplo:
o G
= (V,E)
o V
= {a,b,c,d }
o E
= {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }
· Proponer
otro recorrido:
5.2.2 Computacional
Representación
mediante matrices: La forma más fácil de guardar datos en nodos es mediante la
utilización de un vector que indique los nodos, de manera que aristas entre los
nodos se puedan ver como relaciones entre los índices.
Sintaxis:
Tipo_de_variable[
][ ]… [ ] Nombre_del_array = new
Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];
Arreglos
Unidimensionales: Es un arreglo que solo posee una dimensión, está formado por
un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y
se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.
Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del
arreglo.
Sintaxis:
Fuentes:
*6.2.1 Representación
Matemática de los grafos (s.f), recuperado de: https://sites.google.com/site/matematicasmoralesgalindo/6-2-representacion-de-los-grafos/6-2-1-representacion-matematica-de-los-grafos
*6.2.2 Representación Computacional de los grafos
(s.f), recuperado de: https://sites.google.com/site/matematicasmoralesgalindo/6-2-representacion-de-los-grafos/6-2-2-representacion-computacional-de-los-grafos
*1.5. Representación de grafos en el computador (s.f),
recuperado de: http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_RepresentacionComputador.pdf
No hay comentarios:
Publicar un comentario