Problème de maths Tes spé maths - Graph
Bonjour a tous, voici le problème qui me pose beaucoup de problèmes: (j'ai joint le schéma)
On met en place des feux aux cinq jonctions d'un carrefour (qui n'est pas un rond-point). On veut les synchroniser au mieux pour que pour
que le maximum de voitures puissent traverser simultanément le carrefour sans se croiser. Les voitures roulent sur les files de droite.
Les voies E et C sont à sens unique (sens indiqué par la flèche).
On convient que le mot AB représente la traversée du carrefour venant de A et allant vers B. Deux traversées sont incompatibles,
simultanément, si leur trajectoire doivent se croiser. Par exemple les trajectoires AC et BC sont compatibles ; les traversées AC et BC sont
incompatibles.
1) Représenter le graphe G des traversées incompatibles
2) Expliquer comment résoudre le problème par une coloration minimale
3) déterminer le nombre chromatique du graphe G. En déduire le temps d'attente maximal d'une voiture au carrefour, sachant que le temps d'attente maximum d'un feu est de 2 minutes.
-----