Relation de preordre


  • D

    Bonsoir,
    Je continue mes révisions intensives. Cette fois-ci je bloque sur cet exercice:

    Sur un ensemble X à 6 éléments, on considère une relation binaire de matrice

    M(R)= 0 0 0 0 0 0
    1 0 0 0 0 0
    1 0 0 0 0 1
    1 0 0 0 1 0
    0 0 1 0 0 0
    0 0 0 0 0 0

    a) calculer la matrice de la relation de préordre engendrée par R.

    b) Dessiner le graphe de la relation R et retrouver le résultat de la question précédente.

    Je pense que je suis en mesure de faire seul la question B mais je ne comprends pas la 1er est-il possible que vous me l'expliquer?

    Merci
    Bonne soirée


  • mtschoon

    Bonjour,

    Tu as déjà fait ce genre d'exercice, mais sans l'écriture matricielle.
    Je te mets le lien pour que tu puisses le revoir:
    https://forum.mathforu.com/topic/30043/relation-de-préordre

    J'essaie de t'expliquer cette écriture matricielle (qui n'est pas compliquée, une fois qu'on la connait)

    J'ai complété la matrice avec les valeurs de X verticalement à gauche, qui correspondent au premier élément utilisé pour la relation R ainsi que les valeurs de X horizontalement en haut qui correspondent au second élément utilisé pour la relation R

    Dans la matrice, 1 veut dire que la relation est réalisée, 0 veut dire qu'elle ne l'est pas

    R 1 2 3 4 5 6
    1 0 0 0 0 0 0
    2 1 0 0 0 0 0
    3 1 0 0 0 0 1
    4 1 0 0 0 1 0
    5 0 0 1 0 0 0
    6 0 0 0 0 0 0

    Exemples pour comprendre
    1R1, 1R2,1R3,1R4,1R5,1R6 sont faux (valeurs 0)
    2R1 est vrai (valeur 1), 2R2,2R3,2R4,2R5, 2R6 sont faux (valeur 0)
    etc, etc...

    En bref, ce qui est vrai est :
    2R1, 3R1,3R6, 4R1, 4R5, 5R3,


  • mtschoon

    Tu dois compléter cette relation R pour qu'elle devienne une relation de préordre, c'est à dire réflexive et transitive.

    Pour qu'elle soit réflexive, 1R1, 2R2, 3R3, 4R4, 5R5, 6R6 doivent être vraies donc il faudra mettre 1 dans les cases correspondantes (1,1),(2,2),(3,3),(4,4),(5,5),(6,6) (c'est à dire première diagonale de la matrice)

    Pour qu'elle soit transitive il faut que
    4R3 soit vraie car 4R5 et 5R3 => 4R3, donc mettre 1 dans la case (4,3)
    5R1 soit vraie car 5R3 et 3R1 => 5R1, donc mettre 1 dans la case (5,1)
    (Vérifie qu'il n'y en as pas d'autre à ajouter)

    La matrice de préordre engendrée par R est donc :
    R 1 2 3 4 5 6
    1 1 0 0 0 0 0
    2 1 1 0 0 0 0
    3 1 0 1 0 0 1
    4 1 0 1 1 0 0
    5 1 0 1 0 1 0
    6 0 0 0 0 0 1

    Remarque : les valeurs de X écrites en gras ne font pas partie de la matrice.
    Je les ai écrites pour la compréhension, tu dois les penser (ou les écrire au brouillon) mais tu ne dois pas les écrire dans la conclusion.

    Tu dois écrire seulement
    1 0 0 0 0 0
    1 1 0 0 0 0
    1 0 1 0 0 1
    1 0 1 1 0 0
    1 0 1 0 1 0
    0 0 0 0 0 1

    Bon travail !


  • D

    Bonsoir,
    J'ai du mal avec la transitivité. J'ai fait un schéma car je n'arrive pas à voir la transitivité sur la matrice.
    Pourquoi 4 R 3 et non 3 R 4? Vu qu'il flèche par de 5 et pointe sur 3 et qu'une autre part de 4 et pointe sur 5 je n'arrive pas à comprendre dans quel sens doit aller la flèche.


  • mtschoon

    Rappel de la définition de la transitivité :

    aRb et bRc => aRc

    4R5 et 5R3 => 4R3

    Dans la matrice, il y a 1 dans les cases (4,5) , (5,3) donc (4.3)
    (si tu as fait la matrice correctement, bien sûr)

    Schéma :
    Flèche de 4 vers 5 et Flèche de 5 vers 3 donc Flèche de 4 vers 3 (à tracer.)


  • D

    Merci beaucoup


  • mtschoon

    De rien et j'espère que tu as compris .


Se connecter pour répondre