Exercice sur les graphes

[Alessandra]

Bonjour, pouvez-vous m'aider à cet exercice sur les graphes s'il vous plaît ?

Enoncé:

Joanne éducatrice canin: elle donne des leçons d'éducation le samedi après-midi. Neuf chiots sont présents: Allegro, Bronx, Chouchou, Delco, Euclide, Falbala, Galipette, Homère et Indigo. Joanne souhaite réaliser des exercices d'apprentissage par petits groupes de deux ou trois chiens. Falbala ne pense qu'à jouer si elle est trop proche de Bronx, Chouchou ou Euclide. De même, Delco est très inattentif si Bronx ou Falbala sont à proximité ! Indigo ne supporte pas le caractère trop fougueux de Galipette. Enfin le turbulent Allegro ne supporte la présence d'aucun autre chiot, sauf Euclide et Homère.

1. Représenter cette situation à l'aide d'un graphe G dont les sommets sont les noms des chiots et relier entre eux les chiots que l'on ne peut pas mettre ensemble pour ce travail de groupe.
- J'ai réussi à représenter le graphe G
2. Le graphe G est-il connexe ? Expliquer.
- J'ai trouvé que le graphe G est connexe.

3. Si Joanne veut faire travailler les chiots en groupe, quel est le nombre minimal de groupes nécessaires ? Justifier la réponse
4. Peut-on proposer une répartition des chiots en groupes de deux à trois chiots pouvant travailler ensemble . Justifier la réponse
- Je n'ai pas réussi à répondre aux deux dernières questions

Merci d'avance

[catamat]

Bonjour

Tu aurais pu prendre en photo le graphe que tu as construit et le mettre ici, on verrait s'il est correct.

D'abord le graphe n'est pas connexe car le sommet H est isolé, il n'est relié à aucun autre sommet.

Pour la question 3 c'est une question de coloration, il faut trouver le nombre chromatique, soit chercher s'il y a un Kn (avec n le plus grand possible) puis trouver une coloration en n couleurs. n est alors le nombre chromatique vous avez du faire des exemples en cours.

Pour la question 4
On cherche des sous ensembles stables du graphe, c'est à dire des ensembles de sommets de la même couleur.
Pour des groupes de 3 chiens il faut 3 groupes de 3 chiens, donc trois couleurs, si le nombre chromatique est 3 tu devrais trouver une possibilité.
Pour des groupes de 2 ou 3 chiens soit 1 groupe de 3 et 3 groupes de 2 cette fois on a 4 groupes donc 4 couleurs et c'est encore plus facile à colorier.

[Alessandra]

Pour la question 3, je n'ai jamais fait ça en classe, dans mon énoncé on ne parle pas de coloration ... mais dans un sujet de bac trouvé sur internet oui.
Du coup pour cette question j'ai dit qu'un sous graphe A-B-D-F est complet et d'ordre 4. Donc le nombre de groupe minimal nécessaire est 4.

Pour la question 4 j'ai trouvé que Delco et Homère étaient isolés donc il fallait les mettre ensemble. J'ai donc trouvé 4 groupes:
G1: Delco et Homère
G2: Bronx, Chouchou, Indigo
G3: Allegro et Euclide
G4: Falbala et Galipette
Est-ce bien cela ?
Merci

[catamat]

Ok en effet il y a un K4 (A-B-D-F) donc il faut au moins 4 couleurs, mais il faut quand même justifier que cela suffit en donnant une coloration en 4 couleurs.

Cette coloration peut être celle des 4 groupes que tu donnes.

Quand tu dis "j'ai trouvé que Delco et Homère étaient isolés donc il fallait les mettre ensemble" disons qu'ils ne sont pas adjacents donc on PEUT les mettre ensemble (mais H pourrait intégrer n'importe quel groupe en fait)

Si tu n'as pas vu les colorations de graphes c'est important, en fait on colore de la même couleur les sommets quine sont pas adjacents donc ici les chiens compatibles ce qui permet de former les groupes demandés.

Il y a des tas de cours sur internet par ex :
https://www.meilleurenmaths.com/images/ ... graphe.pdf
https://www.mathematiquesfaciles.com/gr ... _45761.htm

[Alessandra]

On n'a pas vu les colorations de graphes alors qu'on a fini le chapitre... Donc il ne faut pas que j'en parle car ils ne se trouvent pas dans mon cours ... Est-ce que ce que j'ai écrit plus haut (avec vos éléments de corrections pour la question 4) me permet de bien répondre aux questions tout en restant dans le programme du cours donné par mon professeur ?

Merci

[catamat]

Du coup pour cette question j'ai dit qu'un sous graphe A-B-D-F est complet et d'ordre 4. Donc le nombre de groupe minimal nécessaire est 4.

. J'ai donc trouvé 4 groupes:
G1: Delco et Homère
G2: Bronx, Chouchou, Indigo
G3: Allegro et Euclide
G4: Falbala et Galipette
Est-ce bien cela ?
Merci

Oui comme cela c'est correct puisque tu dis que c'est au moins 4 et que tu donnes un exemple avec 4 groupes donc c'est bien le nombre minimal de groupes (ce que j'appelais le nombre chromatique ... mais tu n'es pas obligée d'en parler)

[Alessandra]

D'accord, merci beaucoup pour votre aide !

Bonne soirée