Grafis y arboles

Solo disponible en BuenasTareas
  • Páginas : 3 (629 palabras )
  • Descarga(s) : 0
  • Publicado : 7 de febrero de 2012
Leer documento completo
Vista previa del texto
REPRESENTACIONES DE GRAFOS

Un primer método de representación de un grafo lo constituye una matriz adyacente.

Considérese el grafo de la figura. Para obtener la matriz adyacencia de este grafose selecciona un orden arbitrario para los vértices, por ejemplo a, b, c, d, e. A continuación se le asigna a las filas h a las columnas de una matriz el mismo orden dado a los vértices. Un elementode la matriz es 1 si los vértices correspondientes a la fila y a la columna de dicho elementos están unidos por un lado, y 0 en caso contrario.

La matriz adyacencia para este grafo esta dadapor:



a b c d e
a 0 1 0 0 1
b 1 0 2 0 1
c 0 1 1 0 1
d 0 0 0 0 1
e 1 1 1 1 0
d e



un ejemplo de grafo simple y su matriz adyacencia A seofrece en la figura: supongase que eleva al cuadrado.


Considerese el elemento correspondiente a la fila a y a la columna c en A al cuadrado , obtenido al multipliar por pares los elementos de lafila a y los de la columna c de la matriz A, y proceer a sumarlos

La unica forma de que un elemento diferente de cero aparezca en esta suma es que los elementos que se multipliquen sean ambos, 1.Esto sucde si existe un vértice v cuyo elemento en filas a es 1 y cuyo elemento en la columna c es también 1.
En otras palabras debe existir lados de la forma (a,v) y (v,c). en caso la sumaaumenta en 1. en este ejemplo la suma es 2 pues representa los pares de lados.

(a,b) (b,c)

(a,d) (d,c)

Cada uno de los pares recibe el nombre de sucesion o secuencia de los lados de longitud 2, dede a a c, en consecuencia el elemento que corresponde a la fila x y a la columna y de la matriz A*A es el numero de suceciones de lados de longitud 2 del vértice x al vértice y .

DEFINICIONSea G un grafo con vértices V y lados E. una secesión de lados de longitud n de un vértice x a un vértice y, es un conjunto de lados S que pueden arreglarse de modo que

S={(V0, V1), (V1,...
tracking img