Relações
Neste artigo, vamos aprender a usar Maple para trabalhar com relações binárias e n-árias. Nós explicaremos como usar Maple para representar relações binárias usando conjuntos de pares ordenados, usando representações utilizando de matrizes zero-um, e usando grafos dirigidos. Mostraremos como usar Maple para determinar se uma relação tem várias propriedades que utilizam estas diferentes representações.
Nós descreveremos como calcular o fechamento das relações. Em particular, mostraremos como encontrar o fechamento transitivo de uma relação utilizando dois algoritmos diferentes, e nós iremos comparar o tempo necessário para usar esses algoritmos. Depois de explicar como usar o Maple para trabalhar com relações de equivalência, mostraremos como usar o Maple para trabalhar com ordenações parciais. Mostraremos como usar Maple para fazer ordenação topológica e para determinar se uma ordenação parcial é um reticulado. Concluiremos mostrando como usar o Maple para encontrar relações de ordenações parciais.
Contents
Uma Introdução às Relações em Maple
O primeiro passo para entender as relações e sua manipulação em Maple é determinar como representar as relações em Maple. O leitor notará que não há nenhum pacote de relações específico presente em Maple, e, portanto, a implementação e a representação das relações em Maple pode assumir a forma mais conveniente para a questão em apreço. Possíveis representações de relações em Maple incluem conjuntos de pares ordenados, matrizes zero-um ou gráficos dirigidos, entre muitos outros. Para este capítulo, vamos examinar representações de par ordenado e matrizes zero-um, bem como a representação de gráfico direcionado.
Em primeiro lugar, devem representar relações como pares ordenados. Para este fim, nós construímos um typerel estruturado para as relações. (Note-se que não se pode utilizar a relação nome, uma vez que este tipo já é usado pela biblioteca do Maple). De acordo com a definição, uma relação é um conjunto de pares ordenados de qualquer tipo e de objeto qualquer. O seguinte tipo Maple reflete essa definição.
`type/pair` := [anything, anything]; `type/rel` := set(pair);
Isso é útil, uma vez que nos permite assegurar que, quando passar argumentos para funções, temos utilizado o tipo de dados correto para a entrada. Sendo o nosso tipo rel estruturado, é muito mais fácil escrever rel do que escrever set(anything, anything) após cada argumento de que deve ser interpretado como uma relação. Isso também pode ser feito À mão dentro de cada função, antes do processamento real começar, mas o Maple fornece este tipo verificação automática para nós e resulta em um código mais rápido e, mais importante para nós, mais legível.
Para um exemplo específico, suponha que desejamos estabelecer uma relação que é definida em termos de restrições numéricas, como no Exemplo 4 na página 3577 do texto. No exemplo texto, precisamos criar uma relação R no domínio A=(1,2,3,4) de modo que R={(a,b)|a divide b}. Vamos construir esta relação ao examinar cada possível par ordenado de elementos, e admitindo pares ordenados em R se, e somente se, o par ordenado satisfaz a condição apropriada. Chamaremos R de DividesRelation.
DividesRelation := proc(A::set(integer))
local i, j, temp, R;
R := {};
for i in A do
for j in A do
if (gcd(i,j) = i) then
R := R union [i, j];
fi;
od;
od;
RETURN(R);
end:
DividesRelation(1,2,3,4);
Por conveniência, nós também definir a seguinte variação.
DivRel := proc(n::posint) local i; DividesRelation(seq(i,i=1..n)); end:
Este procedimento constrói a relação divides sobre o conjunto de todos os inteiros no conjunto {1,2,3,...,n}.
Será conveniente ter à mão o seguinte procedimento para criar o dual ou opposite relação de uma determinada relação.
DualRelation := proc(R::rel) local u; map(u -> [ u[2], u[1] ], R); end:
Isto simplesmente inverte todos os pares que pertencem à relação.
Determinar Propriedades de Relações usando Maple
Maple pode ser utilizado para determinar se uma relação tem uma propriedade específica, tal como a reflexividade, simetria, antissimetria e transitividade. Isto pode ser realizado através do procedimento de criação do Maple que tomam como entrada a determinada relação, examinando os elementos da relação, e determinar se a relação satisfaz a propriedade dada.
Desde que possamos utilizar isso repetidamente, será conveniente ter uma rotina que irá extrair para nós do domínio de qualquer relação. Nós simplesmente coletamos em conjunto todos os pontos que ocorrem tanto como uma primeira ou uma segunda entrada em algum par na relação. (Não que, estritamente falando, isso não precise ser igual ao domínio da relação, Uma vez que podem, na verdade, existirem pontos no domínio que não são R-relacionados para qualquer outro ponto do domínio. Talvez seja melhor chamar a isto o effective domain (domínio efetivo) da relação.
DomainRelation := proc(R::rel) RETURN(map(u->op(1,u), R) union map(u->op(2,u), R)); end:
Em primeiro lugar, vamos examinar como determinar se uma relação é reflexiva.
IsReflexive := proc(R::rel)
local is_reflexive, # return value
u; # index into Dom(R)
is_reflexive := true;
for u in DomainRelation(R) do
is_reflexive := is_reflexive and member([u,u], R);
od;
RETURN(is_reflexive);
end:
R1 := [1,1], [1,2], [2,1], [2,2], [3,4], [4,1], [4,4]: R2 := [1,1], [1,2], [2,1]: IsReflexive(R1); IsReflexive(R2);
Vamos examinar as propriedades simétricas e antissimétricas nos próximos dois procedimentos. Para determinar se uma relação é simétrica vamos simplesmente usar a definição; isto é, verificar se para cada par (a,b) em uma relação, o par (b,a) é também membro da relação. Se descobrirmos um par (a,b) na relação para o qual o par (b,a) não está na relação, então sabemos que a relação não é simétrica. Caso contrário, deve ser simétrica. Esta é a lógica utilizada pelo procedimento seguinte.
IsSymmetric := proc(R::rel)
local i, is_symmetric;
is_symmetric := true;
for i from 1 to nops(R) do
if not member( [ R[i][2], R[i][1] ], R) then
is_symmetric := false;
fi;
od;
RETURN(is_symmetric);
end:
Para determinar se uma determinada relação R é anti-simétrica, voltamos a usar a definição. Lembre-se que para uma relação R que ser anti-simétrica, ele deve ter a propriedade de que, sempre que um par (a,b) pertencer a R, e o par (b,a) também pertence a R, então devemos ter que a=b. Para verificar isso, nós simplesmente vamos varrer todos os membros u=(a,b) de R, e veja se o par oposto (b,a) pertence a R. Se isso acontecer, e se a≠b, então R não pode ser antissimétrica; caso contrário, ela é.
IsAntiSymmetric := proc(R::rel)
local u; # index into R
for u in R do
if member([op(2,u), op(1,u)], R) and op(1, u) <> op(2, u) then
RETURN(false);
fi;
od;
RETURN(true);
end:
Agora usamos os nossos procedimentos para determinar qual das relações definidas anteriormente são simétricas ou antissimétricas.
IsSymmetric(R1); IsSymmetric(R2); IsAntiSymmetric(R1); IsAntiSymmetric(R2); R3 := [1,1], [1,2], [1,4], [2,1], [2,2], [3,3], [4,1], [4,4]: R4 := [2,1], [3,1], [3,2], [4,1], [4,2], [4,3]: IsAntiSymmetric(R3); IsAntiSymmetric(R4);
Para decidir se uma relação R é transitiva, devemos verificar se (a,c) pertencerá a R quando existirem pares (a,b) e (b,c) que pertencem a R. Fazemos isso examinando todos os pares (a,b) em R, em conjunto com todos os elementos de x do domínio D de R, para ver se um par (b,x) existe em R para o qual o par (x,b) não está em R. Se encontrarmos essa combinação, em sequencia, a relação R não pode ser transitiva; de outra forma, R será.
IsTransitive := proc(R::rel)
local DomR, # domain of R
u,v,w;# indices into DomR
for u in DomR do
for v in DomR do
for w in DomR do
if (member([u,v], R) and member([v,w], R) and not member([u,w], R)) then
RETURN(false);
fi;
od;
od;
od;
RETURN(true);
end:
IsTransitive(R1); IsTransitive(R2);
IsTransitive(R3); IsTransitive(R4);
Relações n-árias em Maple
Usando Maple, podemos construir uma relação n-ária, onde n é um número inteiro positivo. O formato para a expressão relação n-ária em Maple é semelhante à da relação 2-ária no Maple. Por exemplo, considere a seguinte relação 4-ária que representa os registros dos alunos.
M1:=[Adams, 9012345,`Politics`, 2.98],
[Woo, 9100055, `Film Studies`, 4.99],
[Warshall, 9354321, `Mathematics`, 3.66]:
O primeiro campo representa o nome do aluno, o segundo campo é o número de identificação do aluno, o terceiro campo é o departamento ao qual o estudante pertence e, finalmente, o último registro armazena a média do estudante.
Com esse exemplo de como usar as relações n-árias, nós iremos construir um procedimento geral para calcular uma determinada projeção de uma relação. O procedimento toma como entrada um conjunto de n-tuplas (enupla) como relação com a imagem, que está a ser projetada sobre. A saída deste processo é um conjunto de m-tuplas.
MakeProjection := proc(R::set, P::list)
local i, j, S, temp_list;
S := {};
for i from 1 to nops(R) do
temp_list := [];
for j from 1 to nops(P) do
temp_list := [ op(temp_list), R[ i ][ P[j] ] ];
od;
S := S union temp_list;
od;
S;
end:
Agora vamos examinar este procedimento projeção sobre a relação 4-ário que foi construído anteriormente nesta seção.
MakeProjection(M1, [3,4,1]); MakeProjection(M1, [2,4]);
Passamos agora de construir as projeções para a construção de junção das relações. A operação de junção tem aplicações em comandos de banco de dados quando as tabelas de informações precisam ser combinadas de forma significativa. A operação de junção que vamos programar em Maple segue este esquema pseudocódigo:
1- Entrada: duas relações de entrada A e B, e um parâmetro inteiro não negativo p;
2- Analisar cada elemento de A, e determinar os últimos campos de p de cada elemento;
3- Examinar todos os elementos, y, da relação B para determinar se os primeiros campos de p em y coincidem com os últimos campos p de elemento x;
4- Ao encontrar uma correspondência de um elemento em A e um elemento em B, que combinam estes elementos, colocando o resultado em C, que é devolvido como saída.
MakeJoin := proc(p, A, B)
local i, j, k, C, list_A, list_B, x,
ret_elem, is_done;
list_A := [];
list_B := [];
C := {};
for i from 1 to p do
list_B := [op(list_B), i];
list_A := [nops(B[1])-i, op(list_A)];
od;
for i from 1 to nops(A) do;
is_done := false;
x := MakeProjection(A[i], list_A);
j := 1;
while j <= nops(B) and is_done = false do
if MakeProjection(B[j], list_B) = x then
ret_elem := A[i];
for k from p+1 to nops(B[j]) do
ret_elem := [op(ret_elem), B[j][k] ];
od;
is_done := true;
fi;
j := j+1;
od;
C := C union ret_elem;
od;
C;
end:
Nós examinamos como este procedimento funciona no exemplo definido no livro, nas páginas 371 e 372, envolvendo cursos que os professores estão ensinando para determinar onde eles estão localizados no campus.
A:=[Cruz, Zoology, 335], [Cruz, Zoology, 412], [Farber, Psychology, 501], [Farber, Psychology, 617], [Grammer, Physics, 544], [Grammer, Physics, 551], [Rosen, Computer, 518], [Rosen, Mathematics, 575]: B:=[Computer, 518, N521, 14], [Mathematics, 575, N502, 15], [Mathematics, 611, N521, 16], [Physics, 544, B505, 16], [Psychology, 501, A100, 15], [Psychology, 617, A110, 11], [Zoology, 335, A100, 9], [Zoology, 412, A100, 8]: MakeJoin(2, A, B);
Representar relações como dígrafos e Matrizes Zero-Um
Como foi dito no início deste capítulo, o Maple permite representar e manipular as relações em uma variedade de formas. Vimos como o pacote combinat do Maple permite que o produto cartesiano possa ser usado para gerar relações e, nesta seção, vamos utilizar os pacotes networks (redes) e linalg para representar e manipular as relações. Nós explicamos como usar Maple para trabalhar com relações usando a representação das relações como conjuntos de pares ordenados. Nesta seção, vamos mostrar como usar o Maple para trabalhar com as relações usando dois métodos alternativos para representar essas relações. Em primeiro lugar, vamos explicar como representar relações como grafos dirigidos; isto requer o uso do pacote Maple networks. Em segundo lugar, vamos mostrar como para representar as relações utilização de matrizes zero-um; isto requer o uso do pacote Maple linalg. Veremos que o uso dessas representações alternativas de relações nos permite usar uma ampla gama de capacidades do Maple para resolver problemas que envolvem as relações.
Representando Relações Usando Grafos Dirigidos
Começamos analisando a forma de representar as relações usando grafos dirigidos em Maple, com a ajuda do pacote networks. Para começar, vamos carregar o pacote networks.
with(networks):
Agora, podemos converter nossas relações que foram representadas no formato de par ordenado em um grafo dirigido usando o seguinte algoritmo simples, chamado MakeDigraph.
MakeDigraph := proc(A::set,R::set) local G; new(G); addvertex(A, G); addedge(R, G); RETURN(G); end: G1 := MakeDigraph(1,2,3,4,R1); R1;
O procedimento novo do pacote networks cria uma ocorrência de um gráfico, e addedge faz exatamente o que seu nome sugere: ele adiciona uma borda para o gráfico que é seu segundo argumento. (Uma discussão mais completa dessas rotinas serão apresentados no Capítulo 7.)
Podemos agora usar essa representação gráfica da relação R1 para deduzir se é ou não é transitiva. Para fazer isso, usamos o algoritmo all-pairs shortest path (todos os pares de caminho mais curto), denotado como allpairs em Maple. Especificamente, desejamos determinar que se uma borda (a,b) e uma borda (b,c) ocorrem no gráfico, então a borda (a,c) deve ocorrer também. Por isso, usamos o seguinte esboço pseudocódigo.
1- Entrada: um gráfico G, que representa uma relação R;
2- Executar o algoritmo all-pairs shortest path em G, que retorna o caminho mais curto entre dois pontos quaisquer;
3- Se há um par de elementos que tem comprimento finito que é maior do que 1, então sabe que o grafo não é reflexivo;
4- Caso contrário, temos tudo (finitos) comprimentos entre os elementos um, de modo que, se (a,b) é um par e (b,c) é um par, então a distância de a para c é 1 (Uma vez que este é o único comprimento possível, já que foram eliminados os comprimentos finitos que são maiores do que 1, no passo 3), por isso (a,c) tem de ser uma borda, e, portanto (a,c) está na relação R.
5- Saída: o valor da decisão a partir das etapas 3 e 4.
A implementação deste pseudocódigo é a seguinte;
IsTransitive_G := proc(G::graph)
local i, j, S, T, is_trans;
is_trans := true;
T := allpairs(G);
S := vertices(G);
for i from 1 to nops(S) do;
for j from 1 to nops(S) do;
if T[S[i],S[j] ] > 1 and T[S[i],S[j] ] <infinity then
is_trans := false
fi;
od;
od;
is_trans;
end:
IsTransitive_G(G1);
R2;
IsTransitive_G(MakeDigraph(1,2,3,4,R2));
Você deve examinar outras formas de manipular a representação gráfica das relações em Maple. Em particular, depois de ter estudado o Capítulo 7, você pode explorar uma variedade de maneiras de manipular gráficos, e ver como as informações sobre as relações podem ser extraídos a partir deles.
Relações representando Usando Matrizes Zero-One
Vamos agora considerar a representação das relações de matrizes zero-um. Para começar, uma vez que estará trabalhando com matrizes, é preciso indicar que estaremos usando as funções do pacote Maple linalg. Especificamente, teremos de usar a função de matrix (matriz), e as operações da matriz relacionados, do pacote linalg.
with(linalg):
Agora, nós fornecemos um procedimento Maple, que encontra a representação de matriz zero-um de uma relação, dados os pares ordenados nesta relação. O pseudocódigo para este algoritmo é como se segue;
\item{Entrada: o conjunto R e domínio D.}
\item{Para cada par (i,j) em D, que determinar se a (i,j) está em R.}
\item{Se o par está em R, colocamos uma entrada 1 na posição que representa (i,j) na matriz M. Caso contrário, coloca-se um 0 na posição que representa (i,j) na matriz M.}
\item{Saída: M.}
Traduzindo esse algoritmo para o Maple, o código resulta no seguinte procedimento.
MakeMatrix := proc (R::set, D::set)
local i, j, L;
L := [];
for i from 1 to nops(D) do
for j from 1 to nops(D) do
if member([i,j],R) then
L := [op(L), 1] else L := [op(L),0];
fi;
od;
od;
evalm(matrix(nops(D), nops(D), L));
end:
Em seguida, vamos converter as relações definidas no início deste capítulo de sua forma conjunto para representação de forma zero-um.
m1:=MakeMatrix(R1,1,2,3,4); m2:=MakeMatrix(R2,1,2,3,4); m3:=MakeMatrix(R3, 1,2,3,4); m4:=MakeMatrix(R4,1,2,3,4);
Agora que temos as representações de zero-um da matriz dessas relações, podemos usar essas matrizes para determinar se as relações são reflexivas, simétricas e/ou antissimétricas. Nesta forma, é um pouco mais fácil para determinar se uma a relação tem alguma destas propriedades. Aqui, por exemplo, é um procedimento em Maple que determina se uma relação é reflexiva, utilizando a sua representação matricial de zero-um.
IsReflexive_M:= proc(M::matrix)
local i, is_reflex;
is_reflex := true;
for i from 1 to coldim(M) do
if M[i,i] = 0 then
is_reflex := false;
fi;
od;
is_reflex;
end:
IsReflexive_M(m1);
IsReflexive_M(m3);
Aqui também estão as versões de matriz para IsSymmetric e IsAntiSymmetric.
IsSymmetric_M := proc(M::matrix)
local i,j; # row and column indices
if rowdim(M) <> coldim(M) then
RETURN(false);
fi;
for i from 1 to rowdim(M) do
for j from 1 to i-1 do
if M[i,j] <> M[j,i] then
RETURN(false);
fi;
od;
od;
RETURN(true);
end:
Deve ser quadrada. O código para verificar antissimetria é semelhante.
IsAntiSymmetric_M := proc(M::matrix)
local i,j;
if rowdim(M) <> coldim(M) then
RETURN(false);
fi;
for i from 1 to rowdim(M) do
for j from 1 to i - 1 do
if M[i,j] = 1 and M[i,j] = M[j,i] then
RETURN(false);
fi;
od;
od;
RETURN(true);
end:
Mais uma vez, podemos determinar se as relações representadas em forma de matriz zero-um são simétricas ou antissimétricas.
IsSymmetric_M(m1); IsAntiSymmetric_M(m1); IsSymmetric_M(m2); IsAntiSymmetric_M(m2); IsSymmetric_M(m4); IsAntiSymmetric_M(m4);
Fecho Computacional de Relações
Determinar o fecho de uma relação em Maple pode ser abordado basicamente da mesma forma que abordamos o problema de determinar as propriedades das relações. Especificamente, deve implementar algoritmos que utilizam técnicas semelhantes para determinação das propriedades reflexivas e simétricas, a fim de determinar o fecho dessas propriedades relacionais. O fecho transitivo da relação vai exigir mais conhecimento, mas vamos analisar vários métodos para determinar o fecho transitivo de uma determinada relação.
Fecho reflexivo
O algoritmo para calcular o fecho reflexivo de uma relação é realmente muito simples. Nós simplesmente definimos cada entrada diagonal em sua representação matricial igual a 1. A matriz resultante representa o fecho reflexivo da relação.
RefClose := proc(M::matrix)
local i;
for i from 1 to coldim(M) do
M[i,i] := 1;
od;
evalm(M);
end:
Agora usamos RefClose para encontrar o fecho reflexivo de algumas das relações que introduzimos como exemplos no início do capítulo.
RefClose(m1); RefClose(m4);
Fecho simétrico
Em seguida, vamos construir um processo de determinação do fecho simétrico de uma relação R. Novamente, usamos a observação, a partir da página 3822, que observa que, se (a,b) é um elemento de R, então (b,a) é um elemento do fecho simétrico de R. O código em Maple, o qual é semelhante ao fecho reflexivo implementado acima, é:
SymmClose := proc(M::matrix)
local i, j;
for i from 1 to coldim(M) do
for j from 1 to rowdim(M) do
if M[i,j] = 1 then
M[j,i] := 1;
fi;
od;
od;
evalm(M);
end:
Este procedimento pode ser usado para localizar o fecho simétrico da alguns dos nossos exemplos anteriores, como se segue.
SymmClose(m1); SymmClose(m4);
