Aide à la décision Bloc1 : Théorie des graphes et problèmes dordonnancement Mohamed Ali Aloulou...

Aide à la décision

Bloc1 : Théorie des graphes et problèmes d’ordonnancement

Mohamed Ali Alouloualoulou@lamsade.dauphine.fr

Une partie de ces transparents a été élaborée en se basant sur le document de

Pierre Lopez, LAAS, Toulouse http://www.laas.fr/~lopez/cours/GRAPHES/graphes.html

Plan du bloc 1

1. Qu’est ce qu’on peut faire avec la théorie des graphes ?

2. Concepts généraux en théorie des graphes

3. Le problème du plus court chemin

4. Problème central de l’ordonnancement

http://www.lamsade.dauphine.fr/~aloulou/cours/L3STCF/

Pourquoi la théorie des graphes ?

• Modélisation– Plusieurs problèmes dans différentes

disciplines (chimie, biologie, sciences sociales, applications industrielles, …)

– Un graphe peut représenter simplement la structure, les connexions, les cheminements possibles d’un ensemble complexe comprenant un grand nombre de situations

• Un graphe est une structure de données puissante pour l’informatique

Exemples

1. Concepts généraux en théorie des graphes

• Définitions

• Représentations d’un graphe

• Notions de base

• Graphes particuliers

• Algorithme de détection de circuits

• Algorithme vérifiant qu’un sommet est racine (ou pas) d’un graphe

• Concepts généraux en théorie des graphes

Définitions• Concepts orientés

– Un graphe G(X,U) est déterminé par

• Un ensemble X={x1,…,xn} de sommets

• Un ensemble U={u1, …, um} du produit cartésien X×X d’arcs.

– Un p-graphe : pas plus que p arcs (xi,xj)

3-graphe

1-graphe = graphe

boucleArc u=(xi,xj)

• Concepts généraux en théorie des graphes

Définitions• Graphes et applications multivoques

– xj est successeur de xi si (xi,xj)U– L’ensemble des successeurs de xi est noté

(xi)– L’ensemble des prédécesseurs de xi est noté

-1(xi) est appelée une application multivoque

• Pour un 1-graphe, G peut être parfaitement déterminé (ou caractérisé) par (X,)

• Concepts généraux en théorie des graphes

Définitions

• Concepts non orientés– On s’intéresse à l’existence d’arcs entre deux

sommets sans en préciser l’ordre– Arc = arête– U est constitué de paires non pas de couples– Multigraphe : plusieurs arêtes entre deux

sommets– Graphe simple = non multigraphe + pas de

boucles

• Concepts généraux en théorie des graphes

Représentations d’un graphe

1. Matrice d’adjacence

Pour un graphe numérisé : remplacer 1 par la valeur de l’arc

Place mémoire : n²

• Concepts généraux en théorie des graphes

Représentations d’un graphe

2. Matrice d’incidence sommets-arcs

Place mémoire : n x m

• Concepts généraux en théorie des graphes

Représentations d’un graphe3. Listes d’adjacence

Place mémoire : n+1+m

• Concepts généraux en théorie des graphes

Représentations d’un graphe4. Dictionnaire des suivants / préédents

• Concepts généraux en théorie des graphes

Notions de base

• Concepts généraux en théorie des graphes

Notions de base

• Concepts généraux en théorie des graphes

Notions des base• Chaîne – Cycle

• Chemin – Circuit

• Ascendant – descendant – racine – anti-racine

• Concepts généraux en théorie des graphes

Connexité dans les graphes• Le terme parcours regroupe les chemins, les

chaînes, les circuits et les cycles• Un parcours peut être

– élémentaire : tous les sommets sont distincts– simple : tous les arcs sont distincts– hamiltonien : passe une fois et une seule par chaque

sommet– eulérien : passe une fois et une seule par chaque arc– préhamiltonien : ou moins une fois par chaque

sommet– préeulérien : au moins une fois par chaque arc

• Concepts généraux en théorie des graphes

Connexité dans les graphes

• Exemple– Le problème du voyageur de

commerce : un voyageur de commerce doit visiter n villes données en passant par chaque ville exactement une fois et doit revenir à la ville de départ.

Trouver un circuit hamiltonien de coût minimal dans un graphe valué

• Concepts généraux en théorie des graphes

Connexité dans les graphes• Connexité

• Concepts généraux en théorie des graphes

Connexité dans les graphes• Forte connexité

• Concepts généraux en théorie des graphes

Graphes particuliers• Graphes sans circuit

– Décomposition en niveaux

• Graphe biparti• Graphe planaire• Hypergraphe• Arbre• Forêt• Arborescence

• Concepts généraux en théorie des graphes

Algorithme de détection de circuits

• Concepts généraux en théorie des graphes

Algorithme de vérifiant qu’un sommet est racine d’un graphe

Exemples

En 1736, Euler a montré que c’est impossible !!

retour

retour

Références bibliographiques

• P. Lopez, Cours de graphes, LAAS-CNRS http://www.laas.fr/~lopez/cours/GRAPHES/graphes.html

• Ph. Vallin and D. Vanderpooten. Aide à la décision : une approche par les cas. Ellipses, Paris, 2000.

• M. Gondron, M. Minoux, Graphes et algorithmes, Eyrolles, Paris, 1984• C. Prins, Algorithmes de graphes, Eyrolles, Paris, 1994• Ph. Lacomme, C. Prins, M. Sevaux, Algorithmes de graphes, Eyrolles, 2003• B. Baynat, Ph. Chrétienne, …, Exercices et problèmes d’algorithmique, Dunod, 2003• E. Lawler, Combinatorial Optimization – Networks and matroids, Dover Publications,

INC, 1976. • Cormen, Leiserson, Rivest, Stein, Introduction à l’algorithmique, DUNOD, 2ième

édition, série Sciences Sup,2002.• Berstel, Beauquier, Chrétienne, Eléments d’algorithmique, MASSON, collection MIM,

1992. Téléchargeable gratuitement!

http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.html• R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: Theory, Algorithms and

Applications http://web.mit.edu/jorlin/www/