SHARE
TWEET

Untitled

a guest Jun 19th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // diferenca simetrica
  2. function DS=diffsim(A,B)
  3.     // union une todos os elementos de cada conjunto
  4.     // intersect intersecta todos os elementos comuns a ambos
  5.     // setdiff exclui os elemetos de B a A
  6.     // uniao excluindo a itersecao, igual a diferennca simetrica
  7.     // unique remove todos os elementos duplicados do vetor
  8.     DS=unique(setdiff(union(A,B),intersect(A,B)))
  9. endfunction
  10.  
  11. // relacao composta
  12. function M=relcomp(MR,MS)
  13.     // bool2s serve para passar os valores diferentes de 0 para 1 havendo apenas
  14.     // valores booleanos
  15.     M=bool2s(MR*MS)
  16. endfunction
  17.  
  18.  
  19. // verificar simetria
  20. function s=is_simetrica(M)
  21.     // se a matriz relacao for igual a sua transposta entao e simetrica
  22.     // outra abordagem seria verificar se a,b e b,a estao na relacao. se apenas
  23.     // um deles estiver, entao nao e simetrica.
  24.     if isequal(M,M')
  25.         s=%t
  26.     else
  27.         s=%f
  28.     end
  29. endfunction
  30.  
  31.  
  32. // fecho simetrico
  33. function ret=fecho_simetrico(M)
  34.     [u v]=size(M)
  35.     for i=1:u
  36.         for j=1:v
  37.             // se existir um a,b tem de existir um b,a
  38.             if M(i,j)<>M(j,i)
  39.                 // garantir a existencia de ambos: a,b e b,a
  40.                 M(i,j)=1
  41.                 M(j,i)=1
  42.             end
  43.         end
  44.     end
  45.     ret=M
  46. endfunction
  47.  
  48.  
  49. // verificar a transitividade
  50. function t=is_transitiva(M)
  51.     // se M for igual a M+M^2 significa que qualquer M^3.. M^n com n a ordem da
  52.     // matriz dada, nunca ira mudar entao ela e transitiva. se ao inicio falhar,
  53.     // existe pelo menos um elemento que falha para que ela seja transitiva
  54.     if isequal(M,bool2s(M+M^2))
  55.         t=%t
  56.     else
  57.         t=%f
  58.     end
  59. endfunction
  60.  
  61.  
  62. // fecho transitivo
  63. function t=fecho_transitivo(M)
  64.     [u v]=size(M)
  65.     t=M
  66.     for i=2:u
  67.         // adiciona todas as possibilidades de transitividade apartir da matriz
  68.         // relacao original
  69.         t=t+M^i
  70.     end
  71.     // coloca os valores diferetes de 0 a 1
  72.     t=bool2s(t)
  73. endfunction
  74.  
  75.  
  76. // verificar a reflexividade
  77. function r=is_reflexiva(M)
  78.     [a b]=size(M)
  79.     for i=1:a
  80.         // verifica se a diagonal principal esta a 1. se tiver algum elemento a
  81.         // zero, significa que nao e reflexiva
  82.         if M(i,i)==0 then
  83.             r=%f
  84.             return
  85.         end
  86.     end
  87.     r=%t
  88. endfunction
  89.  
  90.  
  91. // fecho reflexivo
  92. function ret=fecho_reflexivo(M)
  93.     [u v]=size(A)
  94.     // coloca a diagonal principal a 1
  95.     ret=bool2s(M+eye(u,v))
  96. endfunction
  97.  
  98.  
  99. // verifica se e uma relacao antissimetrica
  100. function as=is_antissimetrica(M)
  101.     [a b]=size(M)
  102.     for i=1:a
  103.         for j=1:b
  104.             if i<>j & M(i,j)==1 & M(j,i)==1 then
  105.                 as=%f
  106.                 return
  107.             end
  108.         end
  109.     end
  110.     as=%t
  111. endfunction
  112.  
  113.  
  114. // verifica se e uma relacao de equivalencia
  115. function ret=is_equival(M)
  116.     // para ser uma relacao de equivalencia, tem de ser reflexiva, simetrica e
  117.     // transitiva
  118.     ret = is_reflexiva(M) & is_simetrica(M) & is_transitiva(M)
  119. endfunction
  120.  
  121.  
  122. function e=equival(M)
  123.     [a b]=size(M)
  124.     if is_equival(M) then
  125.         //"A rela??o dada ? uma rela??o de equival?ncia
  126.         e=M;
  127.         return
  128.     else
  129.         //A rela??o dada n?o ? uma rela??o de equival?ncia. A menor rela??o de
  130.         // equival?ncia que cont?m a rela??o R tem a seguinte matriz de rela??o:
  131.         A=bool2s(eye(a,b)+M+M')
  132.         e=zeros(a,b)
  133.         for i=1:a
  134.             e=e+A^i
  135.         end
  136.         e=bool2s(e)
  137.     end
  138. endfunction
  139.  
  140.  
  141. // verifica se e relacao de ordem parcial
  142. function ret=is_ordem_parcial(M)
  143.     // para ser relacao de ordem parcial a relacao tem de ser reflexiva,
  144.     // antissimetrica e transitiva
  145.     ret = is_reflexiva(M) & is_antissimetrica(M) & is_transitiva(M)
  146. endfunction
  147.  
  148.  
  149. // devolve a matriz de caminhos apartir da matriz de adjacencias do grafo
  150. // util para saber se existe caminho e quantos caminhos existem
  151. function MC=matriz_gcaminhos(A)
  152.     [u,v]=size(A)
  153.     MC=A
  154.     for i=2:u
  155.         MC=MC+A^i
  156.     end
  157. endfunction
  158.  
  159.  
  160. // verifica se o grafo e fortemente conexo
  161. function FC=forteconexo(A)
  162.     [u,v]=size(A)
  163.     S=matriz_gcaminhos(A)
  164.     for i=1:u
  165.         for j=1:v
  166.             // para verificar se e fortemente conexo, tem que existir caminho
  167.             // para todos os vertices
  168.             if S(i,j)==0 then
  169.                 FC=%f
  170.                 return
  171.             end
  172.         end
  173.     end
  174.     FC=%t
  175. endfunction
  176.  
  177.  
  178. // verifica se o grafo e unilateralmente conexo
  179. function UC=unilateralconexo(A)
  180.     [u,v]=size(A)
  181.     S=matriz_gcaminhos(A)
  182.    
  183.     // para verificar o vertice i,j ou j,i
  184.     T=S+S'
  185.  
  186.     for i=1:u
  187.         for j=1:v
  188.             // se nenhum deles for alcancavel nao e unilateralmente conexo
  189.             if i<>j & T(i,j)==0 then
  190.                 UC=%f
  191.                 return
  192.             end
  193.         end
  194.     end
  195.     UC=%t
  196. endfunction
  197.  
  198.  
  199. // verifica se o grafo e fracamente conexo
  200. function frC=fracaconexo(A)
  201.     [u,v]=size(A)
  202.  
  203.     V=matriz_gcaminhos(A+A')
  204.    
  205.     for i=1:u
  206.         for j=1:v
  207.             if V(i,j)==0 then
  208.                 frC=%f
  209.                 return
  210.             end
  211.         end
  212.     end
  213.    
  214.     frC=%t
  215. endfunction
  216.  
  217.  
  218. // verifica se o grafo e conexo ou disconexo
  219. function ret=conetividade(A)
  220.     if forteconexo(A) | unilateralconexo(A) | fracaconexo(A) then
  221.         ret=%t
  222.     else
  223.         ret=%f
  224.     end
  225. endfunction
  226.  
  227.  
  228. // retorna os graus de saida de um vertice num grafo
  229. function ret=graus_out(A,v)
  230.     [a,b]=size(A)
  231.    
  232.     ret=0
  233.     for i=1:a
  234.         ret=ret+A(v,i)
  235.     end
  236. endfunction
  237.  
  238.  
  239. // retorna os graus de entrada de um vertice num grafo
  240. function ret=graus_in(A,v)
  241.     [a,b]=size(A)
  242.    
  243.     ret=0
  244.     for i=1:a
  245.         ret=ret+A(i,v)
  246.     end
  247. endfunction
  248.  
  249.  
  250. // devolve o numero de pocos do grafo
  251. function v=pocos_grafo(A)
  252.     [a,b]=size(A)
  253.     v=0;
  254.     for i=1:a
  255.         if graus_out(A,i) == 0
  256.             v=v+1
  257.         end
  258.     end
  259. endfunction
  260.  
  261.  
  262. // devolve o numero de fontes do grafo
  263. function v=fontes_grafo(A)
  264.     [a,b]=size(A)
  265.     v=0;
  266.     for i=1:a
  267.         if graus_in(A,i) == 0
  268.             v=v+1
  269.         end
  270.     end
  271. endfunction
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top