109
edits
Changes
Jump to navigation
Jump to search
no edit summary
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 ==
