Inscription / Connexion Nouveau Sujet
graphe et tournoi
bonjour à tous,
voilà, je cherche de l'aide pour cet exo :
" On rapelle qu'un graphe est une relation binaire sur un ensemble qui est irréflexive et symétrique.
--> Combien y a t-il de graphes sur un ensemble à n éléments ?
Un tournoi est une relation binaire p sur un ensemble E qui est irréflexive, antisymétrique et totale, c'est à dire que pour tout x,y appartenant à E, on a soit x=y, soit xpy, soit ypx exclusivement.
--> combien y a t-il de tournoi à n éléments ?
Retrouvez que ces nombres sont égaux vi une bijection bien choisie."
Alors pour le nombre de graphes, j'ai trouvé qu'il était égal au nombre de sous-ensemble de 2 éléments, soit 2^(2 parmi n)
Par contre je bloque sur les 2 autres questions.
Merci d'avance !
Trop bien car j'ai exactement le même exercice à faire pour un DM à rendre vendredi.
Tu pourais m'expliquer comment t'as pour le graphe stp!
Moi aussi je veux bien de l'aide pour les deux autres questions!
Merci d'avance
De même pour moi, cet exo fait partie d'un DM que je dois rendre pour vendredi, tu es certainement dans une section similaire à la mienne ( MASS).
Pour le nombre de graphes, j'attends confirmation.
Bonsoir laure et antoo
Je trouve la même chose que
nombre de sous-ensemble de 2 éléments, soit 2^(2 parmi n)
sauf que je pensais que c'était plutôt "nombre de sous ensembles dans l'ensemble des parties de 2 éléments"
D'autre part c'est bizarre, je trouve la même chose pour le nombre de tournoi soit 2^(2 parmi n)égal au nombre de graphes.
il faudrait que quelqu'un vérifie tout ça.
tu peux m'expliquer comment tu fais pour le nombre de tournois
ps : on doit trouver la meme chose pour le nombre de graphes que pour le nombre de tournois
Salut antoo
Eh bien j'ai tenté le raisonnement suivant somme toute assez simple:
Il est dit que
Un tournoi est une relation binaire p sur un ensemble E qui est irréflexive, antisymétrique et totale
donc il faut prendre le cas ou toutes les paires sont en relation puisque total
(paire = partie de 2 éléments)
Or tu as calculé toi même qu'il y en C(2 parmi n)
De plus il est bien spécifié que
soit xpy, soit ypx exclusivement.
ce qui veut dire que pour une paire il y a 2 tournois possibles soit de a vers b ou le contraire et comme il y a C(n;2) paires finalement au total
il y aura 2x2x2...x2, C(n;2) fois c'est à dire 2^C(n;2) tout comme le nombre de tournois.
Mais réflexion faite je ne pensais pas q'un tournoi c'était ça. Je fais moi même des tournoi d'échecs et il me semble qu'il y a réciprocité si je joue contre A, le contraire est vrai.Jusqu'à présent j'ai toujours eu un adversaire en face de moi.
Annuler
connectez vous
algèbre en post-bac