Teoría de Grafos.
La
teoría de grafos es el estudio matemático de conexiones entre entidades, ello
se formaliza a través de la noción de los nodos (cualquier tipo de entidad,) y
las aristas o lados ( relaciones
entre distintos nodos).
Prácticamente, los grafos son estructuras de
datos no lineales, ello nos brinda la libertad de establecer relaciones entre
ellos, no tenemos las restricciones de las estructuras lineales con respecto a relaciones,
por ejemplo, es impensable que en una lista yo pueda establecer relaciones
entre la cabecera y cualquier nodo elegido de forma arbitraria.
Grafos
Dirigidos y Grafos no Dirigidos.
Es posible clasificar los grafos según las
relaciones que pueden presentarse entre los nodos. Así encontramos los grafos
no dirigidos cuya relación entre nodos es bilateral y los grafos dirigidos,
cuya relación es unilateral.
Podemos Tomar una Red Social como
ejemplo, En el caso de Facebook, las personas serían los nodos, y las relaciones
de amistad entre ellas las aristas de nuestro grafo. Como dos personas pueden
comunicarse indistintamente nos encontramos ante un nodo no dirigido.
Otro tipo de relación que encontramos
en las redes sociales es la relación de seguidor, la cual es unilateral,
caracterizando un grafo dirigido, por ejemplo una persona que sigue a su marca
preferida de refresco;
Grafo no dirigido que representa la red de los amigos de Juan
Grafos
Ponderados
A su vez, si cada arista posee una cualidad
que pueda mesurarse, nos encontramos con un grafo Ponderado, por ejemplo, grado
de afinidad entre un grupo de personas*.La condición para ser ponderado es
poder expresar dicha cualidad con un valor numérico, de forma que su
implementación ayude indicando que relaciones son más fuertes. Por ejemplo si
asignamos un valor numérico a una relación de amistad teniendo en cuenta la
frecuencia con la que solemos comunicarnos.
*para
convertir el grado de afinidad en una cualidad mesurable se puede implementar
la lógica difusa, nos encontramos con un grado de afinidad que va de 0 a
1(intervalo real);
Sean X
e Y las dos personas;
a:Cantidad
de mensajes intercambiados entre X e Y;
b:total
de mensajes de X ;
b’:total
de mensajes de Y;
c:
cantidad en amigos en común entre X e Y;
d:total
de amigos de X;
d’:
total de amigos de Y;
Definimos
la función de membresía (Pertenencia al conjunto ‘amigos cercanos de X’ como:
A(x)=[(a/b)
+ (c/d)]/2
A(y)=[(a/b’)
+ (c/d’)]/2
El máximo
nivel de afinidad sería 1,(todos los mensajes registrados se dan entre ambas
personas y forman parte de los mismos círculos sociales).
Otra clasificación de Grafos son los
grafos bipartitos, donde nos encontramos con dos clases diferentes de
nodos.
Ejemplo:
Aplicación a colegios, tenemos dos clases de
nodos, colegios y personas, donde solo puede haber una relación entre un nodo
del tipo persona y un nodo del tipo colegio, pero un nodo del tipo colegio
puede estar ligado a varios nodos de tipo persona.
-------En
Construcción -----------------------
¿Por
qué es importante conocer sobre grafos?
No hay comentarios:
Publicar un comentario