1. (Matrizes Booleanas) Matrizes booleanas representam situações com dois estados. Uma matriz é dita do tipo Booleana se suas entradas ai j forem iguais a 1 ou 0. Estas matrizes são aplicadas computacionalmente para descrever situações em que pretende-se analisar objetos que assumem apenas duas possibilidades de estados. Vejamos alguns exemplos a seguir.
    (a) Sejam A1, A2, A3 três aeroportos brasileiros interligados por meio de vôos diretos ou por meio de voos com escala. A matriz a seguir mostra como estes aeroportos estão interligados, onde o valor 1 representa voos diretos e 0 voos com escala.
V=(lll 1 & 0 & 1 0 & 1 & 1 1 & 0 & 1 )
O elemento ai j representa vôos que saem de Ai e chegam em Aj. Quais rotas podem ser feitas apenas com vôos diretos?
(b) A matriz V^2 representa que tipo de situação em termos de conexão entre os aeroportos?
Discuta outras aplicações de matrizes booleanas em ciência da computação e áreas afins.

Passo 1

O enunciado trata de matrizes booleanas, que são usadas para representar relações binárias (apenas dois estados: “ 1” para verdadeiro/existe e “ 0” para falso/não existe). Aqui temos uma matriz de adjacência
V = 1 & 0 & 1 0 & 1 & 1 1 & 0 & 1
cujo elemento aij vale 1 se há voo direto de Ai para Aj e 0 caso contrário.
O que nos pedem:
bul<=t (a) listar as rotas que podem ser feitas apenas com voos diretos;
bul<=t (b) interpretar o significado de V^2 em termos de conexões entre aeroportos;
bul<=t discutir outras aplicações de matrizes booleanas em computação e áreas afins.

Passo 2

Para responder (a), basta olhar todos os índices (i,j) tais que aij=1. Esses pares são
(1,1),(1,3),(2,2),(2,3),(3,1),(3,3).
Traduzindo para rotas entre aeroportos:
A1to A1 (auto-conexão), A1to A3,
A2to A2, A2to A3,
A3to A1, A3to A3.

Passo 3

O produto booleano de matrizes troca a soma e o produto usuais por “OU” e “E”, respectivamente. Assim, em (V^2)ij fazemos
(V^2)ij ;=;veek=1^3l(Vikwed>= Vkjr),
ou seja, (V^2)ij=1 se e somente se existe pelo menos um aeroporto Ak tal que haja voo direto de Ai para Ak e também de Ak para Aj. Em termos de aviação, V^2 indica para cada par (i,j) se é possível viajar de Ai a Aj com exatamente uma escala (dois trechos de voo direto).

Passo 4

Outras aplicações de matrizes booleanas incluem, entre várias:
– determinação de conectividade e fechamento transitiva em grafos (algoritmo de Warshall);
– representação de relações em bancos de dados (relação binária e consulta de existência de ligação);
– análise de circuitos digitais e redes lógicas (portas combinatórias modeladas por OR/AND);
– processamento de imagens binárias e operações de morfologia matemática;
– estruturas de dados para busca de caminhos em redes de comunicação e Internet;
– modelagem de autômatos finitos e linguagem regular, onde a matriz descreve transições possíveis.

Resposta

(a) As rotas de voo direto correspondem aos pares (i,j) com aij=1, ou seja:
A1to A1, A1to A3, A2to A2, A2to A3, A3to A1, A3to A3.
(b) A matriz V^2 informa, para cada par (i,j), se existe uma rota de dois trechos (uma escala) entre Ai e Aj, pois em produto booleano usamos “E” para concatenar voos e “OU” para escolher a escala intermediária.
Outras aplicações de matrizes booleanas aparecem em grafos (conectividade e fechamentos), bancos de dados relacionais, circuitos lógicos, processamento de imagens binárias, autômatos finitos, entre outros.

Exercícios relacionados