GRAFOS EN ESTRUCTURA DE DATOS

GRAFOS

1. Historia de los grafos 

2. Formas e representación de los grafos

2.1 Matriz adyacente

2.2 Grafos no orientados

2.3 Grafos orientados

2.4 Lista de adyacencia

3. Aplicación de grafos en estructuras de datos

4. Estructuras de datos 

4.1 Estructura correspondiente a un vértice(grafo no orientado)

4.2 Estructura básica de un grafo

4.3 Estructura correspondiente a una arista(grafo orientado) 

Historia de los grafos 

Los grafos nacieron debido a la problemática de los puentes de "Königsberg" en el año 1730 el matemático Euler necesito crear una herramienta que le fuera útil para resolver el problema; el cual trata de que solo una vez recorra los 7 puentes, en donde tendría que partir de cualquier punto y debía llegar al lugar de partida.


Para demostrar que de esta forma no podría ser posible resolver este problema, Euler modifico este mapa en donde reemplazo los puntos de partida por puntos y los puentes por arcos, como se muestra en esta imagen:

El problema expuesto es encontrar un camino que recorra el grafo pasando una vez por cada arista y la solución que le dio Euler fue que en cada punto debe incidir un numero par de lineas, esta regla fue llamada el ciclo euleriano.

Partiendo de esta creación se empezó a utilizar este modelo gráfico para física, química y matemáticas (teoría de conjuntos-análisis numérico) entre otros.

Formas de representación de grafos

• Matriz de adyacente: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

Grafos no orientados: un grafo se define como un conjunto de dos o mas elementos por ejemplo X=(U,V);

En donde U es un conjunto finito y no vació de elementos llamados vértices y V es el conjunto de elementos que se compone de subconjuntos de U de cardinalidad llamadas aristas. 

Grafos orientados: un grafo orientado se caracteriza por las flechas que asignan hacia el otro nodo por lo tanto cuando sus aristas tienen asignadas direcciones, osea cuando existe una relación de precedencia entre los elementos.

• Las lineas son los arcos
• Los puntos son los nodos

• Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.  

Aplicación de grafos en estructura de datos 

Un grafo en el ámbito de las ciencias de la computación es un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos(también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.

Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

• 6 vértices 
• 7 aristas 

Estructuras Internas

Esta representación tiene tres estructuras diferenciadas

• 1. Estructura correspondiente a un vértice:
• nodo: Código interno que permite numerar los nodos de 1 a n.
• etiq: Puntero a carácter en el que se encuentra la información que posee ese vértice, es decir su etiqueta.
• ady: Es un puntero a una lista que contiene las aristas que tienen como origen ese vértice.
• inc: Es un puntero a una lista que contiene las aristas que tienen como destino ese vértice (solo para grafos dirigidos).
• sig: Es un puntero que apunta al vértice que ocupa la posición siguiente dentro de la lista de vértices.

• 2. Estructura básica del grafo:
• En realidad se usa la misma estructura que para los nodos pero poniendo los campos etiqueta, adyacencia y siguiente a NULL. Los dos campos restantes contienen:
• nodo: Contiene el número de nodos del grafo.
• sig: Es un puntero que apunta al vértice que ocupa la primera posición dentro de la lista de vértices.

• 3. Estructura correspondiente a una arista (grafo dirigido):
• origen: Es un puntero al vértice que es el origen de esa arista.
• destino: Es un puntero al vértice que es el destino de esa arista.(Nosotros hemos sustituido el puntero por la etiqueta del nodo destino para mayor claridad del dibujo).
• valor: Este campo contiene el peso de la arista que sera un numero entero.
• sig: Puntero que apunta a la siguiente arista dentro de la lista de aristas adyacentes o incidentes.