Partie I : Définition des termes

1. Notion de graphe et sous-graphe

Définition:

• Un graphe G est un schéma contenant des points nommés sommets, reliés ou non par des segments appelés arêtes.
  Un graphe est dit simple s’il ne comporte aucune boucle et que deux arêtes ne relient jamais la même paire de sommets.
  Un graphe est dit complet si tous les sommets sont adjacents les uns avec les autres.

• 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.

Il est dit stable lorsqu’il ne comporte aucune arête, autrement dit si deux sommets quelconques ne sont pas adjacents.

Exemple:

Soit le graphe G :

Figure 1 : G

Si G est le graphe complet d’ordre 4, alors le graphe G’ est un sous-graphe de G mais le graphe G’’ n’en est pas un:

Figure 2 : G’

Figure 3 : G ‘ ‘

2. Sommets, arêtes, ordre et degré d’un graphe

Définitions :

• Un sommet d’un graphe correspond à un point du graphe composé ou non par des arêtes.
• Les arêtes représentent les liaisons entre un sommet et un autre ou un sommet sur lui-même.

• L’ordre d’un graphe est le nombre de sommets de ce graphe.
• Dans un graphe, le degré de chaque sommet est le nombre d’arêtes dont il est l’une des extrémités.

Propriété :

• La somme des degrés de tous les sommets d’un graphe est égal au double du nombre total d’arêtes de ce graphe

Exemple :

Soit le graphe G :

• Les sommets sont A, B et C
• L’ordre du graphe est 3.
• Le degré de A est d(A)=2
• d(A)+d(B)+d(C)=2+2+2=6
  La somme des degré de tous les sommets est bien égale au double du nombre total d’arêtes du graphe

3. Nombre chromatique

Colorier un graphe c’est associer à tout sommet une couleur telle que deux sommets adjacents n’aient pas la même couleur.

Le plus petit nombre de couleurs nécessaire pour colorier un graphe s’appelle le nombre chromatique du graphe.

Le nombre chromatique, noté χ(G), d’un graphe est inférieur ou égal à dmax+1 où dmax est le plus grand degré des sommets.

Nous pouvons déterminer un encadrement de ce nombre, avant de le trouver de manière exacte avec l’algorithme de Welsh-Powel.

 

Exemple :

Soit le graphe G :

Prenons le cas de B-C-G

• Il faut au minimum 3 couleurs car B-C-G représente un graphe complet d’ordre 3: Les 3 sommets ne doivent donc pas avoir la même couleur pour respecter la règle.

Nous savons donc que χ(G) ≥ 3

• Le sommet de plus haut degré est C, de degré 5. Il faut donc au plus 6 couleurs.

Donc,  χ(G) ≤ 6

Nous avons un encadrement :  3 ≤ χ(G) ≤ 6