Abdelkader Naji



CPGE OUJDA SPE

Introduction à la théorie des graphes

A. Qu’est ce qu’un graphe ?

Un des plus anciens problèmes combinatoires, la détermination d’un itinéraire à travers la ville de konigsberg(aujourd’hui kaliningrad) en n’utilisant qu’une fois et une seule chacun des sept ponts qui enjambaient les bras de la pregel ou conduisaient à l’île de kneiphof, dont Euler montra en 1735 l’impossibilité, semble constituer le premier témoignage de l’emploi des graphes finis.

Un Graphe, au départ, c'est simple : des sommets et des arcs, des points et des flèches ou des traits qui les relient. Quand ce sont des flèches, on a affaire à des graphes orientés; si ce sont des traits, le graphe n'est pas orienté. Certains problèmes font intervenir l'orientation, d'autres non.

[pic]

B. Vocabulaire de la théorie des graphes

• Un graphe est composé d'un ensemble de sommets et d'un ensemble d'arcs(ou arêtes); on note X l'ensemble des sommets.

• Un arc (ou arête) est un couple de sommets, donc, un élément du produit cartésien XxX; on note U la famille des arcs (des arêtes). Ainsi le graphe (noté, par exemple : G) sera-t-il égal au couple (X,U)

• U graphe valué ou pondéré est défini par un triplet < X, U, C > où C est une fonction de U sur [pic]appelée fonction de coût. On utilise par convention Cu pour représenter le coûts, le poids ou la valeur d'un arc (ou arêtes) u.. Ainsi le graphe valué (noté, par exemple : G) sera-t-il égal au couple (X,U,C).

• Le nombre de sommets est appelé l'ordre du graphe et sera, en général, noté : n

• En général, les sommets d'un graphe seront représentés par des points de l'espace et les arcs par des flèches allant d'un point à un autre, c'est ce qu'on appelle la représentation sagittale du graphe

• Dans un arc (x,y) : x est l'extrémité initiale et y l'extrémité finale.

• Une boucle est un arc de la forme (x,x) .dans un graphe non orienté les boucles sont interdites et chaque arête est donc constituée de deux sommets distincts.

• On dit que y est un successeur de x s'il existe un arc (x,y); on dit aussi que x est un prédécesseur de y.

• Un graphe simple est un graphe sans boucle tel qu'entre deux sommets différents, il y ait au plus un arc.

o Dans un graphe simple, on pourra donc noter un arc à l'aide de ses extrémités initiale et finale.

o Dans un graphe simple, on peut parler de l'ensemble des arcs.

• Deux arcs sont dits adjacents s'ils ont une extrémité en commun.

• Deux sommets sont dits adjacents si un arc les relie.

• Degré d’un sommet : dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes. Si un sommet est de degré 0, il est dit isolé.

• Degré sortant d’un sommet : dans un graphe orienté, le degré sortant d’un sommet est le nombre d’arc qui en partent.

• Degré entrant d’un sommet : dans un graphe orienté, le degré entrant d’un sommet est le nombre d’arcs qui y arrivent. Et le degré d’un sommet est la somme de son degré entrant et son degré sortant.

• Une chaîne est une succession d'arcs, chaque arc intermédiaire de la séquence ayant une extrémité en commun avec l'arc précédent et l'autre extrémité en commun avec l'arc suivant.

o Une chaîne ne rencontrant pas deux fois le même sommet est dite élémentaire.

o Une chaîne ne rencontrant pas deux fois le même arc est dite simple.

• Un chemin est une chaine bien orientée, c'est à dire que tous les arcs de la chaîne sont parcourus dans le bon sens. Ce n'est pas nécessairement le cas dans une chaîne, où on peut rencontrer des arcs directs (parcourus dans le bon sens) et des arcs inverses.

• Un cycle est une chaîne simple qui "boucle" : les arcs de début et de fin sont adjacents par leur sommet libre.

• Un circuit est un cycle "bien orienté", à la fois cycle et chemin.

• Une chaîne eulérienne est une chaîne empruntant tous les arcs du graphe une fois et une seule.

• Une chaîne hamiltonnienne est une chaîne passant par tous les sommets du graphes une fois et une seule.

• Un graphe non orienté est connexe si pour toute paire de sommets disjoints u et v, il existe une chaîne (u [pic]v) reliant ces deux sommets.

• Un graphe orienté est fortement connexe si pour toute paire ordonnée de sommets disjoints u et v, il existe un chemin de u vers v (u [pic]v).

Représentation non graphiques d’un graphe

Matrice d’adjacences

On peut représenter un graphe simple par une matrice d’adjacences. Une matrice (n×m)

est un tableau de n lignes et m colonnes. (i, j) désigne l’intersection de la ligne i et de la colonne j . Dans une matrice d’adjacences, les lignes et les colonnes représentent les

sommets du graphe.

• Pour un graphe orienté, l’existence d’un arc entre deux sommets i et j se traduit par la présence d’un « 1 » à l’intersection de la ligne i et de la colonne j de la matrice d’adjacences ; l’absence d’arc, par la présence d’un « 0 ».

|1 |2 |3 |4 |5 |6 |7 |8 |9 | | |1 |0 |1 |1 |0 |0 |0 |1 |0 |0 | | |2 |0 |0 |0 |1 |0 |0 |0 |0 |0 | | |3 |0 |0 |0 |0 |0 |1 |0 |0 |1 | | |4 |0 |0 |0 |0 |0 |0 |1 |0 |0 | | |5 |0 |0 |0 |1 |0 |0 |0 |0 |0 | | |6 |0 |0 |1 |0 |0 |0 |1 |0 |1 | | |7 |0 |0 |0 |1 |1 |0 |0 |0 |0 | | |8 |0 |0 |0 |0 |0 |1 |1 |0 |1 | | |9 |0 |0 |0 |0 |0 |0 |0 |0 |0 | | |

• Pour un graphe non orienté, Un « 1 » à la position (i, j) signifie que le sommet i est adjacent au sommet j et « 0 » à la position (i, j) signifie que les sommets i et j ne sont pas adjacents. La matrice d’adjacences d’un graphe non orienté possède les caractéristiques suivantes :

o Elle est carrée : il y a autant de lignes que de colonnes.

o Il n’y a que des zéros sur la diagonale allant du coin supérieur gauche au coin inférieur droit. Un « 1 » sur la diagonale indiquerait une boucle ce qui n’est pas possible pour un graphe non orienté.

o Elle est symétrique : mi j =mji . On peut dire que la diagonale est un axe de symétrie.

o Une fois que l’on fixe l’ordre des sommets, il existe une matrice d’adjacences unique pour chaque graphe. Celle-ci n’est la matrice d’adjacences d’aucun autre graphe.

|1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 | | |1 |0 |0 |1 |1 |1 |0 |0 |0 |0 |0 |0 | | |2 |0 |0 |0 |0 |1 |0 |1 |0 |0 |0 |0 | | |3 |1 |0 |0 |1 |0 |0 |0 |0 |0 |0 |0 | | |4 |1 |0 |1 |0 |0 |0 |1 |0 |0 |0 |0 | | |5 |1 |1 |0 |0 |0 |0 |0 |0 |1 |1 |0 | | |6 |0 |0 |0 |0 |0 |0 |1 |1 |1 |0 |0 | | |7 |0 |1 |0 |1 |0 |1 |0 |1 |0 |0 |0 | | |8 |0 |0 |0 |0 |0 |1 |1 |0 |0 |0 |0 | | |9 |0 |0 |0 |0 |1 |1 |0 |0 |0 |1 |1 | | |10 |0 |0 |0 |0 |1 |0 |0 |0 |1 |0 |1 | | |11 |0 |0 |0 |0 |0 |0 |0 |0 |1 |1 |0 | | |NB :

• si le graphe est valué il n’est plus possible de se contenter d’une matrice de booléen. Dans ce cas, la matrice devient une matrice de coûts de types simples (entier, réel, etc.) et que la valeur peut être utilisée pour signaler l’absence d’arc ou d'arête.

• La représentation matricielle est très pratique pour tester l’existence d’un arc. Il est facile d’ajouter ou de supprimer un arc. Il est tout aussi facile de parcourir tous les successeurs ou prédécesseurs d’un sommet et donc de déterminer son degré ou ses demi-degrés.

C. Parcours de graphe

Le parcours d’un graphe est une méthode appliquée à un graphe orienté ou non orienté permet la conception de toute une famille d’algorithmes particulièrement efficaces. Ces algorithmes, appliqués à un graphe donné, déterminent des propriétés spécifiques ( par exemple déterminer si le graphe est connexe, ou encore fortement connexe) ou bien calculent des quantités caractéristiques de ce graphe(nombre de composantes connexes ; longueurs de chemin ; etc.).

Le principe de la méthode est de parcourir un graphe, c'est-à-dire l’ensemble de ses sommets et des arcs ou arêtes. Le parcours du graphe doit se faire en respectant quelques règles simples assurant, d’une part, que tout sommet et toute arc(arête) a bien été visité et, d’autre part, une complexité minimale de la procédure.

Procédure de parcours d’un graphe

Informellement, la procédure de parcours d’un graphe peut s’énoncer de la manière qui suit : on choisit un somment initial que l’on commence à visiter, la visite d’un sommet étant terminée lorsque l’on est allé visiter tous ses successeurs si le graphe est orienté (ou tous les sommets qui lui sont adjacents si le graphe est non orienté). Ensuite, à chaque étape, on choisit un sommet en cours de visite et on poursuit sa visite. Lorsqu’il n’est plus possible de poursuivre la visite d’aucun sommet du graphe, pour le sommet initial choisi, la procédure s’arrête si tous les sommets du graphe sont visités ; dans le cas contraire, on continue le parcours à partir d’un sommet non encore visité.

Tout au long de la procédure de parcours d’un graphe, chaque sommet passe par trois états successifs :

• initialement, un sommet n’est pas atteint par le parcours, il est alors non marqué,

• puis lorsqu’un sommet est atteint pour la première fois, sa visite débute, le sommet est alors dans l’état ouvert,

• enfin lorsque la visite d’un sommet est terminée, le sommet est alors dans l’état fermé.

Un parcours débute alors par l’ouverture d’un sommet du graphe(le sommet initial) et se termine lorsque tous les sommets sont fermés.

Parcours en profondeur d’un graphe non orienté ( ou un graphe orienté)

La stratégie utilisée pour effectuer un parcours en profondeur d’un graphe non orienté(ou un graphe orienté) obéit à la règle suivante : un sommet qui était non marqué n’est ouvert que s’il est adjacent (ou successeur) au dernier sommet précédemment ouvert, si un tel sommet n’existe pas, le dernier ouvert est fermé.

Il est possible de déterminer le dernier sommet ouvert en utilisant une pile. L’algorithme générique effectuant un parcours en profondeur d’un graphe non orienté (ou un graphe orienté) est le suivant :

1. initialement tous les sommets sont non marqués.

2. Tant qu’il existe s un sommet non marqué,

3. Ouvrir s et inserer s au sommet de la pile

4. Tant que la pile est non vide,

5. S’il existe un sommet y non marqué adjacent (ou successeur) au sommet x situé situé au sommet de la pile alors ouvrir y et inserer y dans la pile.

6. Sinon fermer le sommet x et supprmer x de la pile.

Fonction Python

### parcours en profondeur

import numpy as np

def parcours(M,n,i,f, marque):

new=marque

new.add(i)

for j in range (0,n):

if M[i,j]!= 0 and j not in new:

new=parcours(M,n,j,f,new)

f(i)

return new

def parcoursProfondeur(M,n,f):

marque=set(())

for i in range(0,n):

if i not in marque:

marque = parcours(M,n,i,f,marque)

return None

M=np.array([[0,1,0,0,0,0,0],\

[1,0,1,0,0,0,0],\

[0,1,0,1,0,1,0],\

[0,0,1,0,1,0,1],\

[0,0,0,1,0,0,0],\

[0,0,1,0,0,0,0],\

[0,0,0,1,0,0,0]])

# a en tête

# M=np.array([[0,1,0,1,1,0,0,0],\

# [1,0,1,0,0,0,0,0],\

# [0,1,0,1,0,0,0,0],\

# [1,0,1,0,1,0,0,0],\

# [1,0,0,1,0,1,1,0],\

# [0,0,0,0,1,0,1,0],\

# [0,0,0,0,1,1,0,1],\

# [0,0,0,0,0,0,1,0] ])

#d en tete

# M=np.array([[1,0,1,0,1,0,0,0],\

# [0,1,0,1,1,0,0,0],\

# [1,0,1,0,0,0,0,0],\

# [0,1,0,1,0,0,0,0],\

#

# [1,0,0,1,0,1,1,0],\

# [0,0,0,0,1,0,1,0],\

# [0,0,0,0,1,1,0,1],\

# [0,0,0,0,0,0,1,0] ])

# aa=parcours(M,1,0,print,set({}))

#

# print('**************')

bb=parcoursProfondeur(M,7,print)

Parcours en largeur d’un graphe non orienté ( ou un graphe orienté)

La stratégie pour effectuer un parcours en largeur obéit aux deux règles suivantes : tous les sommets adjacents(ou successeurs) non marqués d’un sommet en cours de visite sont ouverts successivement et leurs numéros d’ordre de prévisite seront donc consécutifs ; le sommet visité à toute étape est, parmi les sommets ouverts, celui qui a été ouvert le premier.

L’algorithme générique effectuant un parcours en largeur d’un graphe non orienté (ou un graphe orienté) est le suivant :

1. initialement tous les sommets sont non marqués.

2. Tant qu’il existe s un sommet non marqué,

3. Ouvrir s et inserer s au sommet de la file

4. Tant que la file est non vide,

5. Supprimer le sommet x en tête de la file

6. Ouvrir et inserer successivement dans la file tous les sommets y non marqués marqués, adjacents (ou successeurs) de x

7. Fermer le sommet x.

D. Algorithme de plus court chemin

Les problèmes de cheminement sont des problèmes classiques de la théorie des graphes. L'objectif est de calculer une route entre des sommets d'un graphe qui minimise ou maximise une certaine fonction économique.

Le problème le plus classique consiste à chercher le chemin qui minimise la somme des valuations des arêtes traversées. Au cas où les arêtes ne possèdent pas de valuations, on recherche le chemin de longueur minimale qui est le nombre d’arêtes de celui-ci. Il existe des algorithmes polynomiaux pour résoudre ce problème, comme l'algorithme de Dijkstra, l’algorithme de Bellman-ford, l’algorithme de Floyd-warshall, etc.

Algorithme de Dijkstra

Principe de l’algorithme : Il s'agit de construire progressivement, à partir des données initiales, un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arêtes (ou arcs) empruntées si les arêtes (ou arcs) ne sont pas valués on leur affecte un poids égal à 1.

Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies. Au cours de chaque itération, on va mettre à jour les distances des sommets reliés par une arête (ou un arc) au dernier du sous-graphe (en ajoutant le poids de l’arête (ou arc) à la distance séparant ce dernier sommet du sommet de départ ; si la distance obtenue ainsi est supérieure à celle qui précédait, la distance n'est cependant pas modifiée). Après cette mise à jour, on examine l'ensemble des sommets qui ne font pas partie du sous-graphe, et on choisit celui dont la distance est minimale pour l'ajouter au sous-graphe.

La première étape consiste à mettre de côté le sommet de départ et à lui attribuer une distance de 0. Les sommets qui lui sont adjacents(ou successeurs) sont mis à jour avec une valeur égale au poids de l'arête(ou l’arc) qui les relie au sommet de départ (ou à celui de poids le plus faible si plusieurs arêtes(ou arcs) les relient) et les autres sommets conservent leur distance infinie.

Le plus proche des sommets adjacents est alors ajouté au sous-graphe.

La seconde étape consiste à mettre à jour les distances des sommets adjacents à ce dernier. Encore une fois, on recherche alors le sommet doté de la distance la plus faible. Comme tous les sommets n'avaient plus une valeur infinie, il est donc possible que le sommet choisi ne soit pas un des derniers mis à jour.

On l'ajoute au sous-graphe, puis on continue ainsi à partir du dernier sommet ajouté, jusqu'à épuisement des sommets ou jusqu'à sélection du sommet d'arrivée.

Algorithme

1. G=(S, E) un graphe avec une valuation positive v des arêtes, sdeb un sommet de S

2. Initialiser tous les sommets comme étant « non marqué ». Affecter la valeur [pic] à tous les labels L

3. L(sdeb)=0

4. Tant Qu'il existe un sommet non marqué

5. Choisir le sommet [pic] non marqué de plus petit label L

6. Marquer a

7. Pour chaque sommet b non marqué voisin de a

L(b)=min(L(b), L(a)+v(a,b))

8. Fin Pour

9. Fin Tant Que

Fonction Python

### dijksta

import numpy as np

def dijkstra(M,s):

""" M : matrice, s: sommet de départ"""

infini=M[0,0] #valeur des cases non définies

n=len(M[:,0]) # le nombre de sommets

A=[]

C=list(range(0,n))

distance=np.ones(n,dtype=type(infini))* infini

distance[s]=0 # on somme les poids

pred=np.ones(n,dtype=int)*s

while C!=[]:

C.sort(key=lambda i:distance[i])

a=C[0]

for c in C:

if distance[a]+ M[a,c] < distance[c]:

distance[c]=distance[a]+M[a,c]

pred[c]=a

A.append(a)

C.remove(a)

return s,pred,distance,infini

M=np.array([ [99,10,99,99, 6,99],\

[ 0,99,99,99,99,99],\

[99, 4,99,99, 3,99],\

[ 99, 1,99,99,3,99],\

[99, 0,99,99,99, 3],\

[ 2, 6,99,99, 5,99] ])

print(dijkstra(M,0))

Avantages et inconvénient

L'algorithme de Dijkstra, très puissant, admet quand même quelques limites :

• Il demande une certaine masse de traitements quand le graphe devient grand. Quand la puissance matérielle est limitée, ou que l'on souhaite traiter rapidement le problème du chemin le plus court, on peut utiliser d'autres algorithmes, qui sont certes moins précis parfois, mais qui sont plus rapides et moins gourmands en ressources.

• On ne peut pas affecter aux liaisons un poids négatif (boucle infinie dans le cas d'un cycle de poids négatif).

Cependant il a plusieurs avantages :

• il trouve toujours le chemin ayant le poids le plus faible.

Algorithme de Bellman-ford

Principe de l’algorithme

L'algorithme de Bellman-Ford (Bell-End-Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, qui ne peut être utilisé que lorsque tous les arcs ont des poids positifs ou nuls, l'algorithme de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de détecter l'existence d'un circuit absorbant, c'est-à-dire de poids total négatif, accessible depuis le sommet source.

Algorithme.

En plus de calculer la longueur d’un plus court chemin depuis s, on peut aussi stocker un plus court chemin. En effet, à chaque fois qu’on relâche un arc (u, v), cela signifie que le chemin de s à v passe dorénavant par u, autrement dit le prédécesseur de v est maintenant le sommet u. On peut par exemple stocker ces prédécesseurs dans un tableau indexé par les sommets du graphe.

Algorithme

Données

G un graphe orienté valué connexe

s un sommet de G

Variables locales

L : tableau des distances depuis s

Pred : tableau des prédécesseurs sur un plus court chemin depuis s

Circuit : Booléen vrai si et seulement s’il y a un circuit négatif

(u, v) un arc

début

initialisation

L[s] := 0

pour tous les sommet v ≠ s faire L[v] := +∞

Circuit:= faux.

pour x = 0 à n − 1 faire

pour chaque arc (u, v) de G faire

si L(v)>L(u)+length((u, v,−!G)) alors

L(v) :=L(u)+length((u, v,−!G))

Pred[v] :=u

finsi

finprch

finpour

pour chaque arc (u, v) de G faire

si L(v)>L(u)+length((u, v,G)) alors

Circuit := vrai

finsi

finprch

fin

Sorties : L, Pred, Circuit.

Algorithme de Floyd-warshall

L’algorithme de Floyd-Warshall est un algorithme pour déterminer tous les plus courts chemins dans un graphe orienté et valué.

Principe de l’algorithme

L'algorithme de Floyd-Warshall prend en entrée un graphe orienté et valué (V, E), sous la forme d'une matrice d'adjacence donnant le poids d'un arc lorsqu'il existe et la valeur ∞ sinon. Le poids d'un chemin entre deux sommets est la somme des poids sur les arcs constituant ce chemin. Les arcs du graphe peuvent avoir des poids négatifs, mais le graphe ne doit pas posséder de cycle de poids strictement négatif. L'algorithme calcule, pour chaque paire de sommets, le poids minimal parmi tous les chemins entre ces deux sommets.

Soit V = {1, 2, 3, 4, …, n} l'ensemble des sommets de G et soient i et j deux sommets de V. On considère un chemin p entre i et j de poids minimal dont les sommets intermédiaires sont dans {1, 2, 3, …, k}. L'algorithme de Floyd-Warshall est basé sur l'observation suivante :

• soit p n'emprunte pas le sommet k ;

• soit p emprunte exactement une fois le sommet k (car les cycles sont de poids positifs ou nuls) et p est donc la concaténation de deux chemins, entre i et k et k et j respectivement, dont les sommets intermédiaires sont dans {1, 2, 3, …, k-1}.

Notons [pic]la matrice telle que [pic]est le poids minimal d'un chemin de i à j n'empruntant que des sommets intermédiaires dans {1, 2, 3, …, k}, s'il en existe un, et ∞ sinon. [pic]est la matrice définissant G. L'observation ci-dessus se traduit par l’égalité[pic], pour tous i, j et k dans {1, 2, 3, 4…, n}, en supposant les opérations [pic] et [pic]convenablement adaptées au cas d'un opérande ∞. Dès lors, on peut calculer successivement les matrices [pic]pour k=1, 2, 3, 4, …, n. Le calcul peut même être effectué en place, dans une unique matrice[pic].

Algorithme

1. Entrée : [pic] est une matrice [pic]

2. W ( G

3. pour k allant de 0 à n-1 à pas=1 faire :

4. pour i allant de 0 à n-1 à pas=1 faire :

5. pour j allant de 0 à n-1 à pas=1 faire :

6. Wij= min(Wij , Wik+Wkj)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download