Discretas

6.2 Representación de los grafos
Definición.- Dado un grafo G = (V, E) con  n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n,  A(G)=(aij) donde  aij es el número de aristas que unen los vértices vi y vj.   
La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) está compuesta sólo por ceros. Si el grafo essimple  entonces la matriz de adyacencia contiene  solo ceros y unos (matriz binaria) y la diagonal está compuesta sólo por ceros. 


Definición .- Dado un grafo simple  G = (V, E) con  n=|V| vértices {v1, ..., vn}  y m=|E|  aristas  {e1, ..., em},  su  matriz de incidencia  es la matriz de orden  nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario. La matriz deincidencia sólo contiene ceros y unos (matriz binaria). Como cada arista  incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.


6.2.1 Representación Matemática de los grafos?
Existen diferentes formas de representar un grafo(simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datosusada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersosporque tienen uneficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista
lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.4
lista de adyacencia - Cada vértice tiene una lista de vértices los cuales sonadyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
lista de grados - También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo.
Estructuras matriciales 
Matrizde incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado)
 
 
Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño , donde   es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento   es 1, de locontrario, es 0













6.2.2 Representación Computacional de los grafos?
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 mantengaun grafo G en la memoria de una computadora, el grafo G normalmente se introduce 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, WPara hallar la matriz deadyacencia A del grafo “G”, tenemos que tomar en cuenta que los nodos están normalmente ordenados de acuerdo con la forma en que aparecen en memoria; o sea, asumimos que  V1 = X,  V2 = Y, V3 = Z, y V4 = W, la matriz de adyacencia A de G sería la siguiente:


aquí  ai j  = 1  si hay una arista  Vi   a  Vj  ;  si no  ai j  = 0.      

Así entonces para hallar la matriz de camino P de G mediante las...