Graph Es [PDF]

Zitiervorschau

Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

1/16

Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI École Nationale de Commerce et de Gestion - Oujda Département de commerce Recherche opérationnelle

22 décembre 2020

Sommaire Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

1

Dénitions et représentations

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

2/16

2

3

Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

3/16

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

3/16

Un graphe est un ensemble ni de points appelés sommets qui sont reliés par des èches appelées arcs.

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

3/16

Un graphe est un ensemble ni de points appelés sommets qui sont reliés par des èches appelées arcs. Exemple

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

3/16

Un graphe est un ensemble ni de points appelés sommets qui sont reliés par des èches appelées arcs. Exemple

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

Un graphe est un ensemble ni de points appelés sommets qui sont reliés par des èches appelées arcs. Exemple

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

• • •

3/16

Dans notre exemple, l'arc (AB) a pour origine le point A et pour extrémité le point B. On dit que B est un suivant de A ou successeur de A. On dit que A est un précédent de B ou prédécesseur de B.

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

4/16

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

•

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

4/16

•

On appelle chemin une succession d'arcs tels que l'extrémité de chacun coïncide avec l'origine de l'arc suivant. On appelle circuit, un chemin tel que l'origine du premier arc coïncide avec l'extrémité du dernier arc.

Dénitions et représentations Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

•

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

4/16

•

On appelle chemin une succession d'arcs tels que l'extrémité de chacun coïncide avec l'origine de l'arc suivant. On appelle circuit, un chemin tel que l'origine du premier arc coïncide avec l'extrémité du dernier arc.

Exemple • (AB), (BC), (CE) est un chemin joignant A à E. on le note tout simplement par ABCE. • ABDEFA est un circuit.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

5/16

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

5/16

On peut représenter un graphe par : • Le dessin présenté ci-dessous, appelé : représentation sagittale • L'ensemble de tous les arcs qui le composent. G = {AB, BC , BD, CE , DE , EF , FD, FA}

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

5/16

On peut représenter un graphe par : • Le dessin présenté ci-dessous, appelé : représentation sagittale • L'ensemble de tous les arcs qui le composent. G = {AB, BC , BD, CE , DE , EF , FD, FA} •

Indiquer dans un tableau tous les suivants de chaque sommet. On obtient alors le dictionnaire des suivants.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

5/16

On peut représenter un graphe par : • Le dessin présenté ci-dessous, appelé : représentation sagittale • L'ensemble de tous les arcs qui le composent. G = {AB, BC , BD, CE , DE , EF , FD, FA} • •

Indiquer dans un tableau tous les suivants de chaque sommet. On obtient alors le dictionnaire des suivants. Indiquer dans un tableau tous les précédents de chaque sommet. On obtient alors le dictionnaire des précédents.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

6/16

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

6/16

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes :

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : •

Déterminer le dictionnaire des précédents du graphe G.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Déterminer le dictionnaire des précédents du graphe G. Relever tous les sommets sans précédents : ils ont pour niveau 0.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Déterminer le dictionnaire des précédents du graphe G. Relever tous les sommets sans précédents : ils ont pour niveau 0.

•

Considérer le dictionnaire des précédents obtenu à partir de celui de G en supprimant dans les 2 colonnes, tous les sommets de niveau 0. On

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Déterminer le dictionnaire des précédents du graphe G. Relever tous les sommets sans précédents : ils ont pour niveau 0.

•

Considérer le dictionnaire des précédents obtenu à partir de celui de G en supprimant dans les 2 colonnes, tous les sommets de niveau 0. On

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Déterminer le dictionnaire des précédents du graphe G. Relever tous les sommets sans précédents : ils ont pour niveau 0.

•

Considérer le dictionnaire des précédents obtenu à partir de celui de G en supprimant dans les 2 colonnes, tous les sommets de niveau 0. On

•

obtient le dictionnaire d'un sous graphe G1.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Déterminer le dictionnaire des précédents du graphe G. Relever tous les sommets sans précédents : ils ont pour niveau 0.

•

Considérer le dictionnaire des précédents obtenu à partir de celui de G en supprimant dans les 2 colonnes, tous les sommets de niveau 0. On

• •

obtient le dictionnaire d'un sous graphe G1. Relever dans G1 tous les sommets sans précédents : ils ont pour niveau 1.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

7/16

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Déterminer le dictionnaire des précédents du graphe G. Relever tous les sommets sans précédents : ils ont pour niveau 0.

•

Considérer le dictionnaire des précédents obtenu à partir de celui de G en supprimant dans les 2 colonnes, tous les sommets de niveau 0. On

• •

obtient le dictionnaire d'un sous graphe G1. Relever dans G1 tous les sommets sans précédents : ils ont pour niveau 1.

•

Supprimer dans le dictionnaire des précédents de G1 tous les sommets de niveau 1, etc ...

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

Niveau ou rang d'un sommet dans un graphe G sans circuit • Pour obtenir une représentation sagittale plus lisible, on détermine d'abord le niveau de chaque sommet de G. • Pour déterminer les niveaux, on suit les étapes suivantes : • •

Sommaire Dénitions et représentations

Relever tous les sommets sans précédents : ils ont pour niveau 0.

•

Diérentes représentations d'un graphe G

Considérer le dictionnaire des précédents obtenu à partir de celui de G en supprimant dans les 2 colonnes, tous les sommets de niveau 0. On

• •

Chemin le plus long ; chemin le plus court dans un graphe sans circuit

obtient le dictionnaire d'un sous graphe G1. Relever dans G1 tous les sommets sans précédents : ils ont pour niveau 1.

•

Supprimer dans le dictionnaire des précédents de G1 tous les sommets de niveau 1, etc ...

•

7/16

Déterminer le dictionnaire des précédents du graphe G.

Ce processus a une n car le graphe G a un nombre ni de sommets et il n'a pas de circuit.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

8/16

Exercice Ordonnancer par niveaux le graphe G suivant puis en donner une représentation sagittale

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

Exercice Ordonnancer par niveaux le graphe G suivant puis en donner une représentation sagittale

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

8/16

• •

Niveau 0 : B, M Niveau 1 : D, F, P, Q

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

Exercice Ordonnancer par niveaux le graphe G suivant puis en donner une représentation sagittale

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

8/16

• • •

Niveau 0 : B, M Niveau 1 : D, F, P, Q Niveau2 : G, H

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

Exercice Ordonnancer par niveaux le graphe G suivant puis en donner une représentation sagittale

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

8/16

• • • •

Niveau 0 : B, M Niveau 1 : D, F, P, Q Niveau2 : G, H Niveau 3 : J

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI

Exercice Ordonnancer par niveaux le graphe G suivant puis en donner une représentation sagittale

Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

8/16

• • • • •

Niveau 0 : B, M Niveau 1 : D, F, P, Q Niveau2 : G, H Niveau 3 : J Niveau 4 : R

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

9/16

Remarques • Pour tracer le graphe G, on place les sommets de gauche à droite et par niveaux croissants. Puis indiquer les arcs du graphe en utilisant le dictionnaire des précédents.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

9/16

Remarques • Pour tracer le graphe G, on place les sommets de gauche à droite et par niveaux croissants. Puis indiquer les arcs du graphe en utilisant le dictionnaire des précédents. • On pourra vérier que le niveau d'un sommet est égal au nombre maximum d'arcs que l'on peut trouver sur un chemin joignant un sommet de niveau 0 au sommet considéré.

Diérentes représentations d'un graphe G Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

10/16

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

11/16

Dénitions Soit G un graphe sans circuit. • On suppose que chaque arc est aecté d'un nombre, appelé : longueur de cet arc. Dans ce cas G est dit graphe valué.

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

11/16

Dénitions Soit G un graphe sans circuit. • On suppose que chaque arc est aecté d'un nombre, appelé : longueur de cet arc. Dans ce cas G est dit graphe valué. • La longueur d'un chemin est la somme des longueurs des arcs qui le composent.

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

11/16

Dénitions Soit G un graphe sans circuit. • On suppose que chaque arc est aecté d'un nombre, appelé : longueur de cet arc. Dans ce cas G est dit graphe valué. • La longueur d'un chemin est la somme des longueurs des arcs qui le composent. • Si le graphe n'est pas valué, la longueur d'un chemin est égale au nombre d'arcs qui le composent.

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

12/16

Chemin le plus long dans un graphe sans circuit Cherchons le chemin le plus long dans le graphe suivant :

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

13/16

La méthode consiste à : • Déterminer de proche en proche pour chaque sommet X, en partant de M, la longueur du chemin le plus long entre les sommets M et X.

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

13/16

La méthode consiste à : • Déterminer de proche en proche pour chaque sommet X, en partant de M, la longueur du chemin le plus long entre les sommets M et X. • On note près du sommet X la longueur obtenue.

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

13/16

La méthode consiste à : • Déterminer de proche en proche pour chaque sommet X, en partant de M, la longueur du chemin le plus long entre les sommets M et X. • On note près du sommet X la longueur obtenue. • On indique en double trait (= ) l'arc permettant d'obtenir cette longueur.

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

13/16

La méthode consiste à : • Déterminer de proche en proche pour chaque sommet X, en partant de M, la longueur du chemin le plus long entre les sommets M et X. • On note près du sommet X la longueur obtenue. • On indique en double trait (= ) l'arc permettant d'obtenir cette longueur. • Ceci permettra à la n de trouver facilement le (ou les) chemin(s) le(s) plus long(s).

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

14/16

le chemin MPGR est donc le chemin le plus long dans le graphe (on ne suit que les arcs en double trait)

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

15/16

Chemin le plus court dans un graphe sans circuit On suit la même démarche en considérant cette fois la longueur du chemin le plus court entre le sommet M et les autres sommets X

Chemin le plus long ; chemin le plus court dans un graphe sans circuit Chapitre 4: Notions de base en théorie des graphes

Dans le même exemple on a :

Abdelaziz CHETOUANI Sommaire Dénitions et représentations Diérentes représentations d'un graphe G Chemin le plus long ; chemin le plus court dans un graphe sans circuit

16/16

Les chemins MPR et MDHJR sont donc les chemins les plus courts dans le graphe