Mathématiques discrètes - Relations
Chaque fois que des ensembles sont discutés, la relation entre les éléments des ensembles est la prochaine chose qui se présente. Relations peuvent exister entre des objets du même ensemble ou entre des objets de deux ensembles ou plus.
Définition et propriétés
Une relation binaire R de l'ensemble x à y (écrite comme $ xRy $ ou $ R (x, y) $) est un sous-ensemble du produit cartésien $ x \ times y $. Si la paire ordonnée de G est inversée, la relation change également.
En général, une relation n-aire R entre les ensembles $ A_1, \ dots, \ et \ A_n $ est un sous-ensemble du produit n-aire $ A_1 \ times \ dots \ times A_n $. La cardinalité minimale d'une relation R est zéro et maximum est $ n ^ 2 $ dans ce cas.
Une relation binaire R sur un seul ensemble A est un sous-ensemble de $ A \ fois A $.
Pour deux ensembles distincts, A et B, ayant respectivement des cardinalités m et n , la cardinalité maximale d'une relation R de A à B est mn .
Domaine et plage
S'il y a deux ensembles A et B et que la relation R a une paire d'ordre (x, y), alors -
le domainde R, Dom (R), est l'ensemble $ \ lbrace x \: | \: (x, y) \ in R \: for \: some \: y \: in \: B \ rbrace $
le range de R, Ran (R), est l'ensemble $ \ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace $
Exemples
Soit, $ A = \ lbrace 1, 2, 9 \ rbrace $ et $ B = \ lbrace 1, 3, 7 \ rbrace $
Cas 1 - Si la relation R est 'égale à' alors $ R = \ lbrace (1, 1), (3, 3) \ rbrace $
Dom (R) = $ \ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace $
Cas 2 - Si la relation R est 'inférieure à' alors $ R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace $
Dom (R) = $ \ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace $
Cas 3 - Si la relation R est 'supérieure à' alors $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $
Dom (R) = $ \ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace $
Représentation des relations à l'aide d'un graphique
Une relation peut être représentée à l'aide d'un graphe orienté.
Le nombre de sommets du graphe est égal au nombre d'éléments de l'ensemble à partir desquels la relation a été définie. Pour chaque paire ordonnée (x, y) dans la relation R, il y aura une arête dirigée du sommet «x» au sommet «y». S'il y a une paire ordonnée (x, x), il y aura auto-boucle sur le sommet 'x'.
Supposons qu'il y ait une relation $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ sur l'ensemble $ S = \ lbrace 1, 2, 3 \ rbrace $, cela peut être représenté par le graphique suivant -
Types de relations
le Empty Relation entre les ensembles X et Y, ou sur E, est l'ensemble vide $ \ emptyset $
le Full Relation entre les ensembles X et Y est l'ensemble $ X \ fois Y $
le Identity Relationsur l'ensemble X est l'ensemble $ \ lbrace (x, x) | x \ dans X \ rbrace $
La relation inverse R 'd'une relation R est définie par - $ R' = \ lbrace (b, a) | (a, b) \ dans R \ rbrace $
Example - Si $ R = \ lbrace (1, 2), (2, 3) \ rbrace $ alors $ R '$ sera $ \ lbrace (2, 1), (3, 2) \ rbrace $
Une relation R sur l'ensemble A est appelée Reflexive si $ \ forall a \ in A $ est lié à a (aRa tient)
Example - La relation $ R = \ lbrace (a, a), (b, b) \ rbrace $ sur l'ensemble $ X = \ lbrace a, b \ rbrace $ est réflexive.
Une relation R sur l'ensemble A est appelée Irreflexive si aucun $ a \ dans A $ n'est lié à a (aRa ne tient pas).
Example - La relation $ R = \ lbrace (a, b), (b, a) \ rbrace $ sur l'ensemble $ X = \ lbrace a, b \ rbrace $ est irréflexive.
Une relation R sur l'ensemble A est appelée Symmetric si $ xRy $ implique $ yRx $, $ \ forall x \ in A $ et $ \ forall y \ in A $.
Example - La relation $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ sur l'ensemble $ A = \ lbrace 1, 2, 3 \ rbrace $ est symétrique.
Une relation R sur l'ensemble A est appelée Anti-Symmetric si $ xRy $ et $ yRx $ implique $ x = y \: \ forall x \ in A $ et $ \ forall y \ in A $.
Example - La relation $ R = \ lbrace (x, y) \ à N | \: x \ leq y \ rbrace $ est antisymétrique puisque $ x \ leq y $ et $ y \ leq x $ implique $ x = y $ .
Une relation R sur l'ensemble A est appelée Transitive si $ xRy $ et $ yRz $ implique $ xRz, \ forall x, y, z \ dans A $.
Example - La relation $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ sur l'ensemble $ A = \ lbrace 1, 2, 3 \ rbrace $ est transitive.
Une relation est un Equivalence Relation s'il est réflexif, symétrique et transitif.
Example - La relation $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \ rbrace $ sur l'ensemble $ A = \ lbrace 1, 2, 3 \ rbrace $ est une relation d'équivalence car elle est réflexive, symétrique et transitive.