Un Grafo es
básicamente un objeto geométrico aunque sea un objeto combinatorio, es decir,
un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de
líneas que une cada par de vértices.
Los grafos son
estructuras de datos no lineales que tienen una naturaleza dinámica. Su estudio
podría dividirse en dos grandes bloques:
GRAFOS DIRIGIDOS: Los
arcos en el grafo tienen una dirección asociada. El primer elemento del arco es
el origen y el segundo es considerado el destino.
GRAFOS NO
DIRIGIDOS (pueden ser considerados un caso particular de los anteriores):
Los arcos en el grafo no tienen una dirección particular, es decir, son
bidireccionales.
Un grafo es una
estructura de datos que almacena datos de dos tipos:
Vértices o nodos, con
un valor almacenado.
Aristas o arcos: cada
una conecta a un vértice con otro, y puede tener un valor almacenado. Una
arista es un par de vértices (x, y). Si el par está ordenado, se dice que el
grafo es dirigido o que es un dígrafo.
El conjunto de nodos o
vértices es {A, B, C, D, F, G, H} y
El conjunto de arcos o
aristas es {(A, B), (A, D), (A, C), (C, D), (C, F), (E, G), (A, A)} para el
siguiente grafo:
Matriz de adyacencia:
La matriz de
adyacencia es una matriz cuadrada que se utiliza como una
forma de representar relaciones binarias.
Construcción de la
matriz a partir de un grafo
-
Se
crea una matriz cero, cuyas columnas y filas representan
los nodos del grafo.
- Por
cada arista que une a dos nodos, se suma 1 al valor que hay
actualmente en la ubicación correspondiente de la matriz.
