2.2.relations binaires



Plan du chapitre:

Rappels et conventions
 

    1. Relation binaire sur un ensemble
    2. Produit de relations binaires
    3. Représentation matricielle d’une relation binaire
    4. Relation binaire transposée
    5. Matrice du produit de deux relations
    6. Fermeture transitive d’une relation binaire
    7. Fermeture réflexo-transitive d’une relation binaire
    8. Algorithmes de calcul de matrices
    9. Exemple de calcul sur une généalogie




Un peu de mathématiques utiles, mais pas trop !

Rappels et conventions

       
    Cas où E est un ensemble fini, c’est d’ailleurs le seul cas qui nous intéresse en informatique où nous ne pouvons pas traiter du non fini.
     


    Nous dirons que M est la matrice de représentation de la relation binaire r et nous la noterons Mr, ssi par définition :

       
       si ai r aj alors mi,j ¬ 1 sinon mi,j ¬ 0 fsi


    Exemple :

    E = { 7,8,3 } ;      r = { (7,8),(7,3),(3,8),(8,7) }

    a1 = 7 ; a2 = 8  ; a3 = 3

    Voici la matrice Mr de la relation r définie ci-haut :
     

    Mr
     
     

    4. Relation binaire transposée
     

    Nous notons rt la relation binaire telle que :
     
    " a , a Î E
    " b , b Î E
      a rt b ssi  b r  a

    Par construction la matrice de rt est la transposée de la matrice de r.
     
     M rt t Mr

     

    5. Matrice du produit de deux relations

    En munissant l’ensemble {0,1} d’une structure d’algèbre de boole avec les opérateurs Ù , Ú ,Ø , il nous est possible d’effectuer des calculs sur les matrices de représentation de relations binaires.
     


    La matrice Mp = Mr.s est très exactement par définition le produit booléen en croix des matrices Mr et Ms.
     
     Mr x Ms = Mp = Mr.s = [ (ai,k Ù bk,j)]

     
     
     

    6. Fermeture transitive d’une relation binaire
     


    Nous posons par définition sa fermeture transitive qui est la relation binaire r+ :
     

     r+  rn  , en fait dans le cas où E est fini l’union se limite à un nombre fini k de rn distincts donc :
     
       r+  rn

     
     

    7. Fermeture réflexo-transitive d’une relation binaire
     


    On note par définition r* sa fermeture réflexo-transitive :
     
        r* = r+  È  r0

    Remarque
      Soit un couple (a,b) de E x E tel que a  r* b :
      a  r*Û  $ n , n Î E  /  a rn

    Nous dirons dans ce cas qu’il existe " un chemin de longueur n, allant de a vers b ". En effet d’après la définition du produit :
     
             a r* b   Û

       tels que : ( a r c1 ) et  (c1 r c2 ) ...et (cnr b )


     

    8. Algorithmes de calcul de matrices

    FermetureTrans.dif \Ftrans.exe
     

    Calcul de la matrice produit à partir de la formule :
     
     
       Mr x Ms = Mp = Mr.s = [(ai,k Ù bk,j)]

    Notons ((mi,j)) l’élément générique de la matrice produit.

    Corps d’un algorithme de calcul :
    pour i ¬ 1 jusquà n faire
     pour j ¬ 1 jusquà n faire
      S ¬ 0 ;
      pour k ¬ 1 jusquà n faire
       S ¬ S Ú (ai,k Ù bk,j)
      Fpour ;
      mi,j ¬ S
     Fpour
    Fpour

     

    Algorithme de Warshall pour la fermeture transitive :

    Avec les mêmes notations soit((ai,j)) l’élément générique de la matrice Mr, l’algorithme de Warshall calcule Mr+ :
     
    pour k ¬ 1 jusquà n faire
     pour i ¬ 1 jusquà n faire
      pour j ¬ 1 jusquà n faire
       ai,j¬ ai,jÚ (ai,k Ù ak,j)
      Fpour ;
     Fpour
    Fpour

     

    9. Exemple de calcul sur une généalogie

    E = l’ensemble des individus d’une même famille depuis plusieurs générations.

 
Soient r, s et t les relations binaires :
   


On peut définir les liens familiaux à l’aide des opérations sur les relations binaires.

r2 = est grand père paternel de
s2 = est grand mère maternelle de
r.s = est grand père maternel de
s.r = est grand mère paternelle de(non commutativité évidente !)
r È s = est parent de
rn = est arrière arrière...arrière grand père paternel de
(r È s)+ = est un ancêtre de (on voit ici la signification pratique de la fermeture transitive qui relie deux individus par un chemin d’ascendants dans son arbre généalogique)
u.ut = est frère ou sœur de etc ....