Cours de Recherche Opérationnelle

 

Année 2002 - 2003

 

THEORIE DES GRAPHES

 

 

 

I. Définition & vocabulaire 2

1. Définition_ 2

2. Vocabulaire_ 2

3. Exemples 3

II. Exercices 4

1. Graphe 1_ 4

2. Graphe 2_ 5

III. Les graphes réseaux_ 7

1. Définitions 7

2. Exemples 8

a. Exemple 1_ 8

b. Exemple 2_ 9

c. Exemple 3_ 10

d. Exemple 4_ 13

 


 

I. Définition & vocabulaire

 

1. Définition

 

 

Un graphe est définit comme un ensemble de sommets (ou objets) reliés entre eux.

 

Extrémité = Variable                                       Terminaison = valeur

 

E

 

B

 
            i (A) = {B, C}

            i (B) = {E, D}

A

 
            i (C) = {E}

            i (D) = {C}

D

 

C

 
            i (E) = Æ

 

Il existe l’application interne :

            i (A) = Æ

            i (B) = {A}

            …..

 

Mathématiquement un graphe G est complément défini :

-         si on connaît l’ensemble des sommes X = {A, B, C, D, E}

-         si on connaît l’application i

donc G = {X, i}

 

U = { (A,B), (A,C), (B,E), (C,E), (B,D), (D,C) } = ensemble des arcs

 

 

2. Vocabulaire

 

 

B

 

A

 

C

 
            -     arcs : A à B         A pas d’arcs B A Þ B

                        Notation (A, B) ou A à B ou AB

 


-         sommet adjacents : deux sommets reliées par un arc

 

-         chemin Hamiltonien : un chemin qui passe une fois et une seule fois par tous les sommets (et qui comprend l’ensemble des sommets)

 

-         chemin simple : un chemin qui passe qu’une et une seule fois sur un arc

 

-         chemin élémentaire : un chemin qui passe qu’une et une seule fois par les sommets qu’il utilise

 

-         circuit : un chemin qui se referme sur lui-même

(A, B, D) est un circuit

 
 

 

 

 

 


-         arête : arc non orienté A – B

 

-         chaîne : succession d’arêtes successives.

 

 

circuit hamiltonien

 

chemin

 

chaîne

 

circuit

 

cycle

 
 

 

 

 

 

 

 

 


-         matrice associées : un graphe peut être défini par sa matrice associée.

2 formes :

      Ø forme booléenne

      Ø forme explicite (matrice ou arcs)

 

3. Exemples

 

 

 

 

 

 


Forme Matrice Booléenne :

 

ä

A

B

C

D

A

0

1

0

0

B

0

0

1

0

C

0

0

0

1

D

0

1

0

0

 

Forme Matrice en arcs :

 

ä

A

B

C

D

A

 

AB

 

 

B

 

 

BC

 

C

 

 

 

CD

D

 

DB

 

 

 

 

 

II. Exercices

1. Graphe 1

 

 

GRAPHE 1

 

A

 

C

 
 

 

 

 

D

 
 

 

 

 

 

 

 


1.      {D, A, E, A, E, A} est-il un chemin simple ?

non car on passe plusieurs fois par le même chemin

 

 

2.      {D, A, E, A} est-il un chemin élémentaire ?

non car il passe deux fois par le sommet A

 

 

3.      {D, A, E} est-il un chemin élémentaire ?

oui

 

 

4.      Donner la matrice aux arcs

ä

A

B

C

D

E

A

 

AB

AC

 

AE

B

 

BB

BC

 

 

C

 

 

 

CD

 

D

DA

 

 

 

DE

E

EA

 

EC

 

 

 

 

5.      Donner la matrice booléenne

ä

A

B

C

D

E

A

0

1

1

0

1

B

0

1

1

0

0

C

0

0

0

1

0

D

1

0

0

0

1

E

1

0

1

0

0

 

 


 

2. Graphe 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 



Dictionnaire des précédents : (graphe 2)

 

X

Prec(X)

A

 

B

A,C,F

C

D

D

E

E

F,B

F

B

 

Dictionnaire des suivants : (graphe 2)

 

X

Prec(X)

A

B

B

E,F

C

B

D

C

E

D

F

B,E

 


 

Chemin de longueur B – taille 1 : (graphe 1)

 

ä

A

B

C

D

E

A

 
A

 

AB

AC

 

AE

B

 

BB

BC

 

 

C

 

 

 

CD

 

D

DA

 

 

 

DE

E

EA

 

EC

 

 

 

Chemin de taille 2 – 2 arcs : (graphe 1)

 

ä

A

B

C

D

E

A2

 
A

AEA

ABB

ABC

AEC

ACD

 

B

 

BBB

BBC

BCD

 

C

CDA

 

 

 

CDE

D

DEA

DAB

DAC

DEC

 

DAE

E

 

EAB

EAC

ECD

EAE

 

 

Chemin de taille 3 : (graphe 1)

 

ä

A

B

C

D

E

A3

 
A

ACDA

AEAB

ABBB

AEAC

ABBC

ABCD

AECD

ACDE

B

 

BBBB

 

 

BCDE

C

 

 

 

 

 

D

 

 

 

 

 

E

 

 

 

 

 

 

 

 

Chemin de taille 4 : (graphe 1)

 

ä

A

B

C

D

E

A4

 
A

ABCDA

AECDA

AEAEA

ACDEA

ACDAB

AEABB

ABBBB

ACDAC

AEABC

ABBBC

AEAEC

ACDEC

AEACD

ABBCD

ACDAE

ABCDE

AECDE

B

BBCDA

BCDEA

BCDAB

BBBBB

BCDAC

BBBBC

BCDEC

BBBCD

BCDAE

BBCDE

C

CDAEA

CDEAB

CDABB

CDEAC

CDABC

CDAEC

CDACD

CDECD

CDACE

D

DACDA

DECDA

DEAEA

DAEAB

DEABB

DAEBB

DAEAC

DEABC

DAEBC

DEAEC

DEACD

DABCD

DAECD

DAEAE

DACDE

DECDE

E

EACDA

ECDEA

ECDAB

EAEAB

EABBB

ECDAC

EAEAC

ECDEC

EABCD

EAECD

ECDAE

EAEAE

EACDE

 

 

Cette méthode est lourde.

Si on recherche les chemins Hamiltonien, il est préférable :

1.      d’enlever les doublons

2.      d’enlever les circuits

 

Les deux schémas représentent le même graphe : sur les deux circuits, on voit qu’il ne peut pas y avoir de chemin hamiltonien.

 

 


 

III. Les graphes réseaux

 

1. Définitions

 

Graphe réseau :

Entrée

 
 

 

 

 

 

 

 


C

 
Lien de précédence :

 

 

 

 

 

 

 


Circuit :

 

 

 

 

 


15

 

10

 
Graphe valués :

 

 

 

 


Arborescence :

 

 

ä

 

 

ä

æ

ä

ä

 

 

æ

æ

ä

 

ä

 

æ

ä

æ

 

 

æ

 

 

 

Programmation dynamique certain :

Toute partie d’un chemin optimal (par référence à un critère d’optimisation est elle-même optimale)


 

2. Exemples

 

 

a. Exemple 1

 

 

On doit construire une route entre A et K en passent par des villes intermédiaires selon les phases de constructions.

Les arcs sont valuées par le coût total correspondant à ces arcs.

Choisir le meilleur tracé possible pour maintenir les coûts totaux.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


1

2

3

4

AB = 8

BE = 3

EI = 4

IK = 5

AC = 5

BG = 4

EJ = 5

JK = 7

AD = 7

CE = 5

FI = 4

 

 

CF = 4

FJ = 4

 

 

CG = 6

GI = 3

 

 

CH = 4

GJ = 2

 

 

DE = 3

HJ = 4

 

 

DG = 2

 

 

 

DH = 3

 

 

 


 

b. Exemple 2

 

LE PLUS COURT = ABDCEF (10)

LE PLUS LONG = ADF (13)

 
 

 

 

 

 

 

 

 

 

 

 


AB = 3

BE = 6

DF = 7

AD = 6

CE = 1

DC = 2

AC = 8

EF = 2

BD = 2

 

 

 

Algorithme de FORD : pour recherche la valeur maximale

 

 

Etape 1 : numéroter les sommets d’une façon quelconque sauf le sommet initiale X0 et le sommet final Xn-1 (n = nombre de sommet)

 

 

Etape 2 : afficher des valeurs li à chacun des sommets li > 0 (1 £ l £ n)

 

 

Etape 3 : pour tout sommet Xj calculer eji = lj - li

si eji < valuation arc (Xi, Xj) alors li est remplacé par li = li + m(xi, xj)

sinon li est inchangé.

 

 

            Etape 4 : on continue les itérations (étape 3) jusqu’à ce qu’on puisse plus augmenter.

 

 


 

 

c. Exemple 3

 

            Trouver le chemin le plus long entre E et S

 

 

 

 

 

 

 

 

 

 

 


EA = 12

AG = 24

GS = 21

EC = 14

AB = 13

FG = 5

 

BG = 3

FS = 2

 

BF = 7

FD = 4

 

BD = 1

DS = 26

 

CB = 10

 

 

CD = 16

 

 

 

1° étape :

 

 

 

 

 

 

 

 

 

 

 


3° étape :

X0 Þ (X0, X1) et (X0, X3) sont les arcs qui partent de X0

(X0, X1) : e10 = l1 - l0 = 0 – 0 = 0

g (X0, X1) = 12

e10 < g (X0, X1) ? oui alors l1 = l0 + g (X0, X1) = 0 + 12 = 12

l1 = 12

 

(X0, X3) : e30 = l3 - l0 = 0 – 0 = 0

g (X0, X3) = 14

e30 < g (X0, X3) ? oui alors l3 = l0 + g (X0, X3) = 0 + 14 = 14

l3 = 14

 

X1 Þ (X1, X6) et (X1, X2) sont les arcs qui partent de X1

(X1, X6) : e61 = l6 - l1 = 0 – 12 = -12

g (X1, X6) = 24

e61 < g (X1, X6) ? oui alors l6 = l1 + g (X1, X6) = 12 + 24 = 36

l6 = 36

 

(X1, X2) : e21 = l2 - l1 = 0 – 12 = -12

g (X1, X2) = 13

e21 < g (X1, X2) ? oui alors l2 = l1 + g (X1, X2) = 12 + 13 = 25

l2 = 25

 

X2 Þ (X2, X6) et (X2, X5) et (X2, X4) sont les arcs qui partent de X2

(X2, X6) : e62 = l6 - l2 = 36 – 25 = 11

g (X2, X6) = 3

e62 < g (X2, X6) ? non

 

(X2, X5) : e52 = l5 - l2 = 0 – 25 = -25

g (X2, X5) = 7

e52 < g (X2, X5) ? oui alors l5 = l2 + g (X2, X5) = 25 + 7 = 32

l5 = 32

 

(X2, X4) : e42 = l4 - l2 = 0 – 25 = -25

g (X2, X4) = 1

e42 < g (X2, X4) ? oui alors l4 = l2 + g (X2, X4) = 25 + 1 = 26

l4 = 26

 

X3 Þ (X3, X2) et (X3, X4) sont les arcs qui partent de X3

(X3, X2) : e23 = l2 - l3 = 25 – 14 = 11

g (X3, X2) = 10

e23 < g (X3, X2) ? non

 

(X3, X4) : e43 = l4 - l3 = 26 – 14 = 12

g (X3, X4) = 16

e43 < g (X3, X4) ? oui alors l4 = l3 + g (X3, X4) = 14 + 16 = 30

l4 = 30

 

X4 Þ (X4, X7) est l’arc qui part de X4

(X4, X7) : e74 = l7 - l4 = 0 – 30 = -30

g (X4, X7) = 26

e74 < g (X4, X7) ? oui alors l7 = l4 + g (X4, X7) = 30 + 26 = 56

l7 = 56

 

X5 Þ (X5, X6) et (X5, X7) et (X5, X6) sont les arcs qui partent de X5

(X5, X6) : e65 = l6 - l5 = 36 – 32 = 4

g (X5, X6) = 5

e65 < g (X5, X6) ? oui alors l6 = l5 + g (X5, X6) = 32 + 5 = 37

l6 = 37

 

(X5, X7) : e75 = l7 - l5 = 56 – 32 = 24

g (X5, X7) = 2

e75 < g (X5, X7) ? non

 

(X5, X4) : e45 = l4 - l5 = 26 – 30 = -2

g (X5, X4) = 4

e45 < g (X5, X4) ? oui alors l4 = l5 + g (X5, X4) = 32 + 4 = 36

l4 = 36

 

X6 Þ (X6, X7) est l’arc qui part de X6

(X6, X7) : e76 = l7 - l6 = 56 – 37 = 19

g (X6, X7) = 21

e76 < g (X6, X7) ? oui alors l7 = l6 + g (X6, X7) = 37 + 21 = 58

l7 = 58

 

 

X7 Þ (X4, X7), (X5, X7), (X6, X7) sont les arcs qui arrivent de X7

(X4, X7) : e74 = l7 - l4 = 58 - 36 = 22

g (X4, X7) = 2

e74 < g (X4, X7) ? oui alors l7 = l4 + g (X4, X7) = 36 + 26 = 62

l7 = 62

 

(X5, X7) : e75 = l7 - l5 = 62 - 32 = 30

g (X5, X7) = 2

e75 < g (X5, X7) ? non

 

(X6, X7) : e76 = l7 - l6 = 62 - 37 = 25

g (X6, X7) = 21

e76 < g (X6, X7) ? non

 

La longueur maximale est de 62.

 

 

 


 

d. Exemple 4

 

 

 

 

 

 

 

 

 

 


X0X1 = 3

X1X3 = 2

X3X2 = 2

X0X3 = 6

X1X4 = 6

X3X5 = 7

X0X2 = 8

X2X4 = 1

X4X5 = 2

 

 

Le plus petit chemin :

            X1 (X0, 3)

            X2 (X0, 8) (X3, 5+2=7)

            X3 (X0, 6) (X1, 3+2=5)

            X4 (X1, 3+6=9) (X2, 7+1=8)

            X5 (X3, 5+7=12) (X4, 8+2=10)

 

Le plus petit chemin est X0, X1, X3, X2, X4, X5 de longueur minimal 33

 
X5 (X4, 10)

X4 (X2, 8)

X2 (X3, 7)

X3 (X1, 5)

X1 (X0, 3)

X0

 

 

Le plus grand chemin :

            X1 (X0, 3)

            X2 (X0, 8) (X3, 6+2=8)

            X3 (X0, 6) (X1, 3+2=5)

            X4 (X1, 3+6=9) (X2, 8+1=9)

            X5 (X3, 6+7=13) (X4, 9+2=11)

 

Le plus grand chemin est X5, X3 de longueur minimal 19

 
X5 (X3, 13)

X3 (X0, 6)

X0

 

            Réseau = graphe          ® avec une entrée et une sortie

                                               ® sans boucles


 

Chemin minimal :

 

 

i

j

(xi, xj) existe

(lj - li)

> g(xi, xj)

lj

i > j ?

i ¬ j (j=0)

j ¬ j+1

j > n ?

fin

l1

+¥

l2

+¥

l3

+¥

l4

+¥

l5

+¥

0

1

oui

oui

3

non

 

2

non

 

3

 

 

 

 

0

2

oui

oui

8

non

 

3

non

 

 

8

 

 

 

0

3

oui

oui

6

non

 

4

non

 

 

 

6

 

 

0

4

non

 

 

 

 

5

non

 

 

 

 

+¥

 

0

5

non

 

 

 

 

6

oui

 

 

 

 

 

+¥

1

1

non

 

 

 

 

2

non

 

 

 

 

 

 

1

2

non

 

 

 

 

3

non

 

 

 

 

 

 

1

3

oui

oui

5

non

 

4

non

 

 

 

5

 

 

1

4

oui

oui

9

non

 

5

non

 

 

 

 

9

 

1

5

non

 

 

 

 

6

oui

 

 

 

 

 

 

2

1

non

 

 

 

 

2

non

 

 

 

 

 

 

2

2

non

 

 

 

 

3

non

 

 

 

 

 

 

2

3

non

 

 

 

 

4

non

 

 

 

 

 

 

2

4

oui

oui

9

non

 

5

non

 

 

 

 

9

 

2

5

non

 

 

 

 

6

oui

 

 

 

 

 

 

3

1

non

 

 

 

 

2

non

 

 

 

 

 

 

3

2

oui

oui

7

non

 

3

non

 

 

7

 

 

 

3

3

non

 

 

 

 

4

non

 

 

 

 

 

 

3

4

non

 

 

 

 

5

non

 

 

 

 

 

 

3

5

oui

oui

12

non

 

6

oui

 

 

 

 

 

12

4

1

non

 

 

 

 

2

non

 

 

 

 

 

 

4

2

non

 

 

 

 

3

non

 

 

 

 

 

 

4

3

non

 

 

 

 

4

non

 

 

 

 

 

 

4

4

non

 

 

 

 

5

non

 

 

 

 

 

 

4

5

oui

oui

11

 

 

6

oui

 

 

 

 

 

12

5

 

 

 

 

 

 

 

oui