Théorie des graphes : coloration d’un graphe à l’aide d’un Algorithme Glouton.

I) Théorie des graphes

 

La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes.

Un graphe est un ensemble de points nommés nœuds (ou sommets) reliés par des traits ou flèches nommées arêtes. L'ensemble des arêtes entre nœuds forme une figure similaire à un réseau. Différents types de réseaux sont étudiés suivant leur genre de forme et propriétés ; les arbres sont une sous-catégorie plus simple de graphes particulièrement importante et qui est très étudiée, notamment en informatique.

 

Exemple de graphe non orienté

Les arêtes peuvent être orientées (flèches) ou non orientées (traits). Si les arêtes sont orientées, la relation va dans un seul sens et est donc asymétrique, et le graphe lui-même est dit orienté. Sinon, si les arêtes sont non orientées, la relation va dans les deux sens et est symétrique, et le graphe est dit non orienté.

Exemple de graphe non orienté

Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau ( réseau social, réseaux informatique, télécommunications, etc) et dans bien d'autres domaines (par exemple génétique ) tant le concept de graphe, à peu près équivalent à celui de ralation binaire, est général. De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la conjecture de Hadwiger, en font une branche vivace des mathématiques discrètes.

 

II) Algorithme Glouton

Principe :

En informatique, un algorithme glouton (greedy algorithm en anglais) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local.  En algorithmique, et plus précisément en optimisation combinatoire, de nombreux algorithmes fonctionnent en faisant une série d'étapes, avec des choix. Une méthode classique est la programmation dynamique qui permet de tester tous les choix. Cependant les complexités des algorithmes de ce type sont parfois trop grandes et l'on choisit d'autres méthodes. L'une de ces méthodes est de choisir localement la meilleure solution : ce sont les algorithmes gloutons.

Exemple d’algorithme Glouton avec le rendu de monnaie :

On dispose de pièces de monnaie le système monétaire européen (en centimes : 1, 2, 5, 10, 20, 50, 100, 200).

Pour payer une somme S (entier naturel quelconque), on aimerait utiliser le nombre minimal de pièces possibles.

Pour cela, l’algorithme glouton donne la plus « grosse » pièce possible.

Puis à nouveau la plus grosse pièce possible pour le montant restant.

Puis à nouveau la plus grosse pièce possible pour le montant restant.

Etc…

L'algorithme glouton donne la somme suivante pour 37 : 20+10+5+2.

Choix optimal ?

L’algorithme mène-t-il toujours à payer avec un nombre minimal de pièces ? La réponse est non.

Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal.

Pour résumer :

Un algorithme glouton construit une solution pas à pas

  • Sans revenir sur ses décisions,
  • En effectuant à chaque étape le choix qui semble le meilleur,
  • En espérant obtenir un résultat optimum global mais suivant les problèmes pas de garantie d’optimalité (heuristique glouton)
  • Peu couteuse (comparée à une énumération exhaustive)
  • Choix intuitif

Nous allons à présent résoudre la coloration d’un graphe grâce a un algorithme glouton.

 

III) Coloration d'un graphe à l'aide d'un algorithme glouton :

Problématique de la coloration d’un graphe :

On cherche à obtenir une coloration des sommets d’un graphe qui satisfasse à la contrainte suivante : deux sommets voisins n’ont jamais la même couleur.

On cherche à optimiser le nombre de couleurs utilisées. Le plus petit nombre de couleurs permettant la coloration est appelé nombre chromatique du graphe.

Un algorithme glouton va bien sur nous aider à résoudre ce problème.

L’algorithme :

Graphe G et Couleurs 1,2,3,4. Les sommets de G sont numérotés de 1 à n (s1,s2,…,sn)

I un entier.

Début

Pour I allant de 1 à n :

Affecter a si la plus petite couleur non affectée à ses voisins déjà coloriés

FinPour

Afficher le nombre de couleur utilisée

Fin

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *