Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#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
Pages : 1