Tema 6: Accesibilidad y conectividad (Sesión 30/11/2010)

Y comenzamos con el tema 6 de matemáticas 1: Accesibilidad y conectividad.

ACCESIBILIDAD

Sea G = {V,A} un grafo dirigido.

1. Sean x_i y x_j dos vértices dentro del conjunto de vértices de G, diremos que x_i alcanza a x_j, o que x_j es alcanzable por x_i, si existe un camino dirigido de x_i a x_j.

2. Sea V = {x_i} _{i –> n} = 1. Llamaremos matriz de accesibilidad asociada al grafo G a la matriz cuadrada de orden n definida por:

R = [r_ij] / r_ij =>

1 si el vértice x_i alcanza a x_j.
0 en otro caso.

3. Sea V = {x_i} _{i –> n} = 1. Llamaremos matriz de acceso asociada al grafo G a la matriz cuadrada de orden n definida por:

Q = [q_ij] / q_ij =>

1 si el vértice x_i es alcanzable desde x_j.
0 en otro caso.

Proposición Q = R^T