Salut à tous,  j'ai un exercice sur les graphes à faire pour un devoir maison, j'ai réussi les premières questions mais sur la suite je bloc un peu lol …pouvez vous m'aider s'il vous plait : )

Exercice 2. Le schéma ci-contre représente un carrefour. Le tableau suivant précise les « franchissements » possibles de ce carrefour. (La circulation de A vers E est considérée comme un « franchissement » même si on ne traverse pas le carrefour.)

En arrivant par A il est possible d'aller en C,E
                B                           A,E,D
                C                             A,D
                D                             C,A
                E                             C,D
Les franchissements A-C et B-E ne peuvent naturellement pas être autorisés simultanément sous peine de collision. On se propose de déterminer le nombre minimal de phases des feux de signalisation nécessaire au fonctionnement de ce carrefour.
a)-Modélisez ces incompatibilités à l'aide d'un graphe dont les sommets représentent les franchissements
-possibles et les arêtes les incompatibilités entre franchissements.
Cette question la je l'ai réussi, je vous donne les sommets et leurs degrés :
AC : 6 (avec EC, DA, DC, CD, BD, BE) ; AE : 1 (avec BE) ; BA : 2 (avec DA et CA) ; BE : 4 (avec AE, AC, DA et CA) ; BD : 6 (avec AC, ED, EC, DA, CD et CA) ; CA : 4 (avec BD, BE, BA, DA) ; CD : 5 (avec DA, EC, ED, AC, BD) ; DC :2 (avec EC et AC) ; DA : 7 (avec EC, AC, BA, BE, BD, CA, CD) ; EC :5 (avec DA, DC, CD, BD, AC) ; ED :2 (avec CD, BD).
b) Montrer que (EC,AC,BD,CD,DA) est un sous-graphe complet d'ordre 5? J'ai refait ce graphe d'ordre 5 et les sommets sont bien adjacents deux à deux, il est donc complet.
c) Que peut-on dire du sommet DA ? En déduire un encadrement du nombre chromatique du graphe. je ne vois pas ce que DA a de particulier :S, peut être que c'est parce que ce sommet est adjacent à tous sauf à 3 sommets: ED, AE, DC donc le nombre chromatique serait égal à 3+1= 4 car il faut aussi que ce sommet ai une couleur, donc le nombre chromatique est égal à 4 et je donne une couleur à chaque groupe.
d) Proposer une coloration du graphe. En déduire son nombre chromatique.
Une couleur pour ED, AC, AE, CA ; une autre pour BA, BE, BD et EC ; une autre pour DA et DC et enfin une dernière pour CD. Le nombre chromatique est 4.
e)Que peut-on dire d'un ensemble de sommets ayant même couleur ? À quoi peut correspondre le nombre chromatique de ce graphe ?
Lorsqu'un ensemble de sommets a la même couleur cela veut dire qu'aucun de ces sommets n'est adjacent à l'autre. Si l'on regroupe tous ces sommets en un graphe, on remarque que c'est un graphe stable.?? Et le nombre chromatique correspond au nombre minimum de cycles que doivent respecter les feux de signalisation de ce carrefour.

Merci beaucoup beaucoup beaucoup c'est super sympas!