Scribd
Importer
49 vues2 pages

Coloration et nombre chromatique des graphes

Ce document définit les notions de sous-graphe, de coloration d'un graphe et de nombre chromatique. Il présente des propriétés pour encadrer le nombre chromatique d'un graphe et décrit un algorithme de coloration couramment utilisé.

Transféré par

big DADY 75
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
49 vues2 pages

Coloration et nombre chromatique des graphes

Ce document définit les notions de sous-graphe, de coloration d'un graphe et de nombre chromatique. Il présente des propriétés pour encadrer le nombre chromatique d'un graphe et décrit un algorithme de coloration couramment utilisé.

Transféré par

big DADY 75
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

2012-2013

Spécialité Mathématiques
Term ES

Coloration
Nous considèrerons les graphes non orientés.

1 Notion de sous-graphe

Définitions 1
• Un sous-graphe d’un graphe G est un graphe constitué de certains sommets de G et de toutes
les arêtes qui les relient.
• Un sous-graphe stable est un sous-graphe sans arête.

2 Nombre chromatique

Définitions 2
• Colorer un graphe consiste à affecter une couleur à chacun des sommets de sorte que deux sommets
adjacents ne soient pas de la même couleur.
• Le nombre chromatique d’un graphe G est le nombre minimal de couleurs nécessaires pour le
colorer. On le note χ(G).

3 Encadrement du nombre chromatique


Propriétés :

• Le nombre chromatique χ d’un graphe G est inférieur ou égal à r+1, où r est le plus grand degré des
sommets.
χ(G) ≤ r + 1
• Le nombre chromatique χ d’un graphe G est supérieur ou égal à l’ordre n du sous-graphe complet
le plus grand de G.
χ(G) ≥ n

4 Algorithme de coloration

Page 1/2
2012-2013
Spécialité Mathématiques
Term ES

Cet algorithme couramment utilisé permet d’obtenir une assez bonne coloration d’un graphe, c’est à
dire une coloration n’utilisant pas un trop grand nombre de couleurs. Cependant, il n’assure pas que le
nombre de couleurs utilisées soit minimum (et donc égal au nombre chromatique du graphe).

Page 2/2

Vous aimerez peut-être aussi