Inscription / Connexion Nouveau Sujet
Devoir maison, sous graphe
Bonjour, j'ai un souci pour un devoir maison en spé, Je join en image le graphe et le tableau de l'énoncé que je ne peux pas faire ici. Je suis un peu embrouillé avec les graphes, je ne sais pas trop comment comprendre les exercices ni analyser ce qui est demandé dans les énoncés.
Pour terminer l'organisation d'un bac blanc, le proviseur d'un lycée doit tenir compte du fait que certaines épreuves doivent se dérouler simultanément étant donné qu'elles sont communes aux différentes classes.
Les contraintes de ce proviseur sont consignées dans le tableau ci-contre. Chaque épreuve est organisée sur une demi-journée.
On se propose de trouver quel est le nombre maximal d'épreuves que l'on peut organiser au cours d'une même journée.
1)Associez à ce problème un graphe tel qu'une arête relie deux épreuves lorsqu'une même classe doit subir les épreuves correspondantes.
2)Déterminer alors le nombre maximal d'épreuves que l'on peut organiser au cours d'une même demi-journée.
--> 1) cf image jointe.
--> 2) Je ne sais pas trop comment lire ce graphe, en imaginant qu'il soit correct…
J'aurais dit qu'au maximum on peut avoir trois épreuves simultanément, à savoir éco allemand et histoire géo, mais je ne suis vraiment pas sûr.
Et quant à la rédaction, comment formuler ceci ?
Quelque chose comme « On cherche un sous graphe tel qu'un maximum de sommet ne soient pas reliés. On a le sous graphe Eco Allemand Philo » ??
Merci d'avance pour votre aide.
petite erreur quand tu termines par la phrase :
On a le sous graphe Eco Allemand Philo
je suppose que tu voulais dire :
On a le sous graphe Eco Allemand Hist-Géo
mais la démarche est correcte
il faut trouver un sous ensemble de points du graphe qui n'aient aucun lien entre eux;
et ensuite déterminer le plus grand de ces sous-ensembles parmi eux.
celui que tu proposes Eco Allemand Hist-Géo est un tel sous-ensemble, il possède trois éléments.
pour justifier que c'est le plus grand, procède par élimination
imagine qu'il y ait les maths dans une solution plus grande, alors on ne peut adjoindre que l'allemand, donc toute solution qui contient les maths ne peut être plus grande
et tu fais la même chose pour toutes les autres matières.
remarque : il y a 6 sommets
du sommet maths partent 4 arcs, qui éliminent 4 autres sommets
donc 6-1-4=1 il ne reste, sans même le connaître, que 1 sommet possible
du sommet philo ou anglais partent 3 arcs, qui éliminent 3 autres sommets
donc 6-1-3=2 il ne reste, sans même le connaître, que 2 sommets possibles
on ne pourra donc pas dépasser cette solution
Eco Allemand Hist-Géo
même si on peut envisager d'en trouver une autre (je n'ai pas vérifié) qui l'égale.
Je ne vois votre réponse que maintenant, mais merci beaucoup, c'est très claire et détaillé, et je comprend mieux la démarche. Oui, c'est une erreur d'inattention dans ma phrase...
En tout cas, c'est vraiment très gentil de m'avoir aidé, vos explications sont très précises. Encore un GRAND merci, bonne soirée à vous 
Salut,
Je passais par hasard...
Ce problème s'appelle "recherche d'un sous-graphe stable maximal".
Il serait bon que ce terme apparaissa dans la réponse...
Bonne soirée
apparaissa ? apparaisse !
un sous-graphe, qui plus est stable, et maximal, c'est d'un chic dans les soirées mondaines 
Bigre !
Mais que vient donc faire ce "a" final dans ma conjugaison que je croyais exemplaire ?
Dérapage claviérique sans aucun doute.
Salut dhalte
Annuler
connectez vous