Théorie des Graphes - Introduction

Institut National des Sciences Appliquées – Rouen

Département Architecture des Systèmes d'Information
[Link]@[Link]
 Histoire
• Graphe : concept récent pour un besoin très ancien.
• Demandeurs : les commerçants, les marins, les soldats
– Ne plus être dépendant de guides locaux.
– Évaluer la difficulté, longueurs, durées, risques, ressources
locales, …
• Représentation fonctionnelle ou cartographique
 Histoire (2)
• Fonctionnelle : (non ressemblante spatialement)
– Table de Peutinger : II ou IV siècle
• Graphique :
– Les portulants XIII et XIV siècle
– Cartes de Cassini (1696 -> 1789)
• Problème de la fonction à la représentation plane
d’une sphère (Ier siècle : Martin de Tyr puis
Mercator au XVI puis Lambert au XVIII)
 Les débuts
• Euler et les ponts de Königsberg en 1736
• Terme graphe avec JJ Sylvester en 1822
• Premier livre avec König (allemand) en 1936
• Problèmes militaires (2ème guerre mondiale)
– Création des Operations Research aux USA
– Organisation des convois (bataille de l’Altlantique)
– Blocus des ports (japonais)
– Répartitions des équipages dans les avions
– …
 L’évolution
• Après la guerre, essaimage vers
– Les grands comptes
– L’enseignement
– Les sociétés savantes
• Dans les années 70-80 : trou noir
• Aujourd’hui : une première approche du
problème technique (aide à la décision)
 Domaine dans l’entreprise
• Production
– Allocation de ressources
• Contraintes des ressources limitées
• Fonction objectif
• Ordonnancement
– Durée des tâches, dates de début, date au plus tôt,
… (Méthode Pert)
– Gestion des achats, stocks
• Logistique
– Placement des dépôts
– Organisations de tournées
 Domaine dans l’entreprise (2)
• Gestion des files d’attentes (configuration)
• Plan Qualité
– Statistique (fiabilité, …)
• Vente
– Théorie des jeux (clients, concurrents, …)
• Aspect social : pouvoir, relations, …
 Principes de base
• Utilisation de méthodes scientifiques (modèles
mathématiques)
• Finalité = Prise de décision et non la description d’un
phénomènes (statistiques, …) / Expliquer, Prévoir, Agir
• Modèle :
– Représentation d’un fragment de la réalité
– Simulations (manuelles impossibles)
– Classes de problèmes
• Résolution (solution exacte ou approchée)
– Problème de représentation des nombres, des erreurs d’arrondis
et des temps de calcul, algorithmique spécifique
 Modèle
• Obligation de bien formuler le problème
• Réduction de la réalité (le modèle n’est pas
la réalité) => Mesure de la perte de réalité
• Compromis entre précision et simplicité
• KISS = Keep It Simple, Stupid
• Outil d’AIDE à la décision
 Modèle (2)
• Définition : Une ou plusieurs relations
paramétrées liant des variables d’entrée et de
sortie
– Entrée :
• Exogènes (décrivent l’environnement, subies)
• Endogènes (contrôle, fixées dans une certaine limite)
– Sortie :
• Valeur optimale
• Structure optimale
 Modèle (3)

• Construit à partir d’hypothèses et d’instruments

– Hypothèses : Transcrit au moins une part de la réalité,
adaptées aux outils de traitement, modèle obtenu doit
être exploitable
– Instruments : graphe, suite, probabilités, …
 Modèle (4)
• Compatible (C) : propriétés de la réalité et du modèle
• Réelle (R) : propriétés de la réalité mais pas du modèle
• Formelle (F) : propriétés du modèle mais pas de la réalité
• Parfait (P) : toute propriété du modèle est propriété de la
réalité
• Complet (C2) : toute propriété de la réalité est propriété
du modèle

Réalité
Modèle
(R) (C) (F)
Modèle - Réalité = ∅ : (P)
Réalité - Modèle = ∅ : (C2)
 Modèle (5)

• Aspect syntaxique (mode de représentation) :

– Axiomes indépendants : ne découlent pas les uns
des autres (bases)
– Non contradictoire : les axiomes ne le sont pas
– Complétude : il n’existe pas de proposition ni
démontrable ni réfutable
– Décidable : il existe toujours une voie permettant
d’établir qu’une assertion est vraie ou non
 Modèle (5b)
• Exemple : Arrêt d'un programme – Existe-t-il
une fonction arret(P) permettant de
déterminer si un programme s'arrête ?
marrant (P)

début

tant que arret (P)

faire
fin tant que

fin
 Modèle (6)
• Aspect sémantique (liens de signification entre
les situations et le modèle):
– Exhaustivité : rend compte en plus d’autres pratiques
(augmentation des propriétés)
– Flexible : s’adapte à d’autres pratiques (générique)
– Fécondité : génère de nouvelles pratiques (IA)
– Validité : liens entre les prémisses et l’interprétation
des résultats (ne doit pas utiliser des propriétés du
modèle qui ne sont pas de la réalité)
– Réfutable : il existe une démarche permettant
d’aboutir à son rejet en cas de concurrence de
modèle
 Conséquences
• Ne pas oublier l’environnement
(psychologique, social, …)
• Suivi des solutions préconisées
• Problème sous-contraint
• Caractère incertain
 Processus de Modélisation
Modélisation / Collecte

Situation Problématique Modèle

Imperfections Résolution

Implantation des décisions Conclusions du modèle

Interprétation
 Classes de théorie
• Théorie des graphes
• Programmation linéaire
• Théorie des files d’attente (Markov)
• Optimisation non combinatoire (sans contrainte)
• Théorie des jeux (désinformation)
• …
 Théorie des Graphes
• Un réseau de transport est constitué de nœuds
(exemple ville) et d’arcs (exemple route)
• Chaque liaison représente un certain coût ou
poids (exemple distance en km)
• Remarque : Ici les fonctions d’étiquetage des
nœuds et des arcs sont rudimentaires
(contrairement aux problèmes bases de données)
 Formalisation - Problème
• Le problème devient alors « comment
joindre un nœud A à un nœud B» de
manière à ce que :
– On ne passe pas deux fois par le même nœud
(même endroit)
– On minimise la fonction de coût
• Plus sophistiqué (expression régulière)
 Exemple
Chaîne : (a1, a5, a6, a3, a2)
(-> non élémentaire)

Cycle : (a1, a5, a6, a4)

(-> élémentaire)

Chemin : (a1, a5, a7, a3)

(-> non élémentaire)

Circuit : (a5, a7, a3)

Forme générale de la théorie des graphes
• p-Graphe :
– Un graphe est un p-graphe  ∀ (i,j) ¬∃ plus de p
arcs (i, j)
• Fonction d'incidence : Ψ : U -> X x X
• Etiquetage des noeuds et des arcs :
– G (X, U, Ψ,ν , ε)
• Type abstrait
– Fonctions de manipulation :
• successeurs (Γ+), prédécesseurs (Γ -), ...
• Problèmes topologiques (chemin, …)
 Historique
• Problèmes de référence :
– Arrêt d’un algorithme (Turing, 1936)
– Gestion des flots (Ford-Fulkerson 1958)
– Fermeture transitive (Warshall 1962)
– Expressions régulières et bases de données
(Mendelzon, 1985)
 Programmation Linéaire -
Principe
• Une entreprise exerce des activités (A i) avec
une intensité variable
• Elle utilise des ressources (Ri) dont on connaît
les quantités disponibles
• On connaît les ratios d’utilisation des
ressources pour les différentes activités
• On connaît les retours sur investissements
 Formalisation - Problème
• Déterminer les intensités (non négatives),
auxquelles il faut exercer les activités A et B
de manière à ce que :
– La quantité des ressources consommées ne
dépasse pas la quantité des ressources
disponibles
– Le retour sur investissement soit maximum
 Exemple

• Activités :
– Activité A1 : production de cidre,
– Activité A2 : production de tartes aux pommes
• Ressources :
– Ressource R1 : des pommes,
– Ressource R2 : des employés
– Ressource R3 : de la pâte à tarte
• Quantités disponibles :
– Les pommes : 8 kg
– Les employés : 7 personnes
– La pâte à tarte : 3 kg
 Exemple (suite)
• Chacune des deux activités peut être exercée respectivement avec
une intensité x1, représentant le nombre de bouteilles de cidre et x2
le nombre de tartes aux pommes.
• La consommation des ressources pour exercer les activités au
niveau de l’unité (1 bouteille ou 1 tarte) :

A1 A2
R1 2 1
R2 1 2
R3 0 1

pour produire 1 bouteille de cidre (A1), on «consomme » 2 kg de

pommes (ressource R1) et 1 employé (ressource R2).
 Exemple (suite)

• Retour sur investissement (au niveau de l’unité) :

– Activité A1 : 4 (le prix de vente d’une bouteille de
cidre est 4 fois supérieur au prix de revient de ce
même cidre)
– Activité A2 : 5.

• Question : Que doit-on produire et dans quelles

quantités pour maximiser le retour sur investissement ?
 Les formes générales de la programmation
linéaire
• Un programme linéaire est un problème faisant intervenir un
certain nombre de variables réelles (x1 et x2 dans notre exemple).
• Ces variables doivent satisfaire un ensemble d’équations et/ou
d’inéquations linéaires.
• Une fonction linéaire de ces variables, dite fonction objectif doit
être rendue optimum (minimum ou maximum).
• Les ressources et les consommations doivent être additives et
divisibles (sinon c’est plus difficile)
(linéaire signifie que toutes les relations font intervenir des
variables du premier degré).
 Les formes générales de la programmation
linéaire (2)
La forme canonique du Problème P – (standard : Ax = b)
Ax ≤ b
x≥0
z = cx(max)
Avec A une matrice (m, n)
b un m-vecteur colonne
c un n-vecteur ligne
x un n-vecteur colonne et
C = { x ≥ 0, Ax ≤ b } représente les contraintes
z = cx(max) est la fonction objectif
 Historique
• Environnement (2ème guerre mondiale) :
– Terme du à Dantzig (simplexe 1947)
– Initialement : Programme = planification opérationnelle
mais maintenant Programme = Problème
d’optimisation
• Hypothèses :
– Linéarité des contraintes
– Proportionnalité des gains/coûts et consommations
– Divisibilité des variables
– Déterminisme des données
 Optimisation non combinatoire
• Départ :
– fonction (scalaire ou vectorielle)
– Une ou plusieurs variables réelles
• Objectif : Déterminer l’optimum de cette fonction
• Non combinatoire : le domaine de définition de la
fonction n’est pas un ensemble fini (ni même
dénombrable)
• Minimiser  Maximiser : max (cx) = - min (-cx)
 Problèmes
• Difficulté majeure : mise en œuvre informatique (temps
d’évaluation de la fonction, espace mémoire, …)
• Dérivabilité de la fonction (suivant les méthodes),
convexité, …
• Programmation en nombre entier (pas d’algorithme
universel efficace)
• Extremum local ou global (selon un voisinage ou sur
tout le domaine de la fonction)
• Problème varié : algorithmes nombreux (dichotomie,
newton , nombre d’or, …)⇒ Trouver la bonne classe de
problème
 Théorie des Jeux
• Organisation :
– Plusieurs centres de décisions (études de tous les
joueurs)
– Prise de décision dont dépend un résultat qui
concerne le joueur
• 3 grands principes
– Coopération pure : agrégation de préférences
individuelle pour conduire à l’intérêt général
– Lutte pure : duel
– Mixte : alliances « fluctuantes »
 Théorie des Jeux (exemple)
• Dilemme du prisonnier
• Jeux économiques :
– à somme nulles
– avec perte
• Marienbad, morpion, puissance 4, …
• Echecs
 Dilemme du Prisonnier
• 2 individus (A et B) en prison:
– Marché : dénoncer son complice ou non
• Si un individu dénonce et qu’il est dénoncé : les
deux ont une remise de peine (1 an)
• Si un individu dénonce et que l’autre couvre : le
premier à une remise de peine importante (5 ans) et
l’autre écope du maximum de peine
• Si les deux individus se couvre mutuellement : les
deux ont une remise de peine intermédiaire (3 ans)
– Question : Doit-on dénoncer ou couvrir ?
 Analyse
• Les deux s’entendent : ils améliorent leurs
situations vis à vis d’une dénonciation
• Mais un peut améliorer sa situation en dénonçant
l’autre
• Craignant cela, l’autre risque de dénoncer aussi,
dégradant la situation
• => Coopération mais sans garantie sur le tiers
(extension au système itératif : plusieurs décisions
dans le temps)
 Représentation

B couvre B dénonce

A couvre Compromis Gain pour B,

A = 3; B = 3 A = 0, B = 5

A dénonce Gain pour A, Double,

A = 5, B = 0 A = 1, B = 1
 Bibliographie
• Berge C. : Graphes, Gauthier-Villars
• Faure R. : Précis de Recherche Operationnelle, Dunod Décision
• Gondran M., Minoux M. : Graphes et algortihmes,
Collection de la DER-EDF
• Garey M.R., Johnson D.S. : Computers and intractability :
a guide to the theory of NP-Completeness, Freeman
• Sites : [Link] (RESO)
• Généraliste : que sais-je ?, PUF
• …