Fecho transitivo

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Na matemática, o fecho transitivo de uma relação binária R sobre um conjunto X é a relação transitiva R+ sobre o conjunto X de maneira que R+ contém R e R+ é mínimo (Lidl and Pilz 1998:337). Se a própria relação binária é transitiva, então o fecho transitivo é a própria relação; senão, o fecho transitivo é uma outra relação. Por exemplo, se X é um conjunto de aeroportos e x R y significa "existe um voo direto do aeroporto x para o aeroporto y", então o fecho transitivo de R sobre X é a relação R+: "é possível voar a partir de x para y em um ou mais voos."

Relações transitivas e exemplos[editar | editar código-fonte]

Uma relação transitiva R sobre um conjunto X é transitiva se, para todo x,y,z em X, sempre que x R y e y R z então x R z. Exemplos de relações transitivas incluem a relação de igualdade em qualquer conjunto, a relação "menor ou igual que" em qualquer conjunto linearmente ordenado, e a relação "x nasceu antes de y" no conjunto de todas as pessoas. Simbolicamente, isso pode ser descrito como: se x < y ey < z, então x < z.

Um exemplo de uma relação intransitiva é "a cidade x é alcançável através de um voo direto a partir da cidade y" no conjunto de todas as cidades. Simplesmente por haver um voo direto de uma cidade para uma segunda, e também um voo direto dessa segunda cidade para uma terceira, não implica haver um voo direto da primeira cidade para a terceira. O fecho transitivo dessa relação é uma relação diferente, que é "existe uma sequência de voos diretos que começa na cidade x e termina na cidade y". Toda relação pode ser estendida de maneira semelhante para uma relação transitiva.

Existência e descrição[editar | editar código-fonte]

Para qualquer relação R, o fecho transitivo de R sempre existe. Para comprovar isso, note que a interseção de qualquer família de relações transitivas é novamente transitiva. Além disso, existe ao menos uma relação transitiva contendo R,

Para conjunto finitos, podemos construir o fecho transitivo passo a passo, começando por R e adicionando arestas transitivas. Isso nos dá a ideia para a construção geral. Para qualquer conjunto X, podemos provar que o fecho transitivo é dado pela seguinte expressão

onde é a i-ésima potência de R, definida através de indução por

e, para ,

onde representa a composição de relações.

Para mostrar que a definição de R+ mostrada acima é a menor relação transitiva contendo R, mostramos que ela contém R, que é transitiva, e que é o menor conjunto com ambas as características.

  • : contém contém todas , particularmente contém .
  • é transitiva: todo elemento de está em um dos , então deve ser transitivo pela seguinte razão: se e , então pela composição associativa, (logo, em ) por conta da definição de .
  • é mínima: Seja qualquer relação transitiva contendo , queremos mostrar que . Isso é suficiente para mostrar que , . Bem, já que contém , . E como é transitiva, para qualquer , de acordo com a construção de e que é transitivo. Logo, por indução, contém todo , e também contém .

Propriedades[editar | editar código-fonte]

A interseção de duas relações transitivas é transitiva.

A união de duas relações transitivas não pode ser transitiva. Para preservar a transitividade, uma delas precisa manter o fecho transitivo. Isso ocorre, por exemplo, quando geramos a união de duas relações de equivalência ou duas relações de pré-ordem. Para obter uma nova relação de equivalência ou pré-ordem uma precisa manter o fecho transitivo (reflexividade e simetria—no caso de relações de equivalência—são automáticas).

Na teoria dos grafos[editar | editar código-fonte]

O fecho transitivo construindo o grafo de retorno a partir do grafo de entrada.
O fecho transitivo construindo o grafo de retorno a partir do grafo de entrada.

Na ciência da computação, o conceito de fecho transitivo pode ser pensado como a construção de uma estrutura de dados que possibilita responder problemas de atingibilidade. Isso é, será possível chegar à um nó b, partindo de um nó a em um ou mais saltos? Uma relação binária apenas informa que esse nó a está conectado ao nó b, e que o nó b está conectado ao nó c, etc. Após o fecho transitivo ser construído, como mostrado na figura abaixo, em uma operação O(1) pode se determinar que o nó d é atingível a partir do nó a. A estrutura de dados é geralmente armazenada como uma matriz, então se matriz[1][4] = 1, significa que o nó 4 é atingível a partir do nó 1 e um ou mais saltos.

O fecho transitivo de um grafo acíclico direcionado (GAD) é a relação de atingibilidade do GAD e uma ordem parcial estrita.

Na lógica e na complexidade computacional[editar | editar código-fonte]

O fecho transitivo de uma relação binária não pode, geralmente, ser expresso em lógica de primeira ordem (LPO). Isso significa que não é possível escrever uma fórmula usando predicados R e T que serão satisfatíveis em qualquer modelo se e somente se T é o fecho transitivo de R.

Na teoria dos modelos finitos, lógica de primeira ordem (LPO) estendida com um operador de fecho transitivo é normalmente chamada lógica de fecho transitivo, e abreviada LPO(FT) ou apenas FT.

Na teoria da complexidade computacional, a classe NL corresponde precisamente ao conjunto de sentenças lógicas que podem ser expressas em FT. Isso acontece porque a propriedade do fecho transitivo tem uma relação próxima com o problema NL-Completo da conectividade st, para achar caminhos direcionados em um grafo. Similarmente, a classe L é de lógica de primeira ordem com fecho transitivo e comutativo. Quando o fecho transitivo é adicionado à lógica de segunda ordem, obtemos PSPACE.

Em linguagens de consulta à banco de dados[editar | editar código-fonte]

Desde os anos 1980 o Oracle database implementa uma extensão SQL prioritária CONNECT BY... START WITH que permite a computação de um fecho transitivo como parte de uma consulta. O padrão SQL 3 (1999) um um construtor mais generalizado WITH RECURSIVE permitindo fechos transitivos serem computados dentro do processador de consultas; em 2011 esse último foi implementado por IBM DB2, Microsoft SQL Server, e PostgreSQL, entretanto não pelo MySQL (Benedikt and Senellart 2011:189).

Datalog também implementa computações transitivamente fechadas. (Silberschatz et al. 2010:C.3.6).

Algoritmos[editar | editar código-fonte]

Algoritmos eficientes para computar o fecho transitivo de um grafo podem ser encontrados em Nuutila (1995). A técnica mais simples é provavelmente o Algoritmo de Floyd-Warshall. O métodos de pior caso mais rápidos, que não são praticamente viáveis, reduzem o problema à uma multiplicação de matrizes.

Bibliografia[editar | editar código-fonte]

Referências

Ligação externa[editar | editar código-fonte]