Marc Gengler [email protected]

St Valentin 2006 Cours de graphes 1 - Intranet 1

• Marc Gengler• [email protected]

Cours de graphes

Alexandra Bac - Sébastien Fournier12h de cours

12h de TDdes devoirs

… et un examen


Bibliographie•Tout ce qui contient

- graphes, graphs.•Internet- souvent, c’est trop simplifié ou trop dense,- et pas toujours correct.•Mes choix- Introduction to Algorithms, Leiserson et al.- Algorithms, Sedgewick.- Fundamental Algorithms, Knuth.- Graphes, Berge.


Les grandes lignes du cours•Définitions de base•Connexité•Les plus courts chemins•Dijkstra et Bellmann-Ford•Arbres•Arbres de recouvrement minimaux •Problèmes de flots•Coloriage de graphes•Couplage•Chemins d’Euler et de Hamilton•Problèmes NP-complets


Définitions de base-----------------------------------------------------------------

• Il y a des sommets ! (vertex, vertices)• Il y a des arêtes ! (edge)• Il y a des arcs ! (arc)



• Formellement :• Il y a l’ensemble « V » des sommets.

– Il y en a « n », c’est-à-dire | V | .– La complexité est fonction du nombre de sommets.

• Il y a l’ensemble « E » des arcs et arêtes.– C’est une partie du produit cartésien V x V .– « E » peut être réflexif, irréflexif ou ni l’un, ni l’autre.

Tous des couples ( a , a ) ! Aucun couple ( a , a ) !



( a , b ) ssi ( b , a ) !Si ( a , b ) avec a = b alors pas ( b , a ) !/



• Il y a l’ensemble « E » des arcs et arêtes.– C’est une partie du produit cartésien V x V .– « E » peut être réflexif, irréflexif ou ni l’un, ni l’autre.– « E » peut être symétrique, anti-symétrique ou ni - ni.





• Il y a l’ensemble « E » des arcs et arêtes.– C’est une partie du produit cartésien V x V .– « E » peut être réflexif, irréflexif ou ni l’un, ni l’autre.– « E » peut être symétrique, anti-symétrique ou ni - ni.

Graphe non orienté ! Graphe orienté !



Si ( a , b ) et ( b , c ) alors (a , c ) !



• Il y a l’ensemble « E » des arcs et arêtes.– C’est une partie du produit cartésien V x V .– « E » peut être réflexif, irréflexif ou ni l’un, ni l’autre.– « E » peut être symétrique, anti-symétrique ou ni - ni.– « E » peut être transitive, ou non-transitive.



• Formellement :– G = ( V , E )– Un graphe est donné par les ensembles « V » et « E ».

• Il y a des multi-graphes qui sont correspondent au cas où « E » est un multi-ensemble (plusieurs arêtes et/ou arcs entre deux sommets).

• Il y a des graphes pondérés qui correspondent au fait l’on attache des poids aux arcs ou arêtes (entiers par exemple).

12

1525



• Sous-graphe G’ d’un graphe G :– Le graphe G’ = ( V’ , E’ ) est un sous-graphe du graphe

G = ( V , E ) , si :

• V’ V les sommets de G’ sont parmi ceux de G

• E’ E V’ x V’ les arcs et arêtes de G’ sont parmi ceux et celles de G et se limitent aux sommets de G’.

UU

v



• Représentation des données :• Nous indexons (numérotons) les sommets.• Nous représentons les arcs et les arêtes.• Nous obtenons une matrice « M » de taille n x n

qui comporte des valeurs binaires.• M( a , b ) est vrai si et seulement si l’arc ( a , b )

existe !



1

2

4

35

6

123456

1 2 3 4 5 6

L’existence ou nonde l’arc ( 2 , 5 ) ! ! !



1

2

4

35

6

123456

1 2 3 4 5 6

VF

FF

FF

V

VV

VLes arêtes ( 2 , 4 ) et ( 3 , 5 )sont symétriques !

V

V

Les arcs ( 1 , 4 ) et ( 4 , 1 )donnent aussi une symétrie !

V

V

Les arcs ( 4 , 3 ) et ( 6 , 3 ) n’ontpas leur pendant symétrique ! ! !

Il faut n^2 bits !

F FF F F

F F

F F

F FF FF F

F F

F F

FFF

La diagonale parle des couples ( u , u ) !



1

2

4

35

6

123456

1 2 3 4 5 6

VF

FF

FF

Pour des multi-graphes, nousremplaçons les booléens pardes multiplicités !V

VV

VV

V

Pour des graphes pondérés,nous remplaçons les booléenspar des poids !

V

V

F FF F F

F F

F F

F FF FF F

F F

F F

FFF



123456

1 2 3 4 5 6

VF

FF

FF

V

VV

VV

V

V

V

F FF F F

F F

F F

F FF FF F

F F

F F

FFF

445

1 2 33

3 6

Il faut( | V | + | E | ) * log( | V | )bits !

Parfois, le graphe est peu dense !

Nous mémorisons juste les indicesdes colonnes différentes de Faux !



123456

1 2 3 4 5 6

VF

FF

FF

Les voisins d’un sommet « u » :

Les voisins sortants : V+ ( u )

Les voisins entrants : V- ( u )V

VV

VV

V

V+ ( u ) = { v V | ( u , v ) E }

V- ( u ) = { v V | ( v , u ) E }

V

V

F FF F F

F F

F F

F FF FF F

F F

F F

FFF

Si le graphe est symétrique :

V ( u ) = V+ ( u ) = V- ( u )

V- ( 3 ) = { 4 , 5 , 6 }

V+ ( 4 ) = { 1 , 2 , 3 }



123456

1 2 3 4 5 6

VF

FF

FF

Le degré d’un sommet « u » :

Le degré sortant : D+ ( u )

Le degré entrant : D- ( u )V

VV

VV

V

D+ ( u ) = | V+ ( u ) |

D- ( u ) = | V- ( u ) |

V

V

F FF F F

F F

F F

F FF FF F

F F

F F

FFF


D ( u ) = D+ ( u ) = D- ( u )

Le degré d’un graphe G = ( V , E ) :

D( G ) = max { D ( u ) }u V



123456

1 2 3 4 5 6

VF

FF

FF

Le degré d’un sommet « u » :

Le degré sortant : D+ ( u )

Le degré entrant : D- ( u )V

VV

VV

V

D+ ( u ) = | V+ ( u ) |

D- ( u ) = | V- ( u ) |

V

V

F FF F F

F F

F F

F FF FF F

F F

F F

FFF


D ( u ) = D+ ( u ) = D- ( u )

Le degré d’un graphe G = ( V , E ) :

D( G ) = max { D ( u ) }u V



• Les chemins :• Un chemin, de longueur « n », du sommet « u » au

sommet « v » est :

( w , . . . , w )

• telle que– u = w et v = w

– ( w , w ) est une arête ou un arc du graphe.

• Le chemin est orienté s’il comporte des arcs, non orienté s’il est fait d’arêtes uniquement.

1 n+1

i i+1

1 n+1



• Notations et propriétés sur les chemins :• Nous noterons ( c’est non standard ) :

– ( u , v ) l’arête ou l’arc, c’est-à-dire le chemin de longueur 1 .

– ( u ; v ) le chemin de longueur quelconque.

• Pour tout chemin non orienté ( u ; v ) du graphe G, nous pouvons construire le chemin ( v ; u ) dans G.

• Dans un graphe G, l’existence du chemin orienté ( u ; v ) n’implique pas l’existence d’un chemin de retour ( v ; u ) .



• Cycles et circuits :• Un chemin non orienté ( u ; v ) pour lequel « u » coïncide

avec « v » est un cycle.• Un chemin orienté ( w ; t ) pour lequel « w » coïncide avec

« t » est un circuit.

u = v

w = t



• Chemins simples :• Un chemin ( u ; v ) , où « u » est différent de « v », est

simple si et seulement si aucun sommet n’est répété dans la séquence :

( u , . . . , v )

u

t

Chemin simple ( u ; v )

v

w

Chemin nonsimple ( w ; t )



• Lemme de König :• De tout chemin non simple ( u ; v ) , nous pouvons

extraire un chemin de « u » vers « v » qui est simple et plus court que le chemin initial.

( u , . . . , w , . . . , w , t , . . . , v )

u

vw

tDe tout cycle oucircuit nouspouvonsextraire uncycle ou circuitélémentaire !



• Lemme de König :• De tout chemin non simple ( u ; v ) , nous pouvons

extraire un chemin de « u » vers « v » qui est simple et plus court que le chemin initial.

( u , . . . , w , . . . , w , t , . . . , v )

u

vw

tDe tout cycle oucircuit nouspouvonsextraire uncycle ou circuitélémentaire !



1

2

4

35

6

123456

1 2 3 4 5 6

VF

FF

FF

V

VV

VV

V

V

V

F FF F F

F F

F F

F FF FF F

F F

F F

FFF

La composante connexe de « u » :

La composante sortante : C+ ( u )

La composante entrante : C- ( u )

C+ ( u ) = { v V | ( u ; v ) existe }

C- ( u ) = { v V | ( v ; u ) existe }

Si G est symétrique : C ( u ) = C+ ( u ) = C- ( u )

C+ ( 4 ) = { 1 , 2 , 3 , 4 , 5 }C- ( 4 ) = { 1 , 2 , 4 }



• Pour un graphe non orienté :• La composante connexe de « u » est :

– réflexive, vous pouvez rester où vous êtes !

– symétrique, les chemins de retour existent !

– transitive, vous pouvez concaténer des chemins !

• Une composante connexe est une classe d’équivalence !• Un graphe non orienté est partitionné en ses classes

d’équivalence !



1

2

4

35

6

123456

1 2 3 4 5 6

VF

FF

FF

V

VV

VV

VF FF F F

F F

F F

F FF FF F

F F

F F

FFF

F

F

Nous partons d’unerelation symétrique !

Nous fermons réflexivement !

La fermeture réflexive d’unerelation « R » est la plus petiterelation réflexive qui contienne « R ».



1

2

4

35

6

123456

1 2 3 4 5 6

V

V

VV

VV

VF FF F F

F F

F F

F FF FF F

F F

F F

FFF

F

F



La fermeture réflexive d’unerelation « R » est la plus petiterelation réflexive qui contienne « R ».

VV

VV

V



1

2

4

35

6

123456

1 2 3 4 5 6

V

V

VV

VV

VF FF F F

F F

F F

F FF FF F

F F

F F

FFF

F

F



La fermeture transitive d’unerelation « R » est la plus petiterelation transitive qui contienne « R ».

VV

VV

V

Nous fermons transitivement !



1

2

4

35

6

123456

1 2 3 4 5 6

V

V

VV

VV

VFF F F

F F

F F

F FF FF F

F F

F F

FFF

F



La fermeture transitive d’unerelation « R » est la plus petiterelation transitive qui contienne « R ».

VV

VV

V


VV



1

2

4

35

6

123456

1 2 3 4 5 6

V

V

VV

VV

VFF F F

F F

F F

F FF FF F

F F

F F

FFF

F



VV

VV

V


VV

{ 1 , 2 , 4 } est une composante connexe !



1

2

4

35

6

123456

1 2 3 4 5 6

V

V

VV

VV

VFF F F

F F

F F

F FF FF F

F F

F F

FFF

F



VV

VV

V


VV

{ 3 , 5 } est une composante connexe !



1

2

4

35

6

123456

1 2 3 4 5 6

V

V

VV

VV

VFF F F

F F

F F

F FF FF F

F F

F F

FFF

F



VV

VV

V


VV

{ 6 } est une composante connexe !



1

2

3

45

6

123456

1 2 3 4 5 6

V

VV

VV

V

V FF F F

F F

FF

F FF FF FF F

F F

FFF

F



VV

VV

V


VV

Si nous renumérotons !



• Principe de décomposition :• Souvent, le traitement appliqué à un graphe non connexe consiste à appliquer ce même traitement indépendamment sur chacune des composantes connexes !

• Dans ce cas, on ne perd rien à supposer G connexe ! ! !



• Pour un graphe orienté :• Un sous-ensemble « X » des sommets d’un graphe orienté

est fortement connexe si nous pouvons aller de n’importe quel sommet vers n’importe quel autre sommet.

• Proposition :– Une composante est fortement connexe si et seulement si chaque sommet se trouve sur un circuit.

• Preuve :– => : Si ( u ; v ) existe, alors ( v ; u ) existe et donc ( u ; v ; u )

.– <= : Soit ( u ; v ) de la forme ( u ; w ; v ). Pour « w » bien choisi, le circuit ( w ; v ; w ) existe ! Nous recommençons le raisonnement pour ( u ; w ) .

u vw



• Pour un graphe orienté :• Un graphe orienté est quasi-fortement connexe s’il existe

un sommet depuis lequel nous pouvons atteindre tous les autres sommets. Un tel sommet sera appelé « racine ».



• Distances et diamètre :• La distance « d ( u , v ) » entre un sommet « u » et un

sommet « v » est :– la longueur du plus court chemin (forcément simple) de « u »

vers « v », si celui-ci existe,

– infini, sinon.

• Le diamètre d’un graphe connexe est la distance entre ses sommets les plus éloignés :

( G ) = max { d ( u , v ) }u , v V



uv

Chemin simple de longueur 4 !Le plus court chemin est de longueur 3 : d ( u , v ) = 3

( G ) = 4



• Ecarts, centre et diamètre :• L’écart « e ( u ) » d’un sommet « u » d’un graphe connexe est :

– la distance vers le sommet « v » le plus loin de « u » :

e ( u ) = max { d ( u , v ) }

• Un sommet « u » est au centre de G si

e ( u ) = min { e ( v ) }

• ( G ) = max { e ( v ) }

v V

v V

v V



u

e ( u ) = 3

v

« v » est au centre car e ( v ) = 2 est minimal !

( G ) = e ( w ) = 4

w



• Lemme des plus courts chemins (De la Palisse) :• Si le plus court chemin de « u » vers « v » passe par « w », alors la partie préfixe de « u » vers « w » est aussi le plus court chemin de « u » vers « w ».

u vw

Le plus court chemin de « u » à « v » !

Le plus court chemin de « u » à « w » !



• Poids d’un chemin :• Dans un graphe pondéré, le poids d’un chemin est la somme

des poids de ses arcs et arêtes.• Nous pouvons alors, de manière évidente, définir le chemin le

plus léger de « u » vers « v ».• Le chemin le plus léger (poids) ne coïncide pas forcément avec

le chemin le plus court (nombre d’arcs et arêtes). • Les poids ne vérifient pas forcément l’inégalité triangulaire !

25

10 12



• Poids d’un chemin :• Dans un graphe pondéré, le poids d’un chemin est la somme

des poids de ses arcs et arêtes.• Nous pouvons alors, de manière évidente, définir le chemin le

plus léger de « u » vers « v ».• Le chemin le plus léger (poids) ne coïncide pas forcément avec

le chemin le plus court (nombre d’arcs et arêtes). • Les poids ne vérifient pas forcément l’inégalité triangulaire !

25

10 12


Connexité – plus courts chemins-----------------------------------------------------------------

• Sur un graphe non orienté, nous allons calculer :– les composantes connexes !

• Sur une composante connexe, nous allons calculer :– les plus courts chemins !

• Nous rajoutons une pondération strictement positive et nous allons calculer :– les chemins les plus légers !



• Nous utilisons trois algorithmes :

– un algorithme par « vague », c’est un parcours en largeur,

– un algorithme par « multiplication de matrices »,

– l’algorithme de programmation dynamique « Floyd-Warshall » !

• Pour chacun d’entre eux, il s’agit de savoir si :

– il arrive à résoudre le problème en question,

– quelle est la complexité du calcul ?



Connexité

Plus courts

Plus légers

La vague Multiplication Floyd-Warshall



• L’algorithme par vague :– Nous choisissons un sommet sec et le mouillons, – nous mouillons ses voisins,– nous mouillons les voisins des voisins , . . .

• Attention, dans un graphe il peut y avoir des cycles ! ! !– Il faut éviter de tourner en rond !– Ici, nous ne faisons rien pour un sommet déjà mouillé !

• Complexité : ( | E | ) = O( | V |^2 ) = O ( n^2 )

– Chaque arête est visitée une et une seule fois !



Connexité

Plus courts

Plus légers


( | E | ) = O ( | V |^2 )



• La multiplication de matrices :– Nous prenons une matrice avec des « 0 » et des « 1 »,– nous la fermons réflexivement (des « 1 » sur la diagonale),– nous effectuons le calcul suivant :

M * M’ ( i , j ) = max M ( i , k ) * M’ ( k , j )

• Nous calculons : M -> M^2 -> M^4 -> . . . • Propriété : M^( 2 * i ) = Mî * Mî contient tous les

chemins de longueur au plus 2 * i .• Il suffit de calculer M^k avec k >= | V |-1 = n-1 (le plus

long chemin possible; et donc tous les chemins) !• Il suffit de O ( log( | V | ) ) élévations au carré !

k



• Preuve de la propriété :– La matrice M fermée réflexivement contient tous les

chemins de longueur 0 ou 1.– Hypothèse d’induction : Mî contient tous les chemins

de longueur au plus i .

M^( 2 * i ) ( u , v ) = 1 max_k Mî ( u , k ) * Mî ( k , v ) = 1 w tel que Mî ( u , w ) * Mî ( w , v ) = 1 Mî ( u , w ) = 1 et Mî ( w , v ) = 1 ( u ; w ) et ( w ; v ) sont de longueur au plus i ( u ; w ; v ) est de longueur au plus 2 * i .• On obtient bien-sûr tous les chemins !



Connexité

Plus courts

Plus légers


( | E | ) = O ( | V |^2 )

( | V |^3 * log( | V | ) )



• Floyd-Warshall :– La multiplication recalcule de façon répétée les chemins

courts. Si Mî ( u , v ) = 1 :

M^( 2 * i ) ( u , v ) = max_k Mî ( u , k ) * Mî ( k , v ) = Mî ( u , u ) * Mî ( u , v ) = Mî ( u , v ) = 1

• La DP numérote les sommets de « 1 » à « n » et :

– à l’étape (1), ne calcule que les chemins dont les intermédiaires sont dans l’ensemble { 1 },

– à l’étape (2), ne calcule que les chemins dont les intermédiaires sont dans l’ensemble { 1 , 2 }, . . .



12

3

Initialement : M(0)

Etape 1 : M(1)

Nous n’avons pas dessiné les boucles de la fermeture réflexive !

Etape 2 : M(2)

Etape 3 : M(3)

Petit à petit, les uns . . .



12

3

Initialement : M(0)

Etape 1 : M(1)


Etape 2 : M(2)

Etape 3 : M(3)

Petit à petit, les autres . . .



12

3

Initialement : M(0)

Etape 1 : M(1)


Etape 2 : M(2)

Etape 3 : M(3)

Petit à petit, finalement . . .



M ( u , v ) = M ( u , v )(k) (k-1)

(k-1)

(k)

• M est donnée, elle comporte tous les chemins avec des intermédiaires parmi { 1 , . . . , k-1 } .

• M ( u , v ) est un chemin de « u » vers « v » avec des intermédiaires parmi { 1 , . . . , k } .

• Soit le sommet « k » figure dans ce chemin, soit il ne le fait pas.

u - . . . - k - . . . - v

M ( u , k ) M ( k , v )

/ k / k

(k-1) (k-1)

} }



• M est la matrice d’adjacence, fermée réflexivement. Elle comporte des « 0 » et des « 1 ».

M ( u , v ) = max ( , )• M est la matrice recherchée !

(0)

M ( u , k ) * M ( k , v )(k-1)M ( u , v )(k-1)

(k-1)

(n)

(k)

Pour k de 1 a | V | Pour u de 1 a | V | Pour v de 1 a | V | M_k ( u , v ) <- . . .



Connexité

Plus courts

Plus légers


( | E | ) = O ( | V |^2 )

( | V |^3 * log( | V | ) ) ( | V |^3 )


Synthèse-----------------------------------------------------------------

• Définitions de base

• Connexité :

– à l’aide de la vague,

– à l’aide de la multiplication,

– à l’aide de Floyd-Warshall.

Documents

Marc Gengler [email protected]