79
Éric Sopena Avril 2005 Théorie des graphes Quelques exemples Quelques exemples d’application… d’application…

Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Embed Size (px)

Citation preview

Page 1: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Théorie des graphes

Quelques exemples Quelques exemples d’application…d’application…

Page 2: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Plan de la présentation IntroductionIntroduction

rappel de quelques définitions de base, bref rappel de quelques définitions de base, bref historique, historique, un premier exempleun premier exemple……

Quelques exemples d’applicationQuelques exemples d’applicationChimie, sociologie, bio-informatique, recherche Chimie, sociologie, bio-informatique, recherche opérationnelle, réseaux de communication, opérationnelle, réseaux de communication, fonctionnement de systèmes, etc.fonctionnement de systèmes, etc.

Page 3: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Présentation consultable :Présentation consultable :

http://www.ac-bordeaux.fr/http://www.ac-bordeaux.fr/

Pedagogie/Maths/peda/lyc/graphes.htmPedagogie/Maths/peda/lyc/graphes.htm

Page 4: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Merci de votre

attention…

[email protected]

Page 5: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Un ensemble d’arêtesUn ensemble d’arêtes

Notions élémentaires…

Un ensemble de sommetsUn ensemble de sommets

A

F

E

D

CB

G

Un chemin…Un chemin…

Un cycle…Un cycle…

Graphes non orientés

18

115

9

19

7 21

3Graphe Graphe valuévalué

4Sommet de Sommet de

degré 3degré 3

Un arbre couvrant…Un arbre couvrant…

Page 6: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Un ensemble d’arcsUn ensemble d’arcs

Notions élémentaires…

Un ensemble de sommetsUn ensemble de sommets

A

F

E

D

CB

G

Graphes orientés

Un chemin…Un chemin…

Un circuit…Un circuit…Degré entrant 1Degré entrant 1Degré sortant 2Degré sortant 2Degré 3Degré 3

Page 7: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Bref historique…

1736, Euler : 1736, Euler : les ponts de Königsbergles ponts de Königsberg

… … récréations mathématiques …récréations mathématiques …

… … chimie, électricité …chimie, électricité …

1852, De Morgan (Guthrie) : 1852, De Morgan (Guthrie) : quatre couleursquatre couleurs

1946, Kuhn, Ford et Fulkerson, Roy, etc.1946, Kuhn, Ford et Fulkerson, Roy, etc.

… … recherche opérationnelle …recherche opérationnelle …

Depuis 1960, applications… (informatique)Depuis 1960, applications… (informatique)

Page 8: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Un outil pour la modélisation (et la résolution !…) de problèmes

Problème sur des « objets »Problème sur des « objets »

Problème de graphesProblème de graphes

GraphesGraphes

Solution ?…Solution ?…(algorithme)(algorithme)

Page 9: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple : meilleur trajet…

Objet : plan de ville, durée de trajet pour chaque tronçonObjet : plan de ville, durée de trajet pour chaque tronçon

départ

arrivée

62

3

5

2

28

9

5

4

7 4

2

2

12

Problème de plus court chemin dans un graphe valué (algorithmes connus…)

Version « dynamique » (évolution de la valuation)

départ

arrivée

Page 10: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Les ponts de Königsberg…

Il existe un cycle « eulérien » si et seulement si tous les Il existe un cycle « eulérien » si et seulement si tous les sommets sont de degré pair…sommets sont de degré pair…

A

B C

D D

A

B C

Il existe un chemin « eulérien » si et seulement si 0 ou 2 Il existe un chemin « eulérien » si et seulement si 0 ou 2 sommets sont de degré impair…sommets sont de degré impair…

Page 11: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Le problème des quatre couleurs…

Tout graphe planaire est coloriable en utilisant quatre Tout graphe planaire est coloriable en utilisant quatre couleurs au plus… couleurs au plus… [Appel & Haken, 1977][Appel & Haken, 1977]

D

EG

FB

A

C

D

EG

F

B

A

C

Graphe planaire

Page 12: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Quelques domaines d’application…

ChimieChimie SociologieSociologieBio-informatiqueBio-informatiqueRecherche opérationnelleRecherche opérationnelleRéseaux de communicationRéseaux de communicationFonctionnement de systèmesFonctionnement de systèmes

Page 13: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Autres domaines d’application…

Géographie (cartographie), architecture (plans), linguistique Géographie (cartographie), architecture (plans), linguistique (sémantique), etc.(sémantique), etc.

Le WEB (graphe des liens, calcul de pertinence dans les Le WEB (graphe des liens, calcul de pertinence dans les moteurs de recherche, etc.)moteurs de recherche, etc.)

Graphes « petits mondes » (Graphes « petits mondes » (Kevin BaconKevin Bacon)) Les réseaux optiques (producteurs-consommateurs, bande Les réseaux optiques (producteurs-consommateurs, bande

passante, etc.)passante, etc.) Bases de données (dépendances)Bases de données (dépendances) Bases de connaissancesBases de connaissances Techniques de compilationTechniques de compilation Imagerie numérique (scènes, Imagerie numérique (scènes, compressioncompression)) Grammaires de graphes (Grammaires de graphes (aspects dynamiquesaspects dynamiques)) Etc.Etc.

Page 14: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Compression d’images : les quadtrees

Codage d’une image par un arbre…Codage d’une image par un arbre…

ZONE Z

NO

SO SE

NENO SO SENE

Z

Etc.

Feuilles = pixels ou « zones uniformes »Feuilles = pixels ou « zones uniformes »

Page 15: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Modélisation de molécules

méthane CHméthane CH44 butène Cbutène C44HH88

CC

HH

HH

HHHH CC

HH

HH

HHHH CCCCCC

HH

HH

HH HH

Cayley [1875]Cayley [1875] Hydrocarbures saturés CHydrocarbures saturés CnnHH2n+22n+2 : arbres… : arbres… Énumération de molécules, d’isomères, Énumération de molécules, d’isomères,

classifications, etc.classifications, etc.

Graphes (multigraphes) avec contraintes sur les degrés des Graphes (multigraphes) avec contraintes sur les degrés des sommets selon le type de sommet…sommets selon le type de sommet…

Page 16: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Graphes signés (sociogrammes)

Notions de « clans » (employés, nations, Notions de « clans » (employés, nations, politiciens, etc.), algorithmes de découpagepoliticiens, etc.), algorithmes de découpage

+ +

+

+ +

-

- -

+Relation aimer / détester entre employés…Relation aimer / détester entre employés…Configurations équilibrées (A,B) ou non (C)Configurations équilibrées (A,B) ou non (C)

A CB

Page 17: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Pouvoir et influence

Chaque individu a une opinion représentée par un nombre réel Chaque individu a une opinion représentée par un nombre réel (e.g. valeur d’un objet)…(e.g. valeur d’un objet)…

Ces opinions évoluent dans le temps, en fonction des opinions des Ces opinions évoluent dans le temps, en fonction des opinions des personnes ayant de l’influence sur l’individu…personnes ayant de l’influence sur l’individu… L’opinion de l’individu UNTEL se stabilise-t-elle ?L’opinion de l’individu UNTEL se stabilise-t-elle ? Si oui, tend-on vers un consensus ? Vers plusieurs ?Si oui, tend-on vers un consensus ? Vers plusieurs ? Qui a réellement de l’influence sur ces consensus ?Qui a réellement de l’influence sur ces consensus ?

Page 18: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Décodage de chaînes d’ADN

chaîne ADNchaîne ADN

Chaîne d’ADN = séquence de nucléotides Chaîne d’ADN = séquence de nucléotides A,C,G,T : Adénine, Cytosine, Guanine, ThymineA,C,G,T : Adénine, Cytosine, Guanine, Thymine

Séquençage par « hybridation »Séquençage par « hybridation »

« sondes »« sondes »

sondes sondes 

hybridéeshybridées

CACGT

ACGT

CACG

CACT

CACG

CAGT

CATG

Page 19: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

ACT

CTA

TAC

CCT

TCC

CTC

TACT

CTCC

TCCT

CCTA

ACTC

CTAC

Décodage de chaînes d’ADN

Sondes hybridées : TCCT, ACTC, CTAC, Sondes hybridées : TCCT, ACTC, CTAC, TCCT, ACTC, CTCC, TACT, CCTA, CTCCTCCT, ACTC, CTCC, TACT, CCTA, CTCC

TCC CCT

TCCTChemin eulérien ?

ACTCCT ACT CCT

Problème : en général, plusieurssolutions possibles…

Page 20: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Recherche opérationnelle

Méthodes et techniques Méthodes et techniques d’analyse pour d’analyse pour

l’aide à la décisionl’aide à la décision

Page 21: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Recherche opérationnelle

R.O.R.O.

ÉCONOMIE

• Économie d’entreprise• Analyse économique

INFORMATIQUE

• Structures de données• Algorithmes

• Bases de données

MATHÉMATIQUES

• Théorie des systèmes• Méthodes d’optimisation

• Méthodes statistiques

Élaboration du modèle

Traitement du modèle

Théorie des

graphes

Page 22: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

solutions dans Rn« meilleure » solution ?…solutions dans un sous-espace de Rn

Problèmes de recherche opérationnelle

n valeurs à déterminer

ensemble de contraintes

fonction(s) à optimiser

Page 23: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Quelques exemples de problèmes… Problèmes d’ordonnancementProblèmes d’ordonnancement Problèmes de flot maximalProblèmes de flot maximal Problèmes d’affectationProblèmes d’affectation Programmes de transportProgrammes de transport

dépôts de marchandises, clients avec besoins, capacité des canaux dépôts de marchandises, clients avec besoins, capacité des canaux illimitée (transformations d’arbres…)illimitée (transformations d’arbres…)

Problème du voyageur de commerceProblème du voyageur de commercevisite de villes, avec retour… (chemin hamiltonien de coût minimal)visite de villes, avec retour… (chemin hamiltonien de coût minimal)

Problème du « sac à dos »Problème du « sac à dos »n objets, chaque objet ayant une « utilité », sac de capacité m…n objets, chaque objet ayant une « utilité », sac de capacité m…

Etc.Etc.

Page 24: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

En pratique…

Logiciels d’aide à la décisionLogiciels d’aide à la décision

(boîte à outils de résolution…)(boîte à outils de résolution…)

1.1. Modéliser les données du problèmeModéliser les données du problème

2.2. Définir les contraintesDéfinir les contraintes

3.3. Définir la fonction à optimiserDéfinir la fonction à optimiser

4.4. Utiliser les outils de résolutionUtiliser les outils de résolution

5.5. Décider !…Décider !…

Économie, commerce, production, transport, etc.Économie, commerce, production, transport, etc.

Page 25: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Problèmes d’ordonnancement

Sommets = tâches à réaliserSommets = tâches à réaliser

Arcs = relation d’antériorité (valuation : durée de la tâche initiale)Arcs = relation d’antériorité (valuation : durée de la tâche initiale)

33

4

5

23

2

3

Dates au plus tôtDates au plus tôt

0 105

8

3

3

3

Dates au plus tardDates au plus tard

07

10

8

4

3

5

Chemin(s) critique(s)Chemin(s) critique(s)

A C

D

E

F

fin

B

Page 26: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Réseaux de transport

20

15

15

10

10

20

Dépôts de Dépôts de marchandises marchandises

(stock)(stock)

(50)

(30)

(15)

(30)

(10)

(25)

Clients Clients (besoin)(besoin)

« Canaux » « Canaux » (capacité)(capacité)

ports, gares, centrales, ports, gares, centrales, châteaux d’eau, …châteaux d’eau, …

ports, gares, villes, …ports, gares, villes, …bateaux, trains, camions, bateaux, trains, camions, canalisations, …canalisations, …

Page 27: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

50

30

10

3015

25

SS PP

Réseau de transport :Réseau de transport : Un sommet source (S), un sommet puits (P),Un sommet source (S), un sommet puits (P), Pour tout sommet u, il existe un chemin de S vers u et un Pour tout sommet u, il existe un chemin de S vers u et un

chemin de u vers Pchemin de u vers P

Réseaux de transport

20

15

15

10

10

20

(50)

(30)

(15)

(30)

(10)

(25)

Page 28: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

50

30

10

3015

25

Flot dans un réseau de transport

20

15

15

10

10

20

SS PP

Flot :Flot : Pour chaque arc : Pour chaque arc : valeur valeur capacité capacité Pour tout sommet (sauf S et P) : Pour tout sommet (sauf S et P) :

somme des valeurs entrantes = somme des valeurs sortantessomme des valeurs entrantes = somme des valeurs sortantes

15

15

15 30

15

1010

5

5

30

35

10 65

Page 29: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

35

5 1065

50

30

10

3015

25

Flot maximal dans un réseau de transport

20

15

15

10

10

20

SS PP

15

15

15 30

15

1010

5

30

Flot maximal : pas de Flot maximal : pas de « chaîne améliorante »« chaîne améliorante »

15

515

Amélioration : 5

40

10 1570

Souvent des chaînes « plus complexes », avec retours arrières,Souvent des chaînes « plus complexes », avec retours arrières, Possibilité de « coût de transport » sur les arcs…Possibilité de « coût de transport » sur les arcs…

Page 30: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

50

30

10

3015

25

SS PP

Une coupe = ensemble d’arcs dont la suppression « sépare » Une coupe = ensemble d’arcs dont la suppression « sépare » les sommets S et Ples sommets S et P

Coupe minimale20

15

15

10

10

2070

80

85

Coupe minimale = coupe dont le poids (somme des poids des Coupe minimale = coupe dont le poids (somme des poids des arcs la composant) est minimalarcs la composant) est minimalTh : Poids d’une coupe minimale = valeur d’un flot maximalTh : Poids d’une coupe minimale = valeur d’un flot maximal

Page 31: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Problèmes d’affectation

Exemple : affectation de 5 postes (a,b,…) à 5 personnes (A,B,…)Exemple : affectation de 5 postes (a,b,…) à 5 personnes (A,B,…)

Matrice des « préférences »Matrice des « préférences »

a b c d eA 1 2 3 4 5B 1 4 2 5 3C 3 2 1 5 4D 1 2 3 5 4E 2 1 4 3 5

Problème Problème

réaliser l’affectation réaliser l’affectation en minimisant les en minimisant les

insatisfactionsinsatisfactions

Affectation de personnes sur Affectation de personnes sur des machines-outils, de des machines-outils, de

commandes sur des sites de commandes sur des sites de production, etc.production, etc.

Page 32: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Problèmes d’affectation

Matrice des « préférences »Matrice des « préférences »

a b c d eA 1 2 3 4 5

AA aa

etc.etc.

bb

cc

dd

ee

etc.etc.11

11

11

11

11

11

11

Capacités : 1 partout…Capacités : 1 partout…Chaque personne se verra affectée à Chaque personne se verra affectée à un poste, chaque poste à une un poste, chaque poste à une personnepersonne

SS PP

Coût unitaire : matrice…Coût unitaire : matrice…Sauf sortant de S ou entrant en P : coût = 0Sauf sortant de S ou entrant en P : coût = 0

00

55

44

33

22

11

00

Problème de flot Problème de flot maximal de coût maximal de coût

minimal…minimal…

Page 33: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Les réseaux de communication

réseaux téléphoniques réseaux téléphoniques réseaux informatiques réseaux informatiques architectures parallèlesarchitectures parallèles

Page 34: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Modélisation d’un réseau

utilisateurs, machines, etc.utilisateurs, machines, etc.canaux de communicationcanaux de communication

sommetssommetsarcs, arêtesarcs, arêtes

A

F

E

D

CB

Gnon orienténon orienté

14

Capacité des canaux

Chemin de communication

Page 35: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

orientéorienté

Modélisation d’un réseau

utilisateurs, machines, etc.utilisateurs, machines, etc.canaux de communicationcanaux de communication

sommetssommetsarcs, arêtesarcs, arêtes

A

F

E

D

CB

G

Page 36: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Quelques applications…

Mesure de paramètresMesure de paramètres fiabilitéfiabilité chargecharge

Algorithmes de communicationAlgorithmes de communication diffusion de messagediffusion de message routage de messagesroutage de messages

Page 37: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Logiciels...

calcul de différents paramètres (mesures),calcul de différents paramètres (mesures),

comparaison de différentes topologies comparaison de différentes topologies (statique),(statique),

détermination de chemins optimaux détermination de chemins optimaux (dynamique),(dynamique),

aide à la conception de réseaux...aide à la conception de réseaux...

Page 38: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Fiabilité du réseau

panne des canaux de communicationpanne des canaux de communication

A

F

E

D

CB

G

ensemble d’arêtes déconnectant le grapheensemble d’arêtes déconnectant le graphe

Page 39: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Fiabilité du réseau

panne des « sommets relais »panne des « sommets relais »

A

F

E

D

CB

G

ensemble de sommets déconnectant le grapheensemble de sommets déconnectant le graphe

Page 40: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Charge du réseau

Communications A-C, B-D, A-E, F-C, F-E...Communications A-C, B-D, A-E, F-C, F-E...

A

F

E

D

CB

G

Minimiser la charge des canaux Minimiser la charge des canaux

choix de chemins, contraintes de capacité, …choix de chemins, contraintes de capacité, …

Page 41: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Diffusion d’informations

A veut diffuser une information à l’ensemble du A veut diffuser une information à l’ensemble du réseau...réseau...

Algorithme 1 Algorithme 1

Lorsqu’un sommet Lorsqu’un sommet reçoit l’information pour reçoit l’information pour la première fois, il la la première fois, il la diffuse à ses autres diffuse à ses autres voisins...voisins...

Mesures :Mesures : nombre de messages transmis (charge)nombre de messages transmis (charge) nombre d’étapes (temps)nombre d’étapes (temps)

Page 42: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 0messages : 0

A

F

E

D

CB

G

étapes : 0étapes : 0

Page 43: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 3messages : 3

A

F

E

D

CB

G

étapes : 1étapes : 1

Page 44: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 10messages : 10

A

F

E

D

CB

G

étapes : 2étapes : 2

Page 45: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 13messages : 13

A

F

E

D

CB

G

étapes : 3étapes : 3

C a reçu le C a reçu le message de message de B en premierB en premier

Page 46: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 14messages : 14

A

F

E

D

CB

G

étapes : 4étapes : 4

D a reçu le D a reçu le message de message de C en premierC en premier

Page 47: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Diffusion d’informations

A veut diffuser une information à A veut diffuser une information à l’ensemble du réseau...l’ensemble du réseau...

Algorithme 2 Algorithme 2

Idem algorithme 1, Idem algorithme 1, mais en utilisant les mais en utilisant les arêtes d’un arbre arêtes d’un arbre recouvrant...recouvrant...

Mesures :Mesures : nombre de messages transmis (charge)nombre de messages transmis (charge) nombre d’étapes (temps)nombre d’étapes (temps)

Page 48: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 0messages : 0

A

F

E

D

CB

G

étapes : 0étapes : 0

Page 49: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 3messages : 3

A

F

E

D

CB

G

étapes : 1étapes : 1

Page 50: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 5messages : 5

A

F

E

D

CB

G

étapes : 2étapes : 2

Page 51: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Exemple...

messages : 6messages : 6

A

F

E

D

CB

G

étapes : 3étapes : 3

optimal (6 sommets optimal (6 sommets à informer)à informer) profondeur profondeur

de l’arbrede l’arbre

Algorithme 1 :Algorithme 1 : 14 messages14 messages 4 étapes4 étapes

Page 52: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Routage dans les réseaux

A communique avec D via un chemin (route)A communique avec D via un chemin (route)

A

F

E

D

CB

G

Un routage est un ensemble de N(N-1) routes…Un routage est un ensemble de N(N-1) routes…

Page 53: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Routage dans les réseaux

Algorithmes pour calculer un routage :Algorithmes pour calculer un routage : minimisant la charge des sommets,minimisant la charge des sommets, minimisant la charge des arêtes,minimisant la charge des arêtes, « raisonnable » en longueur de « raisonnable » en longueur de

chemins (dilatation).chemins (dilatation).

réseaux classiques, machines parallèles réseaux classiques, machines parallèles (communications entre processeurs), réseaux (communications entre processeurs), réseaux

optiques, etc.optiques, etc.

Page 54: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Mise en œuvre du routage

Algorithmes de routageAlgorithmes de routage

message pour Al’entête du message contient l’identité du

destinataire

?

?

?

Page 55: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Mise en œuvre du routage

Solution 1 : tables de routageSolution 1 : tables de routage

Chaque sommet possède sa

propre table de routage…

message pour… sortieA 1B 3C 1

etc. etc.

Coûteux en place mémoire…Coûteux en place mémoire…

Page 56: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Mise en œuvre du routage

Solution 2 : routage par intervallesSolution 2 : routage par intervalles

Chaque sommet possède sa

propre table de routage…

message pour… sortie[1,8] 1[9,26] 3[27,32] 2

1.1. Trouver une « bonne » numérotation des sommets,Trouver une « bonne » numérotation des sommets,

2.2. Trouver un « bon » routage (dilatation).Trouver un « bon » routage (dilatation).

Page 57: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Hiérarchisation des sommets

Graphe découpé en régionsGraphe découpé en régions Chaque région possède une « capitale »Chaque région possède une « capitale » Communications via les capitalesCommunications via les capitales

Page 58: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Hiérarchisation des sommets

Graphe découpé en régionsGraphe découpé en régions Chaque région possède une « capitale »Chaque région possède une « capitale » Communications via les capitalesCommunications via les capitales

Table de routage CAPITALETable de routage CAPITALEsa région + réseau des capitalessa région + réseau des capitales

Table de routage VILLETable de routage VILLEsa régionsa région

Possibilité de hiérarchies à plusieurs niveaux…Possibilité de hiérarchies à plusieurs niveaux…

Page 59: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Routage dynamique (adaptatif)

Les « paires communicantes » évoluent dans Les « paires communicantes » évoluent dans le temps…le temps…

Le réseau évolue…Le réseau évolue…

Machines parallèles,Machines parallèles,

Téléphonie mobile…Téléphonie mobile…Contraintes sur le nombre de chemins Contraintes sur le nombre de chemins empruntant une arête (fréquences)empruntant une arête (fréquences)

Page 60: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Fonctionnement de systèmes

modélisation par modélisation par automatesautomates

Page 61: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Modélisation par un automateModélisation par un automate

Événement { action }

État 1 État 2

Les événements déclenchent des actions (réactions) du système selon l’état dans lequel celui-ci se trouve…

Automate déterministe : pour chaque état, au plus une transition par événement…

Page 62: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Fermeture { fermer }

Exemple 1 : une porte…Exemple 1 : une porte…

Ouverte Fermée

Ouverture { ouvrir }

Page 63: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

On { allumer }

Exemple 2 : une ampoule…Exemple 2 : une ampoule…

Éteinte Allumée

Off { éteindre }

Page 64: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Produit d’automatesProduit d’automates

Exemple 1 : une pièce d’habitation…Exemple 1 : une pièce d’habitation…

FermetureFerméeallumée

Ouverture

Ouverteallumée

Fermeture Ferméeéteinte

Ouverture

Ouverteéteinte

Off On

Off On

Ouverture+ Off

Ouverture+ On

Fermeture+ On

Fermeture+ Off

Page 65: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Produit d’automatesProduit d’automates

Exemple 2 : un réfrigérateur…Exemple 2 : un réfrigérateur…

FermetureFerméeallumée

Ouverture

Ouverteallumée

Fermeture Ferméeéteinte

Ouverture

Ouverteéteinte

Off On

Off On

Ouverture+ Off

Ouverture+ On

Fermeture+ On

Fermeture+ Off

Page 66: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Produit d’automates avec contraintesProduit d’automates avec contraintes

Ouverteallumée

Fermeture Ferméeéteinte

Ouverture

Ouverteéteinte

Off On

Ouverture+ On Fermeture

+ Off

Fermée

Ouverte

Ouverte

-

Fermeture

Fermeture

INTERDIT

Éteinte

Allumée

Éteinte

On

-

On

Ampoule Porte

Page 67: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Produit d’automates avec contraintesProduit d’automates avec contraintes

Ouverteallumée

Ferméeéteinte

Ouverture+ On Fermeture

+ Off

En « couplant » porte et En « couplant » porte et interrupteur…interrupteur…

On impose des concurrences On impose des concurrences d’événements (pas toujours d’événements (pas toujours possible…)possible…)

Page 68: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

En pratique...En pratique...

Modéliser le système par un automate ou Modéliser le système par un automate ou plusieurs automates « synchronisés ».plusieurs automates « synchronisés ».

notion de sous-système…notion de sous-système…explosion combinatoire, calculs « à la volée »…explosion combinatoire, calculs « à la volée »…

Vérifier certaines propriétés de l’automate.Vérifier certaines propriétés de l’automate.

états inaccessibles, états « vivaces », interblocages, états inaccessibles, états « vivaces », interblocages, etc. (problèmes de chemins)etc. (problèmes de chemins)

Rectifier en conséquence... et valider !Rectifier en conséquence... et valider !

Page 69: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Quelques applications...Quelques applications...

Conception de systèmes (respect des Conception de systèmes (respect des spécifications),spécifications),

Outils d’aide à la vérification de systèmes Outils d’aide à la vérification de systèmes (sûreté de fonctionnement),(sûreté de fonctionnement),

Outils de vérification de logiciels,Outils de vérification de logiciels, etc.etc.

aéronautique, aérospatiale, transport aéronautique, aérospatiale, transport ferroviaire, nucléaire, réseaux téléphoniques, ferroviaire, nucléaire, réseaux téléphoniques,

réseaux informatiques, électronique, ...réseaux informatiques, électronique, ...

Page 70: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Techniques de compilationTechniques de compilation

Représentation d’un programme par un arbreReprésentation d’un programme par un arbre

expression arithmétique

3 * a + 2 * (b – 4)

codage par un arbre

+

* *

3 a 2 -

b 4

Page 71: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Techniques de compilationTechniques de compilation

Représentation d’un programme par un arbreReprésentation d’un programme par un arbre

instruction

si (a > 5) alors b b + 1

codage par un arbre

si

>

a 5 b +

b 1

Programme graphe

(sous-arbres communs)

Page 72: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Techniques de compilationTechniques de compilation

Principe général :Principe général :

Analyse du texte source (programme)Analyse du texte source (programme)erreurs éventuelleserreurs éventuellescodage du source (arbre ou graphe)codage du source (arbre ou graphe)

Traduction du codage en un autre langage Traduction du codage en un autre langage (langage machine, …)(langage machine, …)

Langage interprété :Langage interprété : exécution du codage par exécution du codage par l’interpréteur…l’interpréteur…

Page 73: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Grammaires de graphes...Grammaires de graphes...

Règle de remplacementRègle de remplacement

Réécriture d’un grapheRéécriture d’un graphe

???

Page 74: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Construction d’un arbre couvrantConstruction d’un arbre couvrant

Règle de remplacementRègle de remplacement

Réécriture d’un grapheRéécriture d’un graphe

A

F

E

D

CB

G

Plusieurs solutions…mais toujours un arbrecouvrant !…

Page 75: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Construction d’arbresConstruction d’arbres

Règle de remplacementRègle de remplacement

Réécriture d’un grapheRéécriture d’un graphe

Etc.

Page 76: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Le graphe de Kevin BaconLe graphe de Kevin Bacon

Sommets = acteursSommets = acteurs

Arêtes entre acteurs ayant joué dans un Arêtes entre acteurs ayant joué dans un même film…même film…

Propriété :Propriété :

Tout acteur est à Tout acteur est à distance au distance au

plus 6 de Kevin plus 6 de Kevin Bacon !…Bacon !…

Page 77: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Le graphe de Kevin Bacon (2)Le graphe de Kevin Bacon (2)

Louis de Funes has a Bacon number of 2. Louis de Funes has a Bacon number of 2.

Louis de Funes was in Aventures de Rabbi Jacob, Les Louis de Funes was in Aventures de Rabbi Jacob, Les (1973) with Janet Brandt (1973) with Janet Brandt

Janet Brandt was in Queens Logic (1991) with Kevin Janet Brandt was in Queens Logic (1991) with Kevin Bacon Bacon

Site Web : Site Web :

http://www.fast-rewind.com/bacon.htmhttp://www.fast-rewind.com/bacon.htm

The Oracle of Bacon at VirginiaThe Oracle of Bacon at Virginia

Page 78: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Le graphe de Kevin Bacon (3)Le graphe de Kevin Bacon (3)

Catherine Deneuve has a Bacon number of 2. Catherine Deneuve has a Bacon number of 2.

Catherine Deneuve was in Anima persa (1977) with Catherine Deneuve was in Anima persa (1977) with Vittorio Gassman Vittorio Gassman

Vittorio Gassman was in Sleepers (1996) with Kevin Vittorio Gassman was in Sleepers (1996) with Kevin Bacon Bacon

Site Web : Site Web :

http://www.fast-rewind.com/bacon.htmhttp://www.fast-rewind.com/bacon.htm

The Oracle of Bacon at VirginiaThe Oracle of Bacon at Virginia

Page 79: Éric SopenaAvril 2005 Théorie des graphes Quelques exemples dapplication…

Éric Sopena Avril 2005

Le graphe de Kevin Bacon (4)Le graphe de Kevin Bacon (4)

Audrey Tautou has a Bacon number of 3. Audrey Tautou has a Bacon number of 3.

Audrey Tautou was in Venus beaute (institut) (1999) Audrey Tautou was in Venus beaute (institut) (1999) with Bulle Ogier with Bulle Ogier

Bulle Ogier was in Merci Docteur Rey (2002) with Eli Bulle Ogier was in Merci Docteur Rey (2002) with Eli Wallach Wallach

Eli Wallach was in Mystic River (2003) with Kevin Bacon Eli Wallach was in Mystic River (2003) with Kevin Bacon

Site Web : Site Web :

http://www.fast-rewind.com/bacon.htmhttp://www.fast-rewind.com/bacon.htm

The Oracle of Bacon at VirginiaThe Oracle of Bacon at Virginia