Alcançabilidade

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
	ALCANÇABILIDADE
O dígrafo da figura a seguir representa a rede de comunicação que existe entre sete empresas do seu estado, cuja função é veicular a informação. O direcionamento das arestas indica o sentido do fluxo da informação. Toda informação útil obtida por uma delas, e ainda não transmitida, é passada imediatamente para aquelas com as quais está ligada. 
1
2
3
4
7
6
5
Prof.: Lamounier Josino de Assis
*
*
*
MODELAGEM
Vértices de D: Empresas
Arestas de D: Linhas de comunicação entre as empresas.
RESOLUÇÃO.
Como D(V,E) é um digrafo que não possui arestas paralelas, sua matriz de adjacência é definida como a matriz quadrada A de ordem n, onde n é o número de vértices do digrafo.
aij = 1 se (i,j)  E 
 = 0 caso contrário
Prof.: Lamounier Josino de Assis
*
*
*
Matriz A
0	 1	 0	 0	0	0 0 
0	 0	 1	 0	0	1 0
0	 0	 0	 0	0	0 1 
0	 0	 1	 0	 0	0 1
1	 0	 1	 0	 0	0 0
0	 0	 0	 1	 1	 0 0
0 0 0 0 0 0 0 
Prof.: Lamounier Josino de Assis
*
*
*
Algumas Características de A.
Não possui laços aij = 0 
Soma dos elementos da linha i = grau+(i)
Soma dos elementos da coluna i = grau-(i)
Cada elemento aij não nulo de a indica a existência da aresta (i,j).
A existência de caminhos de comprimento 1 conectando dois vértices do digrafo pode ser verificada, examinando-se a matriz A. 
Prof.: Lamounier Josino de Assis
*
*
*
Condição do Problema
Solicita a procura de caminhos de comprimentos arbitrários em D, sabendo-se que eles são seqüências especiais de arestas.
Questão.
“Quando existirá uma seqüência de duas ou mais arestas conectando o vértice i ao j, em D? É possível sabê-lo a partir de A?”
Prof.: Lamounier Josino de Assis
*
*
*
Busca de Comprimento 2
Haverá tal seqüência caso exista um terceiro vértice k e as arestas (i,k) e (k,j)  D.
Uma nova matriz B pode ser definida:
bij = 1 se existir uma seqüência de duas arestas conectando i a j;
 = 0 em caso contrário.
QUESTÃO. 
É possível obter B a partir de A? 
Prof.: Lamounier Josino de Assis
*
*
*
Fixando dois vértices quaisquer de D. Por exemplo, os vértices 6 e 3, existe a referida seqüência de arestas conectando-os?
	< (6,4) (4,3) > caminho < 6,4,3) > 
	
	< (6,5) (5,3) > caminho < (6,5,3) >
Abstraindo-se da representação geometrica de D, pode-se obter esse mesmo resultado utilizando sua matriz de adjacências.
Prof.: Lamounier Josino de Assis
*
*
*
Para a seqüência procurada de formato < (6,k) (k,3) >,
basta extrair a linha 6 e a coluna 3 da matriz A. 
i = [ 0 0 0 1 1 0 0 ]	 	0		
										1
										0
										1		=2
										1
										0	
										0	
	
Como k é um elemento variável, devem ser-lhe atribuídos todos valores de 1 a 7, para que o método não fique particularizado.									
Prof.: Lamounier Josino de Assis
*
*
*
Prof.: Lamounier Josino de Assis
*
*
*
Essa informação poderia ser registrada na matriz B, atribuindo-se ao elemento b63 o valor 1, indicando a existência da seqüência procurada. Os demais valores de B podem ser obtidos da mesma forma.
B = A x A = A², uma vez que cada elemento bij é o resultado de operações feitas entre os elementos correspondentes da linha i e coluna j de A.
0	 0	 1	 0	0	1 0 
0	 0	 0	 1	1	0 1
0	 0	 0	 0	0	0 0 
0	 0	 0	 0	 0	0 1
0	 1	 0	 0	 0	0 1
1	 0	 2	 0	 0	 0 1
0 1 0 0 0 0 0 
Prof.: Lamounier Josino de Assis
*
*
*
O elemento a²ij indica o número de seqüência de duas arestas de i para j, que também é o número de caminhos de comprimento 2 de i a j, já que D não possui laços.
Obs. 
Como o que interessa é saber a existência de tais seqüências e não o número em elas ocorrem, podemos em vez de trabalhar com o produto matricial tradicional, substituí-lo pelo produto matricial lógico
	(matrizes booleanas).
O elemento a²ij = 1 indica que existe pelo menos uma seqüência de duas arestas = comprimento 2.
a²ij = 0 caso não exista tal seqüência. 
 
Prof.: Lamounier Josino de Assis
*
*
*
PRODUTO MATRICIAL LÓGICO
Prof.: Lamounier Josino de Assis
*
*
*
O elemento b63 pode ser encontrado como resultado da seguinte expressão booleana.
a61 ^ a13 = (0 ^ 0) = 0
 a62 ^ a23 = (0 ^ 1) = 0
a63 ^ a33 = (0 ^ 0) = 0
a64 ^ a43 = (1 ^ 1) = 1
a65 ^ a53 = (1 ^ 1) = 1
a66 ^ a63 = (0 ^ 0) = 0
a67 ^ a73 = (0 ^ 0) = 0
Resultado: 0 v 0 v 0 v 1 v 1 v 0 v 0 = 1
Prof.: Lamounier Josino de Assis
*
*
*
Podemos determinar novas matrizes 
	A³, A4, . . . ,Ar, onde cada elemento arij da matriz Ar informa sobre a existência de seqüências de r arestas conectando i a j.
Os elementos da matrizes Ar, r = 1,2,3,... Indicam a presença de seqüências de r arestas entre tais vértices, e algumas dessas seqüências podem ser caminhos entre eles.
QUESTÃO:
	“ De que forma se pode detectar a presença de um caminho, a partir da determinação das matrizes das seqüências.”
 
Prof.: Lamounier Josino de Assis
*
*
*
PROCEDIMENTO
Determinar as potências lógicas de A até An-1, pois caso exista , o menor caminho entre dois vértices de um digrafo de n vértices, é no pior caso igual a n-1.
A*→ matriz de alcançabilidade; guarda toda informação anterior.
	 A* = I A A1 A2 .... An-1
Obs. 
Os elementos não nulos de A* indicam a presença caminhos entre os pares de vértices a eles associados.
aij = 0; ausência de caminhos de i a j.
+
+
+
+
+
+
+
Prof.: Lamounier Josino de Assis
*
*
*
ALGORITMO DE WARSHALL
O Algoritmo de Warshall começa com A=M0 e calcula, sucessivamente M1,M2,..., Mn = A*.
Passos informais para se calcular os elementos de Mk+1, a partir da matriz Mk.
 Considere a coluna k+1 na matriz Mk
Para cada linha com um elemento 0(zero) nessa coluna, copie essa linha Mk+1.
Para cada linha com um elemento 1 nessa coluna, execute a operação booleana V(ou) dessa linha com a linha k+1 e escreva a linha resultante em Mk+1. 
Prof.: Lamounier Josino de Assis
*
*
*
Aplicar o Algoritmo de Warshall
0	 1	 0	 0	0		 
0	 0	 1	 0 0
1	 0	 0	 1	0
0	 0	 1	 0	 0	
0	 0	 0	 0	 0	
Prof.: Lamounier Josino de Assis
*