Teoria sesión 11

Sesión correspondiente al dia (30/11/2010).

En esta sesión continuamos con el tema de grafos

• REPRESENTACIÓN MATRICIAL

-Matriz de adyacencia

Sea G un grafo con n vértices {v_i}. Llamamos matriz de adyacentes a la matriz de orden (nxn) (una matriz cuadrada, mismo número de filas y columnas) A=[a_i,j] tal que a_i,j es igual al número de aristas (arcos) del vértice v_i al v_j. Para los grafos no dirigidos los bucles se cuentan 2 veces.

La matriz de adyacencia define completamente el grafo.

EJEMPLO

Grafo no dirigido

Como se puede apreciar se trara de una matriz simétrica, los elementos de la diagonal inferior coinciden con los de la diagonal superior, a_i,j=a_j,i.

-Para un grafo no dirigido con matriz de adyacencia A, la suma de los elementos de la fila i (o columna i) es igual al grado del vértice vi.

Grafo dirigido

La fila representa el vértice origen y la columna el vértice destino.

-Para un grafo dirigido con matriz de adyacencia A, la suma de los elementos de la fila i es igual al grado de salida del vértice vi y la suma de los elementos de la columna j es igual al grado de entrada del vértice j.

-Sea G un grafo con matriz de adyacencia A. Entonces, el elemento (i, j) de la matriz A^r, r>= 1, es igual al número de cadenas r_i a r_j de longitud r.

-Matriz de incidencia

Sea G = {V, A} un grafo no dirigido con n vértices y m aristas siendo V = {v_i} y A  = {a_i}. Llamamos matriz de incidencia de G a la matriz de orden n x m.

Tenemos una matriz con “j” columnas que serán los arcos o aristas e “i” filas que serán los vértices, pero según sea un grafo dirigido o no dirigido tendremos una nomenclatura u otra.

–Grafo no dirigido:

M= [m_ij]/m_ij

->0 si v_i no es incidente con a_j

->1 si v_i es incidente con a_j

->2 si a_j es un bucle en v_i

Todas las columnas sumarán 2 porque una arista une 2 vértices. Es una forma de comprobar si hicimos bien la matriz incidente.

EJEMPLO

-Grafo dirigido:

B= [b_ij]/b_ij

->0 si v_i no es incidente con a_j

->1 si v_i es vértice inicial de a_j

->-1 si v_i es vértice final de a_j

->2 si a_j es un bucle en v_i

La suma de columnas de un grafo dirigido sin bucles da 0 porque tendremos un 1 por el arco saliente y un -1 por el entrante.

EJEMPLO

Propiedades de la matriz de incidencia:

• Para un grafo no dirigido, la suma de los elementos de cada fila de la matriz de incidencia es igual al grado del correspondiente vértice.
• Para un grafo no dirigido, la suma de los elementos de cada columna de la matriz de incidencia es igual a 2.
• Para un grafo dirigido sin bucles, la suma de los elementos de cada columna de la matriz de incidencia es igual a 0.

Tabla de aristas incidentes

Para un grafo no dirigido, llamaremos tabla de aristas incidentes a una tabla que lista, para cada vértice v, todas las aristas incidentes con v.

Tabla de arcos salientes

Para un grafo dirigido, llamaremos tablas de arcos salientes a una tabla que lista, para cada vértice v, todos los arcos salientes de v. Llamaremos tablas de arcos entrantes a una tabla que lista, para cada vértice v, todos los arcos entrantes en v.

• ACCESIBILIDAD Y CONECTIVIDAD

Sea  G = (V, A) un grafo dirigido.

1. Sean x_i , x_j ε V, diremos que x_j es alcanzable desde x_i o que x_i alcanza a x_j si existe un camino dirigido de x_i a x_j .

2. Sea V = {x_i}. Llamaremos matriz de accesibilidad asociada al grafo G a la matriz cuadrada de orden n definida por

R=[r_ij] /r_ij

->1 si x_i alcanza a x_j.

->0 en otro caso

3. Sea V = {x_i}. Llamaremos matriz de acceso asociado al grafo G a la matriz  cuadrada de orden n definida por

Q=[q_ij] /q_ij

->1 si x_i alcanzable desde x_j

->0 en otro caso

PROPOSICIÓN: Q =R^T

-CÁLCULO DE LA MATRIZ ACCESIBILIDAD

R(v_i) = conjunto de todos los vértices del grafo que son alcanzables desde el vértice v_i. Todos los elementos del conjunto son 1.

Luego como R(v_i) está formado por:

-el vértice v_i ={v_i}

-Г(v_i): conjunto de vértices alcanzable desde “v_i” mediante un camino dirigido de longitud 1.

-Г²(v): conjunto de vértices alcanzable desde “v_i” mediante un camino dirigido de longitud 2.

-Г^p(v): conjunto de vértices alcanzable desde “v_i” mediante un camino dirigido de longitud p, p<= n (número de vértices).

Podemos calcular R(v_i) de la siguiente forma:

R(v_i)= {v_i} U Г(v_i) U…U Г^p(v_i), p <= n.