Aide exercice de graphe terminale ES

[LisaBlkm]

Bonjour, cherche de l’aide pour que quelqu’un m’explique comment répondre aux questions de cet exercice sur les graphes.


À un examen, les candidats peuvent choisir deux ou trois options parmi les six options proposées :
-graphes
-langue régionale
-piano
-latin
-natation
-vélo
Certains élèves ont choisi les options graphe, langues régionales, piano. D’autres vélos et latin. D’autres enfin langues régionales et natation. Les élèves passent au plus une épreuve chaque jour. À l’aide de la théorie des graphes, répondez aux questions suivantes :
Certains élèves ont choisi les options graphes, langue régionale, piano. D’autres vélo et latin. D’autres enfin langue régionale et natation. Les élèves passe au plus une épreuve chaque jour. À l’aide de la théorie des graphes, répondez aux questions suivantes :

1) combien peut-on programmer des preuves d’option au maximum dans une journée ?

2) quelle est la durée minimum de l’ensemble des épreuves optionnel ? Pourquoi ?


J’ai compris comment dessiner le graphe qui représente les options et le tableau avec l’ordre des points mais je ne comprends pas vraiment comment répondre aux questions. Je voit remercie d’avance de vos réponses !

[GaBuZoMeu]

Je vois un graphe avec 6 sommets et 5 arêtes. Ça correspond à ce que tu as ? J'ai besoin de savoir si on parle bien du même graphe, avant de voir comment l'utiliser pour répondre aux questions.

Qu'appelles-tu "le tableau avec l’ordre des points" ???

[LisaBlkm]

Je vois un graphe avec 6 sommets et 5 arêtes. Ça correspond à ce que tu as ? J'ai besoin de savoir si on parle bien du même graphe, avant de voir comment l'utiliser pour répondre aux questions.

Qu'appelles-tu "le tableau avec l’ordre des points" ???

Oui j’ai bien la même chose que vous pour le graphe. Le tableau j’y met juste l’ordre de chaque points (ex: le vélo est seulement relié au latin).

[GaBuZoMeu]

Ce tableau ne me semble pas d'une utilité folle. Tu veux répartir les sommets du graphe en paquets (chaque paquet correspondant à un jour d'épreuves) tel que dans chaque paquet il n'y ait pas deux sommets reliés par une arête.
La question 1 te demande combien de sommets au maximum on peut mettre dans un tel paquet, et la question 2 combien de paquets au minimum pour avoir tous les sommets.

[LisaBlkm]

Ce tableau ne me semble pas d'une utilité folle. Tu veux répartir les sommets du graphe en paquets (chaque paquet correspondant à un jour d'épreuves) tel que dans chaque paquet il n'y ait pas deux sommets reliés par une arête.
La question 1 te demande combien de sommets au maximum on peut mettre dans un tel paquet, et la question 2 combien de paquets au minimum pour avoir tous les sommets.

Je n’ai pas bien compris l’histoire des paquets, il est possible de donner des exemples s’il vous plaît ?

[GaBuZoMeu]

Les six sommets de ton graphe sont bien les six options ?
Deux options sont reliées par une arête quand il existe des étudiants qui ont ces deux options dans leur choix, tu es bien d'accord ?
Un paquet, c'est un ensemble d'options qui peuvent se passer le même jour , c.-à-d. un ensemble de sommets du graphe tel qu'il n'y en ait pas deux reliés par une arête.
Si tu veux, on peut formuler ça en termes de coloration de graphe : on cherche à colorier le graphe de telle façon que deux sommets reliés par une arête ne soient jamais de la même couleur. Les couleurs sont alors les paquets qui nous intéressent : les épreuves d'options de même couleur peuvent se passer le même jour.

[LisaBlkm]

J’avais cru comprendre qu’il n’y avait que trois combinaisons possibles, on peux prendre les options individuellement ?