Grafos

GRAFOS
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representamediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica sunombre lo indica es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:
Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos conestructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.
Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.
En lamayoría de los textos de estructura de datos se utiliza el termino "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, árboles y grafos.
También un grafo es una terna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente,"vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.
REPRESENTACIONES GRAFICAS
Grafo sencillo


Grafo no dirigido

Grafo dirigido

Grafo de lista de adyacencia

 
REPRESENTACION MATRICIAL
La matriz de incidencia es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representar relaciones binarias.Construcción de la matriz a partir de un grafo
1. Las columnas de la matriz representan las aristas del grafo.
2. Las filas representan a los distintos nodos.
3. Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros (0).
En el ejemplo de la figura, si sumamos las cantidades de 1's que hay en cada columna, veremos que haysolo dos. Pero si sumamos las cantidades de unos 1's que hay por cada fila, comprobaremos que los nodos 2, 4 y 5 poseen un valor de 3. Ese valor indica la cantidad de aristas que inciden sobre el nodo.


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
1. Se creauna matriz cero, cuyas columnas y filas representan los nodos del grafo.
2. Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.
Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.
Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos(elementos).
Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.
Ejemplo de grafo no dirigido
La matriz de adyacencia para el grafo no dirigido de la Figura 1 viene dada por:

Ejemplo de grafo dirigido
La matriz de adyacencia para el grafo dirigido de la Figura 2 viene dada por:


CAMINOS
Un camino en un grafo es una...