Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 15-04-2021 21:13:55

moussa1997
Membre
Inscription : 15-04-2021
Messages : 5

Relation binaire

Bonjour,

J'aimerais de l'aide a propos de cet exercice :

Trouver toutes les relations d'ordre sur l'ensemble $E=\{a,b,c\}$.

En fait j'ai donné 12 graphes dont les propriétés de l'ordre sont vérifiées et chaque graphe contient au moins le diagonale  de $E \times E.$

Dernière modification par yoshi (16-04-2021 07:23:40)

Hors ligne

#2 16-04-2021 07:17:52

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

Bonjour,

J'en trouve 13, il y a 6 ordres totaux, 6 ordres où un seul des 3 éléments est isolé, et 1 où tous les éléments sont isolés ( c'est l'égalité ).

Alain


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#3 16-04-2021 12:33:50

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

Bonjour,

En fait j'en ai sauté 6 autres, j'ai regardé la question trop rapidement, à savoir les cas où les relations partant ou arrivant d'un point ( ou sur ...) ne sont pas dans le même sens,
donc en tout ça en fait 19, à savoir ( sans expliciter la réfléxivité) :
La diagonale seule (1),  les relations types a->b ->c et permutations (6), les relations types b -> c et permutations (6), enfin celles du type
c -> a, c -> b ( cas d'un minimum sans maximum) (3 avec les permutations )  , et  c <- a, c <- b ( cas d'un maximum sans minimum) (3 avec les permutations ).
Cette fois ça doit être bon...

Désolé
Alain


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#4 16-04-2021 12:49:05

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

ou sous forme plus visuelle... par niveaux de stricte hauteur:

                                                                                                             c
                                                                                                             |
                                                              c        b       b   c                      b
                                                              |        / \       \ /                        |
1 niveau  style a b c ,  2 niveaux,       a  b ,   a  c   ,   a    , 3 niveaux   a   qui donne en  nombre de graphes possibles:

                         1                              6           3          3                         6               ->  total = 19

Alain

Dernière modification par bridgslam (23-04-2021 16:56:52)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#5 16-04-2021 15:26:42

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

Bonjour,


La question n'est pas facile dans le cas général ( n éléments ), à cause de la transitivité de la relation d'ordre.
Par-contre le nombre de relations anti-symétriques est plus facile à trouver en fonction de n.

Soit n le nombre d'éléments de E. On a déjà une partie à prendre sur la diagonale, donc [tex]2^n[/tex] choix de telles parties.

Ensuite il faut prendre une partie constitué d'éléments hors diagonale, avec deux choix possibles s'excluant mutuellement quand les couples sont symétriques.
Comme on a [tex]N = n(n-1)/2[/tex] couples au-dessus de la diagonale, on a encore un choix de   
[tex]\sum_{k=0}^N 2^k \binom{N}{k}[/tex]  parties possibles de couples hors diagonale ( puisque un couple exclut son symétrique ) , donc [tex]3^N[/tex] parties possibles  pour les points hors diagonale ( ce qu'on peut voir directement: un point hors diagonale est soit pas pris et son symétrique non plus, soit pris au-dessus, ou bien soit au-dessous ... donc 3 possibilités pour chaque )

Au final on a donc [tex]2^n 3^{n(n-1)/2}[/tex] relations anti-symétriques sur un ensemble à n éléments.

Une relation d'ordre étant toujours anti-symétrique, leur quantité pour n éléments est toujours majorée par celui-ci.

Pour revenir au dénombrement de relations d'ordre le mieux est peut-être de raisonner par niveaux comme dans les diagrammes de Hasse
le système étant le suivant:

- au même niveau aucun élément n'est relié à un autre.
- un élément d'un niveau donné est toujours relié à au moins 1 élément d'un niveau inférieur (si niveau inférieur il y a of course)

Cette démarche permet de dénombrer les diagrammes possibles sans en oublier. mais c'est assez pénible.

Alain

Dernière modification par bridgslam (23-04-2021 17:00:25)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#6 17-04-2021 01:32:38

moussa1997
Membre
Inscription : 15-04-2021
Messages : 5

Re : Relation binaire

Bonjour,
Ah oui j'avais pas remarqué les permutations, merci.

Hors ligne

#7 17-04-2021 13:34:02

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

Plus précisément le nombre de relations d'ordre est inférieur à[tex]3^{n(n-1)/2}[/tex] car le choix des points diagonaux est unique (tous) avec la réfléxivité... Avec n =3 on a bien 19  plus petit que 27...
Peut-être peut-on améliorer cette majoration, mais ça ne me saute pas aux yeux..

Alain


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#8 18-04-2021 02:07:33

moussa1997
Membre
Inscription : 15-04-2021
Messages : 5

Re : Relation binaire

Bonjour,
Apres j'ai exactement 19 graphes, je les ai énuméré. Mais le cas général me pose problème.
le nombre de partie de la diagonale est compris, par contre votre dénombrement sur le nombre de partie hors diagonale
m'étonne.
Pourriez-vous m'expliquer le nombre de partie hors diagonale s'il vous plait.
En premier essai je comprends que le nombre d'éléments au dessus de la diagonale est $\frac{n(n-1)}{2}$.

Moussa

Dernière modification par moussa1997 (18-04-2021 02:11:25)

Hors ligne

#9 18-04-2021 11:18:49

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

Bonjour,

Je m'intéressais juste au nombre de  relations anti-symétriques Et réflexives sur un ensemble à n éléments, pour pouvoir
ensuite dire que le nombre de relations d'ordre est justement  inférieur à ce nombre.

On décrit complètement une relation anti-symétriques ( pour les points hors-diagonales, le choix sur la diagonale est arbitraire, sauf cas de réflexivité où on aura un unique choix -> tout ) en disant que pour chaque point du produit cartésien au-dessus,
soit il est dans le graphe (mais pas son symétrique ) , soit il n'y est pas  ni son symétrique, soit il n'y est pas mais son symétrique est dedans. On a 3 choix à effectuer pour chaque point au-dessus de la diagonale, d'où la formule car l'ensemble de tous ces choix sont différents et il est en bijection avec ce qu'on cherche.
Pour chacun des points P(x,y) au-dessus de la diagonale ( pour fixer les idées, on pourrait raisonner avec dessous la diagonale ) :

Ou bien:

- non P(x,y) et non P( y, x )
- p(x, y ) et non P(y,x)
- non p(x,y) et P(y,x)

soit effectivement [tex]3^{n(n-1)/2}[/tex] configurations.

Le choix de choix points diagonaux revient à [tex]2^n[/tex], nombre de parties parmi n points, il est indépendant des autres choix.
En cas de réfléxivité imposée, on est obligé de prendre un seul choix, la diagonale pleine...


Alain


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#10 18-04-2021 21:22:26

moussa1997
Membre
Inscription : 15-04-2021
Messages : 5

Re : Relation binaire

Bonjour,

Je comprends, en fait  le nombre de  parties antisymétriques de points hors diagonale peut être déterminer de deux façons:

-En choisissant un élément  sur chaque ensemble du type $\{(a,b),(b,a),\phi \}$ alors le nombre de possibilités est $2^N$.

-En construisant une partition de l'ensemble en question, on cherche d'abord  k points au dessus de la  diagonale
ce qui fait $\binom{N}{k}$  puis les permutations de chaque point de la partie ce qui fait $2^k$ possibilités  et le tout fait $\sum_{k=0}^N 2^k \binom{N}{k}$, merci.

Moussa

Dernière modification par moussa1997 (18-04-2021 22:03:02)

Hors ligne

#11 19-04-2021 10:33:01

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 297

Re : Relation binaire

Bonjour,

[tex]3^N[/tex] pour la première affirmation, une coquille je pense ( 3 possibilités indépendantes pour chacun des N points ).

Alain


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#12 19-04-2021 17:52:36

moussa1997
Membre
Inscription : 15-04-2021
Messages : 5

Re : Relation binaire

Bonjour,
Oh oui je me précipitait et je me suis trompé lors du saisi c'est  $3^N$ (soit un élément soit son symétrie soit rien), merci.

Moussa

Dernière modification par moussa1997 (19-04-2021 17:53:10)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
trente sept plus trente sept
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums