end:
</pre>
Em seguida, é conveniente introduzir um procedimento chamado '''mub''' que calcula o conjunto de limites mínimos da cota superior de um subconjunto de um conjunto parcialmente ordenado.
<pre>
mub := proc(R::po, S::set)
MinimalElements(R, UpperBounds(R, S));
end:
</pre>
Agora, para completar a tarefa em mãos, precisamos apenas verificar se mub retorna uma única coisa. Se assim for, então o supremo (por definição); caso contrário, não faz, e nós devolver o valor NULL.
<pre>
lub := proc(R::po, S::set)
local M; # set of minimal upper bounds of S
M := mub(R, S);
if nops(M) <> 1 then
RETURN(NULL);
fi;
RETURN(op(M));
end:
</pre>
A ordenação topológica é usada para produzir, a partir de uma dada ordem parcial, uma ordem linear no seu domínio que é compatível com o mesmo. Por exemplo, a ordem natural no conjunto {1,2,3,6} é uma ordem linear que é compatível com a ordem parcial de divisibilidade. (de fato, isso é verdade para a rede de divisores de qualquer inteiro positivo uma vez que, se ''m'' e ''n'' são inteiros positivos, em seguida, ''m'' divide ''n'' somente se ''m'' é menor ou igual ''n''). Tendo implementado supremo e elementos mínimos, podemos agora criar um procedimento ordenação topológica que usa o algoritmo ''MinimalElements'' acima.
<pre>
TopSort := proc(R::po, T::set)
local i, k, S, A;
k := 1;
S := T;
A := [];
while S <> {} do
A := [op(A), MinimalElements(R, S)[1] ];
S := S minus A[k];
k := k+1;
od;
A;
end:
R := DivisorLattice(12);
TopSort(R, DomainRelation(R));
R := DivisorLattice(2*3*5);
TopSort(DualRelation(R), DomainRelation(R));
R := DivisorLattice(2*3*5*7);
TopSort(R, numtheory[divisors](2*3*7));
</pre>
== Grades ==
Nesta seção, vamos olhar para o problema de determinar se uma ordem parcial é reticulada. A abordagem que devemos tomar é um bom exemplo de ''top down programming'' (programação de cima para baixo).
Para que possamos construir alguma exemplo interessante, vamos introduzir uma nova função para produzir exemplos de uma boa classe de reticulados.
<pre>
DivisorLattice := proc(n::posint)
DividesRelation(numtheory[divisors](n));
end:
</pre>
O procedimento '''divisors''', do pacote '''numtheory''', retorna o conjunto de divisores positivos de seu argumento inteiro. Usamos o procedimento '''DividesRelation''', construído no início deste capítulo, para criar a relação de divisão neste conjunto.
<pre>
type(DivRel(6), po);
</pre>
Queremos escrever um programa em ''Maple'' que irá determinar se uma ordem parcial (finita) é um reticulado. Agora, uma ordem de ''R'' parcial é um reticulado, se, e somente se, é tanto um ''meet semilattice'' quanto um ''join semilattice''. A primeira é uma ordem parcial em que cada par de elementos tem um encontro - um limite mínimo superior ou supremo; Segundo, é aquele em que a dupla condição for satisfeita: cada par de elementos tem um supremo, ou um ínfimo. Então, o nosso teste para uma ordem parcial deve ser um reticulado, apenas precisa de verificar se estas duas condições são satisfeitas.
<pre>
IsLattice := proc(R::po)
IsMeetSemiLattice(R) and IsJoinSemiLattice(R);
end:
</pre>
Em seguida, usamos o fato de que uma ordem parcial é um ''meet semilattice'', se, e somente se, a sua relação dual é um ''join semilattice''.
<pre>
IsJoinSemiLattice := IsMeetSemiLattice @ DualRelation;
</pre>
Agora o verdadeiro trabalho começa; devemos codificar a função '''IsMeetSemiLattice'''. Para isso, é preciso testar se, dada a relação ''R'', cada par ''a'', ''b'' no domínio da ''R'' tem um supremo com relação a ''R''. Uma observação que simplifica a nossa tarefa consideravelmente é que, uma vez que estamos a lidar apenas com relações finitas, basta verificar que cada par tem um limite superior comum.
<pre>
IsMeetSemiLattice := proc(R::po)
local DomR, # the domain of R
r,s; # indices into R
DomR := DomainRelation(R);
for r in DomR do
for s in DomR do
if lub(R, r, s) = NULL then
RETURN(false);
fi;
od;
od;
RETURN(true);
end:
</pre>
Finalmente, todas as sub-rotinas que estão fazendo o nosso programa '''IsLattice''' estão completas, e podemos testá-lo em alguns exemplos. O seguinte resultado não deve vir com qualquer surpresa.
<pre>
IsLattice(DivisorLattice(24));
</pre>
Mas, observe o que acontece quando nós construímos a relação ''divides'' em todos os inteiros no conjunto {1,2,3, ..., 24}.
<pre>
IsLattice(DividesRelation(seq(i, i=1..24)));
</pre>
== Relações de abrangência ==
É muito ineficiente, em geral, armazenar todos os pares em uma relação de ordem parcial. Há uma representação mínima de uma ordem parcial, a partir do qual toda a relação pode ser reconstruída, denominado sua relação de abrangência. (Isto não é abordado no texto, mas será útil para nós na seção seguinte, além de ser um tema importante por si só). A relação de abrangência de uma ordem parcial não é em si uma ordem parcial. É um subconjunto mínimo da ordem parcial a partir do qual todos os outros pares de relação podem ser deduzidos. Seja ''R'' uma ordem parcial em um conjunto ''S''. Dizemos que um elemento ''b'' em ''S'' abrange um elemento ''a'' em ''S'' se (''a'', ''b'') pertence a ''R'', e ''a''≠''b'', mas não há elemento ''s'' em ''S'' para o qual ambos (''a'', ''s'') e (''s'', ''b'') pertencem a ''R''. Em outras palavras, ''b'' abrange ''a'' se ''b'' é maior do que ''a'', e se não há nada entre eles. A relação de abrangência de uma ordem ''R'' parcial é a relação ''C'' de ''S'' que consiste naqueles pares (''a'', ''b'') em ''R'' para o qual ''b'' abrange ''a''. Como um exemplo simples, considere o conjunto {1,2,3,4} ordenado pela magnitude. Sua relação de abrangência é o conjunto {(1,2), (2,3), (3,4)}. Todos os outros pares, tais como (1,3), pode ser deduzida a partir da relação de abrangência, usando transitividade: 1 ≤ 2 ≤ 3, e, portanto, uma 1 ≤ 3 (isto é, o par (1,3) está na relação). Relações de abrangência também são importantes porque é a relação de abrangência de uma ordem parcial que é desenhada num diagrama de Hasse, em vez de toda a relação.
Nesta seção, nós fornecemos um procedimento em Maple para calcular a relação cobrindo de uma ordem parcial. Em primeiro lugar, precisamos de um teste para saber se um determinado elemento cobre outro.
<pre>
Covers := proc(R::po, a, b)
local u; # index into Dom(R)
if a = b then
RETURN(false);
fi;
if not member([a,b], R) then
RETURN(false);
fi;
for u in DomainRelation(R) minus a, b do
if member([a,u], R) and member([u,b], R) then
RETURN(false);
fi;
od;
RETURN(true);
end:
</pre>
Agora podemos construir a relação cobrindo de uma ordem parcial usando o seguinte procedimento em Maple:
<pre>
CoveringRelation := proc(R::po)
local C, # covering relation; returned
DomR, # the domain of R
r,s; # indices into DomR
DomR := DomainRelation(R);
C := {};
for r in DomR do
for s in DomR do
if Covers(R, r, s) then
C := C union [r,s];
fi;
od;
od;
RETURN(C);
end:
</pre>
Vejamos alguns pequenos exemplos.
<pre>
CoveringRelation(DivisorLattice(6));
CoveringRelation(DividesRelation(1,3,5,7,11,13,17));
</pre>
== Diagramas de Hasse ==
A relação de abrangência de uma ordem parcial é muitas vezes usada para representar uma ordem parcial. Nós já mencionamos que é mais eficiente (o que exige menos memória), mas também é usada para representar uma ordem parcial graficamente, no sentido de que o diagrama de Hasse é apenas uma representação visual da relação de abrangência da ordem parcial. Nós já temos a maioria das ferramentas de que precisamos para fazer uma primeira tentativa de uma representação visual de uma ordem parcial. As ferramentas de visualização no pacote '''networks''' tornam relativamente fácil de desenhar uma imagem gráfica de uma ordem parcial. Nós simplesmente calculamos sua relação de abrangência, e depois a convertemos para um gráfico e a exibimos como no seguinte procedimento.
<pre>
HasseDiagramFirstTry := proc(R::po)
local C;
C := CoveringRelation(R);
networks[draw](MakeDigraph(DomainRelation(C),C));
end:
</pre>
Por exemplo, aqui está uma imagem do divisor reticulado de 2100.
<pre>
HasseDiagramFirstTry(DivisorLattice(2*3*5*7));
</pre>
Infelizmente, esta sofre da desvantagem de não desenhar diagramas Hasse na forma tradicional, com o fim de os elementos representados pelo fluxo do diagrama. Para corrigir isso, precisamos fazer um pouco de codificação. A ideia é organizar os elementos de um ordenado parcialmente definida em níveis, e então usar a opção '''Linear''' para rotina '''draw''' para formar o diagrama mais apropriadamente. Várias rotinas de serviços públicos são necessárias. Esta função é usada para verificar se um elemento é um átomo; isto é, que não tem precedentes. Destina-se a ser utilizado apenas com relações de abrangência '''CR'''. O argumento extra '''D''' é necessário para que possamos localizá-lo mais tarde.
<pre>
IsAtom := proc(CR::rel, D::set, a::anything)
local d;
for d in D do
if member([d,a], CR) then
</pre>
encontrou um predecessor:
<pre>
RETURN(false);
fi;
od;
</pre>
deve ser um átomo:
<pre>
RETURN(true);
end:
</pre>
Nós usamos isso no próximo procedimento, que determina todos os átomos em um determinado subconjunto de uma relação de cobertura.
<pre>
Atoms := proc(CR::rel, D::set)
local A, # set of atoms; returned
d; # index into D
A := {};
for d in D do
if IsAtom(CR, D, d) then
A := A union d;
fi;
od;
RETURN([op(A)]);
end:
</pre>
Aqui é a nossa nova implementação do Diagrama de Hasse. A maior parte do novo trabalho envolve a disposição dos elementos do conjunto parcialmente ordenado em uma sequência de níveis para passar para '''Linear''' na rotina '''draw'''.
<pre>
HasseDiagram := proc(R::po)
local L, C, G, A, D;
C := CoveringRelation(R);
D := DomainRelation(C); # = DomainRelation(R)
G := MakeDigraph(D, R);
L := NULL;
while D <> {} do
A := Atoms(C, D);
L := L, sort(A);
D := D minus op(A);
od;
networks[draw](Linear(L), G);
end:
</pre>
Ela produz imagens muito melhores, com o fluxo, da esquerda para a direita, seguindo aproximadamente os elementos crescentes do conjunto parcialmente ordenado.
<pre>
HasseDiagram(DivisorLattice(4));
HasseDiagram(DivisorLattice(6));
HasseDiagram(DivisorLattice(81));
</pre>
Os dois seguintes são especialmente bonitos!
<pre>
HasseDiagram(DivisorLattice(2*3*5*7));
HasseDiagram(DivisorLattice(2*3*5*2));
</pre>
== Cálculos e explorações ==
Nesta seção, vamos explorar como o ''Maple'' pode ser usado para resolver as questões 1, 4 e 5 da secção cálculos e explorações.
1- Exibir todas as diferentes relações em um conjunto com 4 elementos.
'''Solução:'''
Como de costume, Maple é demasiado poderoso para resolver somente uma única instância do problema geral sugerido por esta questão. Nós fornecemos aqui um procedimento muito simples que irá calcular todas as relações em qualquer conjunto finito.
<pre>
AllRelations := proc(S::set)
local s, t, # indices into S
C; # Cartesian product SxS
C := {};
for s in S do
for t in S do
C := C union [s,t];
od;
od;
combinat[powerset](C);
end:
</pre>
Nós agora testar o nosso procedimento em um conjunto menor, de modo a manter a saída de um comprimento razoável. O leitor é convidado para determinar o tempo de execução e o comprimento de saída para o processo, quando o conjunto de entrada tem cardinalidade 4 ou 5. Tenha em mente que existem <math>2^{n^{2}}</math> relações em um conjunto com n membros.
<pre>
AllRelations(1,2);
</pre>
2- Determine quantas relações transitivo existem em um conjunto com ''n'' elementos para todos os inteiros positivos ''n'' com ''n'' ≤ 7.
'''Solução:'''
Vamos construir cada possíveis <math>N x N</math> da matriz zero-um, usando um algoritmo semelhante ao de contagem binária. O pseudocódigo é:
1- Para cada valor de 1 até <math>2^{(n ^{2})}</math>, criamos uma lista que é a representação de base 2 desse inteiro.
2- Nós criamos uma matriz M com elementos sendo a lista de valores. Estes são todos os possíveis <math>n^{2}</math> de matriz zero-um (o leitor pode provar esta afirmação).
3- Avaliar o fechamento transitivo de cada uma das matrizes que criamos, e retornar o conjunto de fechos transitivos dessas matrizes.
A implementação é como se segue:
<pre>
FindTransitive := proc(S::set)
local i, j, T, P;
P := {};
for i from 0 to 2^(nops(S)^2)-1 do
T := convert(i, base, 2);
while nops(T) < nops(S)^2 do
T := [op(T), 0];
od;
P := P union matrix(nops(S), nops(S), T);
od;
P;
end:
</pre>
Mais uma vez, utilizamos o nosso processo em valores relativamente pequenos (devido ao comprimento da saída), e deixamos a exploração adicional para o leitor.
<pre>
P := FindTransitive(1,2):
Q := {}:
for i from 1 to nops(P) do
Q := Q union Warshall(P[i]):
od:
Q;
</pre>
3- Encontre o fecho transitivo de uma relação em um conjunto com pelo menos 200 elementos.
'''Solução:'''
Vamos gerar aleatoriamente uma matriz zero-um com dimensão 10x10, e em seguida, aplicar o algoritmo de \textbf{Warshall} para deduzir o fecho transitivo matriz.
Para gerar uma matriz zero-um aleatória, usamos a função '''randmatrix''' do pacote '''linalg''', e fornecer seu terceiro argumento, opcional com um procedimento que gera uma sequência aleatória 0's (zero) e 1's (uns). Em seguida, aplicamos o algoritmo de '''Warshall''' a esta matriz aleatória, obtendo o resultado. Aqui, para economizar espaço, podemos aplicar este procedimento para uma matriz de 10x10 como um exemplo.
<pre>
Q := randmatrix(10, 10, entries=rand(2));
Warshall(Q);
</pre>
== Referências ==
[http://www.mhhe.com/math/advmath/rosen/r5/student/ch07/maple.html Maple: Chapter 7. Relations]