Terminale Economique et Sociale > Mathématiques > Graphes > Graphes

GRAPHES

Tu dois disposer d'un abonnement
pour regarder la vidéo

L'abonnement aux Bons Profs permet de profiter de toutes les vidéos de rappels de cours dans toutes les matières de la 6e à la Terminale.

Ces vidéos sont présentées par des professeurs de l'Education nationale et permettent de revoir en quelques minutes toutes les notions du cours.

Demande à tes parents de te créer un compte. C'est très simple et tu pourras démarrer tes révisions immédiatement.

COLORIER UN GRAPHE

Permalien

Télécharger la fiche de cours Les téléchargements sont réservés uniquements aux abonnés

Colorier un graphe

 

On souhaite colorier un graphe avec un minimum de couleurs en ayant comme contrainte que deux sommets voisins aient des couleurs différentes. Le nombre minimal de couleurs est appelé le nombre chromatique

On dispose du drapeau suivant que l'on souhaite colorier.

d0791d031cb1293e18be881b7ef72600d78a054a.png

 

Pour se faire, on réécrit ce drapeau sous forme d'un graphe dont les sommets représentent les différentes zones et les arêtes traduisent que deux zones se touchent. 

On écrit sur chaque sommet son degré. 

7da9415fecf737ff20364b1a20ccff059653564a.png

Pour colorier le graphe, on utilise l'algorithme de Welsh-Powell.

 

On classe par ordre décroissant du degré les différents sommets sur la première ligne du tableau et par ordre alpha

Il reste 70% de cette fiche de cours à lire

Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.