Inscription / Connexion Nouveau Sujet
Problème de graphe
Bonjour,
j'ai un problème avec la question d'un exercice de spé maths qui allie les matrices et les graphes
J'ai un graphe qui contient 7 sommets A B C D E F G
Ces sommets sont reliés par des arêtes
Chaque sommet représente un aéroport et chaque arête représente une liaison entre 2 aéroports
La question est la suivante : un artiste souhaite décorer chaque aéroport en utilisant une couleur de sorte que 2 aéroports adjacents n'utilisent pas la même. Combien de couleurs lui faudra-t-il au minimum ?
J'ai réfléchi et essayé plusieurs choses mais rien de concluant. Si vous pouviez m'aider, ça serait sympa.
Merci d'avance.
Avec des couleurs ? Je ne comprends pas où tu veux en venir
J'ai essayé de faire le graphe inverse, c'est à dire relié les sommets qui ne sont pas adjacents dans le graphe initial, mais après je ne sais pas quoi en faire...
Juste voir s'il était possible de donner une réponse avec le graphe.
Exemple :
4 sommets reliés en quadrilatère cela donne que 2 couleurs
5 sommets reliés en pentagone, cela donne que 3 couleurs.
Annuler
connectez vous