Ingeniero

Definición de grafo :
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 su nombre 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 con estructuras de datos); la estructura de datos que refleja estarelació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 la mayoría de los textos de estructura de datos se utilizael termino “registro” al hacer referencia a archivos y “nodo” cuando se usan listas enlazadas, arboles 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 cadaarista con sus dos vértices.
Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.
Si el dibujo puede efectuarse sin que haya superposición de líneas, se dice que G es un grafo plano. Por ejemplo, el siguiente es un grafo plano:
puesto que es equivalente a este otro:

Representación de ungrafo :
Existen dos formas de mantener un grafo “G” en la memoria de una computadora, una se llama Representación secuencial de G, la cual se basa en la matriz de adyacencia A; la otra forma, es la llamada Representación enlazada de G y se basa en listas enlazadas de vecinos. Independientemente de la forma en que se mantenga un grafo G en la memoria de una computadora, el grafo G normalmente seintroduce en la computadora por su definición formal: Un conjunto de nodos y un conjunto de aristas
 Representación secuencial de un grafo :
Considere el grafo siguiente “G”:
y suponga que los nodos se mantienen en memoria en un array DATOS tal como sigue:
DATOS: X, Y, Z, W
Para hallar la matriz de adyacencia A del grafo “G”, tenemos que tomar en cuenta que los nodos están normalmenteordenados de acuerdo con la forma en que aparecen en memoria; o sea, asumimos que 1 = X, 2 = Y, 3 = Z, y 4 = W, la matriz de adyacencia A de G seria la siguiente:

aquí i j = 1 si hay una arista i a j ; si no i j = 0.
Así entonces para hallar la matriz de camino P de G mediante las potencias de la matriz de adyacencia A, como G tiene cuatro nodos se calcula

por lo tanto la matriz de caminosP se obtiene ahora haciendo pi j = 1 siempre que haya una entrada positiva en la matriz B4 . así

La matriz de caminos muestra que no hay camino de 1 a 2 de hecho, no hay camino de ningún nodo a 1 por tanto, G no es fuertemente conexo.
 Representación enlazada de un grafo :
Un grafo “G” se guarda en memoria como sigue:
NODO | A | B | | E | | D | C | |
SIG | 7 | 4 | 0 | 6| 8 | 0 | 2 | 3 |
ADY | 1 | 2 | | 5 | | 7 | 9 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
PRINCIPIO = 1, NDISP = 5
DEST | 2 | 6 | 4 | | 6 | 7 | 4 | | 4 | 6 |
ENL | 10 | 3 | 6 | 0 | 0 | 0 | 0 | 4 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
ADISP = 8
Para dibujar el respectivo grafo “G”, primero debemos buscar todos los...