> Plus de cours & d'exercices de maths (mathématiques) sur le même thème : Problèmes [Autres thèmes]
	> Tests similaires : - Heure et durées (CE1/CE2) - Test de niveau(8)- Situations Problèmes 2 (CM2/6ème) - Heures et durées (7)- Bilan + Grand Test - Heures et durées(2)- Les unités de temps, Cours et Grand Test - Test de niveau(9)- Situations Problèmes 3 (CM2/6ème) - Problèmes : Vitesse /Durée/ Distance parcourue - Test de niveau (4)- Logique (Fin de cycle 2 des apprentissages fondamentaux) - Suites numériques
	> Double-cliquez sur n'importe quel terme pour obtenir une explication...

Graphes (2)- coloration d'un graphe (Niveau Terminale ES) - cours

Ce test poursuit l'étude des graphes abordée dans les tests n°45326 test, n°45970 test et n°45842 test

Graphes en TES

Coloration d'un graphe

Nombre chromatique

I. Coloration d'un graphe: exemple et algorithme

a) Exemple:

Ci-dessous la carte de six pays imaginaires; on a colorié cette carte à l'aide de 6 couleurs différentes...

Problème :

Est-il possible de colorier la carte en respectant les contraintes suivantes ?

- utiliser le minimum de couleurs ;

- faire en sorte que deux pays ayant une frontière commune soient coloriés de deux couleurs différentes...

Solution :

Pour chercher un tel coloriage, on n'utilise pas de carte; on travaille sur le graphe associé.

'On commence par colorer le pays qui a le plus de pays frontaliers'

graphe et graphe coloré: 3 en gris ; 1 et 5 en rouge ; 2 et 4 en bleu

b) Algorithme :

Colorer un graphe c'est colorer les sommets de telle façon que deux sommets distincts et adjacents aient toujours des couleurs différentes.

Méthode : Algorithme de Welch-Powell ou algorithme glouton

1. Ranger les sommets par ordre décroissant de leurs degrés ;
   
2. Choisir une couleur ;
   
3. Affecter cette couleur au premier sommet de la liste non encore coloré ;
   
4. Suivre la liste en attribuant cette même couleur à tout sommet
   

• qui n'est  pas encore coloré ;
  
•  et qui n'est pas adjacent à un sommet coloré avec cette couleur.

Continuer jusqu'à ce que la liste soit finie.

Si tous les sommets ne sont pas colorés, choisir une couleur qui n'est pas encore utilisée et recommencer les étapes 3 et 4 ;

Continuer tant que chaque sommet n'est pas coloré.

II. Graphes complets

• Lorsque chaque sommet est relié à chaque autre par une arête, le graphe est complet.

Exemples :

• Un graphe planaire est un graphe qui peut être représenté sur un plan, sans qu'aucune arête n'en croise une autre.

Les premiers circuits imprimés étaient moins fragiles quand le graphe du circuit était planaire.

• Soit G un graphe complet d'ordre p .

Si p est inférieur ou égal à 4, alors G est planaire ;
Si p est supérieur ou égal à 5, alors G n'est pas planaire.

• A l 'origine des graphes planaires, on trouve le théorème des 4 couleurs :
  

'Il est possible, en n'utilisant que quatre couleurs différentes, de colorer n'importe quelle carte de sorte que deux régions limitrophes reçoivent toujours deux couleurs distinctes.'

III. Nombre chromatique

Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorer le graphe; notons le  .

• Deux sommets distincts et reliés par une arête doivent avoir des couleurs différentes; lorsque le graphe est complet d'ordre n, son nombre chromatique    est n.

• On peut donner des couleurs différentes aux sommets. Donc si le graphe a n sommets, alors     n .

• Si le plus grand degré d'un sommet est r, alors   r+1.
  

• Si on peut extraire d'un graphe, un sous-graphe complet d'ordre p, alors p  .

Dans notre exemple:

Du graphe associé à la carte, on peut extraire un sous-graphe complet d'ordre 3 (les sommets 3, 5 et 6 et leurs arêtes)

donc 3  
D'autre part, on a coloré le graphe à l'aide de 3 couleurs; donc   3.
On peut conclure :  = 3

Pour trouver le nombre chromatique  d'un graphe, on cherche

- un encadrement de 

- une coloration du graphe en p couleurs: on en déduit   p.

Le plus souvent, on peut en déduire la valeur de  ...

Il peut arriver que l'on trouve 3     4 ; dans ce cas, on ne peut pas donner  !

A vous de jouer!

Avancé Tweeter Partager
Exercice de maths (mathématiques) "Graphes (2)- coloration d'un graphe (Niveau Terminale ES) - cours" créé par anonyme avec le générateur de tests - créez votre propre test !
Voir les statistiques de réussite de ce test de maths (mathématiques)

Merci de vous connecter à votre compte pour sauvegarder votre résultat.

1. Un examen comporte 6 options au choix. Chaque option se déroule sur une demi-journée; un candidat donné ne peut pas passer plus d'une option la même demi-journée. On cherche une organisation qui utilise le moins de demi-journées possibles, sachant qu'il y a des candidats inscrits en Sport (1), en Équitation (2) et Informatique (3); d'autres en Musique(4), Informatique (3) et Piscine (5) ; d'autres enfin en Danse (6) et Piscine (5).

Le graphe associé est

a) On peut extraire un sous-graphe complet d'ordre p = 534Je ne sais pas, et p est inférieur ou égal au nombre chromatique.

b) En étudiant les degrés des sommets, on peut affirmer que le nombre chromatique est inférieur ou égal à 543Je ne sais pas .

c) Pour que chaque élève puisse passer toutes ses options, il est impératif d'organiser cet examen sur 435Je ne sais pas demi-journées au minimum

2. Un musée est constitué de six salles numérotées de 1 à 6; le plan de ce musée est associé au graphe suivant dans lequel une arête représente une porte de communication entre deux salles .

a) Peut-on visiter chacune des salles du musée en passant une fois et une seule par chacune des portes ? ouinonon ne peut pas savoirJe ne sais pas

b) Peut-on visiter chacune des salles du musée en passant une fois et une seule par chacune des portes et en revenant au point de départ ? on ne peut pas savoirnonouiJe ne sais pas

c) Le conservateur du musée souhaite différencier chaque salle des salles voisines (c'est-à-dire accessibles par une porte) par la moquette posée sur le sol. Combien faut -il de moquettes au minimum pour réaliser ce souhait ? 342Je ne sais pas