Algorithmique II PDF

1
THÉORIE DES GRAPHES

Dr. Ing. Mohamed-Bécha Kaâniche
Laboratoire de Recherche en Sécurité Numérique, Sup’Com, Université de Carthage
1ère année cycle ingénieur
© medbecha 2010-2017
2
PLAN DU COURS
üNotion de graphes
üPropriétés des graphes
üReprésentations des graphes
üParcours des graphes
üProblèmes des plus courts chemins
3
NOTION DE GRAPHES
üUn graphe est un type abstrait de donnnées implémentant les concepts
mathématiques de graphes orientés et de graphes non orientés.
üUn graphe orienté G est représenté par un couple (S,A) où S est un
ensemble fini et A une relation binaire sur S (sous-ensemble du produit
cartésien S x S). L’ensemble S est l’ensemble des sommets de G et A est
l’ensemble des arcs (arrows) de G.
üUn graphe non orienté est un couple G=(S,A) où S est un ensemble fini
représentant les sommets du graphe et A est un ensemble de pairs inclus
dans l’ensemble { 𝑥 , 𝑦 ; 𝑥 ∈ 𝑆, 𝑦 ∈ 𝑆, 𝑥 ≠ 𝑦 } et représentant les arêtes
(lines) du graphe.
4
NOTION DE GRAPHES
üDans le cas général, le terme lien (edge) désigne un arc ou une arête
üUn graphe avec des liens pouvant être multiples entre deux sommets
distincts est appelé multi-graphe.
üL’ordre d’un graphe est le nombre de ses sommets :|S| ≧1
üLa taille d’un graphe est le nombre de ses liens : |A|≧0
5
PROPRIÉTÉS DES GRAPHES

üUne boucle est un arc qui relie un sommet à lui-même. Dans un graphe non
orienté les boucles sont interdites et chaque arête relie donc deux sommets
distincts.
üDegré d’un sommet : Dans un graphe non orienté, le degré d’un sommet est
le nombre d’arrêtes qui lui sont incidentes. Si un sommet est de degré 0,
comme le sommet 4 de l’exemple, il est dit isolé.
üDegré sortant d’un sommet : Dans un graphe orienté, le degré sortant d’un
sommet est le nombre d’arcs qui en partent.
üDegré rentrant d’un sommet : Dans un graphe orienté, le degré rentrant (ou
entrant) d’un sommet est le nombre d’arcs qui y arrivent.
6

üLe degré d’un sommet dans un graphe orienté est la somme de son
degré sortant et son degré entrant.
üChemin : Dans un graphe orienté G=(S,A), un chemin de longueur k
d’un sommet « u » à un sommet « v » est une séquence (w0,w1,…,wk)
de sommets telle que u = w0, v = wk et (wi-1,wi) appartient à A pour
tout i entre 1 et k. Un chemin est élémentaire si ses sommets sont tous
distincts.
üUn sous-chemin « sc » d’un chemin c = (w0,w1,…,wk) est une sous-
séquence contiguë de ses sommets. Autrement dit il existe « i » et « j »,
tels que 0 <= i <= j <= k et sc =(wi,wi+1,…,wj).
7

üCircuit : Dans un graphe orienté G=(S,A), un chemin c = (w0,w1,…,wk) forme
un circuit si et seulement si (1) w0 = wk et (2) le chemin contient au moins un
arc. Ce circuit est élémentaire si ses sommets sont tous distincts. Une boucle
est un circuit de longueur 1.
üChaîne : Dans un graphe non orienté G=(S,A), une chaîne de longueur k
d’un sommet « u » à un sommet « v » est une séquence (w0,w1,…,wk) de
sommets telle que u = w0, v = wk et {wi-1,wi} appartient à A pour tout i entre 1
et k. Une chaîne est élémentaire si ses sommets sont tous distincts.
üCycle : Dans un graphe non orienté G=(S,A), une chaîne (w0,w1,…,wk) est un
cycle si k>=3 et si w0 = wk. Ce cycle est élémentaire si ses sommets sont tous
distincts. Un graphe non orienté sans cycle est dit acyclique.
8

üGraphe connexe : Un graphe non orienté est connexe si chaque paire de
sommets est reliée par une chaîne. Les composantes connexes d’un graphe
sont les classes d’équivalence de sommets induites par la relation « est
accessible à partir de ».
üGraphe fortement connexe : Un graphe orienté est fortement connexe si
chaque sommet est accessible à partir de n’importe quel autre. Les
composantes fortement connexes d’un graphe sont les classes
d’équivalence de sommets induites par la relation « sont accessibles l’un à
partir de l’autre ».
üSous-Graphes : On dit qu’un graphe G0 = (S0,A0) est un sous-graphe de G =
(S,A) si S0 est inclus dans S et si A0 est inclus dans A.
9
REPRÉSENTATION DES GRAPHES

üLes sommets d’un graphe sont généralement numérotés de 1 à n où n est le
cardinal de l’esemble des sommets. Que devons nous stocker ?
ü Les informations sur les sommets peuvent être stockées dans un tableau
ü Les liens doivent être stockés d’une manière ou d’une autre.
üNous devons prendre en compte les opérations suivantes :
ü Parcourir tous les voisins immédiats d’un sommet : Suivre les liens incidents sur le
sommet considéré.
ü Tester si deux sommets sont directement connectés par un lien : Tester si deux
sommets sont voisins.
üPour stocker les liens, il faudra utiliser soit la matrice d’adjacence soit les listes
d’adjacences.
10

ü Matrice d’adjacence
ü Un moyen simple pour stocker l’information de connectivité
ü Savoir si deux sommet sont directment connectés prend un temps constant Θ 1
ü Parcourir les voisins immédiats d’un sommet prend Θ 𝑛 en temps
ü Utilisation d’une matrice 𝐴 de taille 𝑛×𝑛
ü 𝑎𝑖𝑗 =1 (ou bien un poids) s’il y a un lien entre le sommet i et le sommet j
ü 𝑎𝑖𝑗 = 0 sinon
ü Utilise Θ 𝑛2 en mémoire
ü A utiliser uniquement quand le nombre de sommet est inférieur à quelques milliers,
ü Et quand le graphe est dense
11

üListes d’adjacences
ü Chaque sommet possèdemsa propre liste de liens
ü Les listes sont de tailles variables (différentes tailles)
ü Utilisation en mémoire : Θ 𝑛 + 𝑚
12

üImplémentation des listes d’adjacences
ü Solution 1 : en utilisant les listes linéaires chainées
ü Surplus de mémoire et de traitement
ü Faire attention à l’utilisation de la mémoire dynamique et des pointeurs !
ü Solution 2 : Utilisation d’un tableau de vecteurs
ü Facile à coder et pas de problème de gestion de mémoire.
ü Mais relativement lente
ü Solution 3. Utilisation de tableaux !
ü Suppose que le le nombre total des liens est connu à l’avance
ü Très rapide et bonne utilisation de la mémoire
ü Il est très difficile d’ajouter des liens supplémentaires, le graphe doit être statique.
13
14

üImplémentation des listes d’adjacences en utilisant des tableaux :
ü Utiliser deux tableaux : un tableau E de taille 𝑚 et un tableau LE de taille 𝑛
ü E contient les liens
ü LE contient le premier lien de la liste d’adjacence de chaque sommet
ü Initialiser tous les éléments de LE à -1 (à zéro si le tableau est 1-indexé)
ü Insertion d’un nouveau lien de u à v avec un ID k
E[k].to = v
E[k].nextID = LE[u]
LE[u] = k
ü Parcourir tout les liens incidents (sortants) à partir du sommet u:
for(ID = LE[u]; ID != -1; ID = E[ID].nextID)
// E[ID] is an edge starting from u
15
GRAPHES SPÉCIAUX
üUn arbre est un graphe non orienté connexe et acyclique
Toutes ces assertions sont équivalentes :
ü𝛀 est un arbre
ü𝛀 est un graphe connexe et |A| = |S| - 1
ü𝛀 est un graphe acyclique et |A| = |S| - 1
üIl existe exactement une chaine entre chaque paire de sommets de 𝛀
ü𝛀 est un graphe acyclique mais si on ajoute une arête il devient cyclique
ü𝛀 est un graphe connexe mais si on supprime une arête il ne l’est plus
16
GRAPHES SPÉCIAUX
üGraphe Orienté Acyclique (Directed Acyclic Graph (DAG)):

üdéfinit un ordre partiel entre ses sommets
üGraphe Bipartite
üL’ensemble S des sommets peut être partitionné en deux sous-
ensembles (disjoints) tel que chaque lien du graphe relie un
sommet de l’un des sous-ensembles à l’un des sommets de l’autre
sous-ensembles.
17
PARCOURS DES GRAPHES

üLes graphes peuvent contenir des circuits/cycles et il faut éviter de
parcourir indéfiniment ces circuits/cycles ! Pour cela, il suffit de colorier
les sommets des graphes (marqué les sommets déjà parcourus) :
üInitialement les sommets sont tous blancs,
ülorsqu’un sommet est rencontré pour la première fois, il est peint
en gris,
ülorsque tous ses successeurs dans l’ordre de parcours ont été
visités, un sommet est repeint en noir.
18

ü Parcours en profendeur d’abord :
DepthFirstSearch(G)
Begin
for each vertex u (*sommet*) of G do color[u] = white
for each vertex u of G do
if color[u] = white then DFS-visit(G, u, color)
End
DFS-visit(G, v, color)
Begin
color[v] = grey
for each neighbor n (*voisin*) of v do
if color[n] = white then DFS-visit(G, n, color)
color[v] = black
End
19

üParcours en profendeur d’abord (Suite)
üUtiliser une version non-récursive si la profondeur des appels
récursifvs est très grande (dépassant quelques milliers)
üRemplacer l’appel récursive par l’utilisation d’une pile
üParcours en largeur d’abord
Dans un parcours en largeur d’abord, tous les nœuds à une profondeur
i doivent avoir été visités avant que le premier nœud à la profondeur
i+1 ne soit visité. Un tel parcours nécessite l’utilisation d’une file
d’attente pour se souvenir des branches qui restent à visiter.
20

üParcours en largeur d’abord (suite)
BreadthFirstSearch(G)
Begin
for each vertex u (*sommet*) of G do color[u] = white
for each vertex u of G do
if color[u] = white then BFS-visit(G, u, color)
End
21

ü Parcours en largeur d’abord (suite)
BFS-visit(G, v, color)
Begin
color[v] = grey
Let Q a queue (*soit Q une file *)
Init Q with v (* queuing v in Q : enfiler v dans Q *)
while not Q.empty() do
u = Q.get() (* defiler *)
for each neighbor n (* voisin *) of u do
if color[n] = white then color[n] = grey
Q.put (n) (* enfiler *)
color[u] = black
End
22
PROBLÈMES DES PLUS COURTS CHEMINS
üEntrée : un graphe valué G = ( S, A )

üLe graphe peut être orienté ou non orienté
üParfois, les arcs/arêtes avec poids négatives sont autorisés
üSortie : Le chemin entre deux sommets donnés u et v minimisant le
coût total (ou poids total ou bien longueur total)
üParfois, il faudra calculer les plus courts chemins entre chaque pair
de sommets
üParfois, il faudra calculer les plus courts chemins entre un sommet
particulier et les autres sommets
23
üThéorème d’existence :
Les plus court chemins existent entre chaque pair de sommets

quelconques du graphe G si et seulement si :
üG est non orienté et connexe ou G est orienté et fortement connexe
üG ne contient pas de cycle / circuit absorbant c.à.d. un cycle / circuit

avec un poids total négatif
24
üAlgorithme de Floyd-Warshall
üCalcule les plus courts chemins entre chaque pair de sommets
üUtilise la représentation du graphe avec une matrice d’adjacence
üGénère une matrice D où 𝑑78 est la plus courte distance entre le
nœud i et nœud j
üPeut détecter un cycles / circuit absorbant
üS’exécute en une temps de 𝜣(𝒏𝟑 )
üTrès facile à coder
üApplications : routage optimal, Maximisation de la bande
passante
25
Algorithm Floyd-Warshall (G = (S, A))

Begin
let D be a |S|×|S| array of minimum distances initialized to ∞ (infinity)
for each vertex i
𝑑77 ← 0
for each edge (u,v)
𝑑>? ← w(u,v) // the weight of the edge (u,v)
for k = 1 to n do
for all i and j :
𝑑78 = min 𝑑78 , 𝑑7D + 𝑑D8
if 𝑑77 < 0 for some i, then the graph has a negative cycle
End
26
üNotons 𝑓(𝑖, 𝑗, 𝑘) la plus courte distance de i à j en utilisant au plus k nœud

intermédiaire
ü 𝑓(𝑖, 𝑗, 𝑛) est la plus courte distance entre i et j
ü 𝑓 𝑖, 𝑗, 0 = 𝑐𝑜𝑠𝑡(𝑖 , 𝑗) ( 0 si i = j ; w(i, j) si (i, j) ∊ A et i ≠ j ; ∞ si (i, j) ∉ A )
üLe chemin/chaîne optimal pour 𝑓(𝑖, 𝑗, 𝑘) peut ou pas avoir k comme nœud
intermédiaire
ü Si oui 𝑓 𝑖, 𝑗, 𝑘 = 𝑓 𝑖, 𝑘, 𝑘 − 1 + 𝑓(𝑘, 𝑗, 𝑘 − 1)
ü Si non 𝑓 𝑖, 𝑗, 𝑘 = 𝑓(𝑖, 𝑗, 𝑘 − 1)
üEt donc, 𝑓(𝑖, 𝑗, 𝑘) est le minimum de ces deux quantités
27
üIl s’ensuit que :
ü𝑓 𝑖, 𝑗, 0 = 𝑐𝑜𝑠𝑡(𝑖 , 𝑗)
ü𝑓 𝑖, 𝑗, 𝑘 = min( 𝑓 𝑖, 𝑘, 𝑘 − 1 + 𝑓 𝑘, 𝑗, 𝑘 − 1 , 𝑓 𝑖, 𝑗, 𝑘 − 1 )
üDepuis les valeurs 𝑓 . , . , 𝑘 − 1 , les valeurs 𝑓(. , . , 𝑘) sont calculés

ü Il est nullement nécessaire de garder une matrice séparée pour chaque k, il est
plutôt judicieux de remplacer les valeurs existantes
28
Procedure FloydWarshallWithPathReconstruction (G = (S, A))

Begin
//intialize dist[i][j] to ∞ and dist[i][i] to 0
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
next[u][v] ← v
for k from 1 to |S| // standard Floyd-Warshall implementation
for i from 1 to |S|
for j from 1 to |S|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
next[i][j] ← next[i][k]
End
29
Procedure Path(u, v)
Begin
if next[u][v] = null then
return []
path ← [u]
while u ≠ v
u ← next[u][v]
path.append(u)
return path
End
30
üAlgorithme de Dijkstra
üNe marche que sur les graphes valués avec des poids positifs (sans
poids négatifs)
üCalcule les plus courts chemins entre un sommet particulier et les
autres sommets
üGénère un tableau d où 𝑑7 est la distance la plus courte du
sommet de départ au sommet 𝑖
üAlgorithme glouton
ü Idée similaire à l’algorithme de Prim
ü Peut être implémenté en 𝜣(𝒏𝟐 + 𝒎) ou 𝜣(𝒎 𝐥𝐨𝐠 𝒏) ou 𝜣(𝒏 𝒍𝒐𝒈 𝒏)
ü Choix glouton : trouver le plus proche sommet de s puis celui le proche de
ce dernier, …
31
Algorithm Dijkstra(G = (S, A), start)

Begin
𝐸 ← {𝑠𝑡𝑎𝑟𝑡} //a set to which the shortest distances are decided
d ← [|𝑆|] //𝑑? = 𝑐𝑜𝑠𝑡(𝑠𝑡𝑎𝑟𝑡, 𝑣) equals infinity if 𝑠𝑡𝑎𝑟𝑡, 𝑣 ∉ 𝐴
𝑠𝑖𝑛𝑐𝑒 ← [|𝑆|] //initialized to -1 except for start which is set to start
repeat until 𝐸 = 𝑆
find 𝑣 ∉ 𝐸 with the smallest 𝑑?
𝐸←𝐸∪ 𝑣
for each edge (𝑣, 𝑢) of cost c :
if (𝑑> > 𝑑? + 𝑐) then
𝑑> ← 𝑑? + 𝑐
𝑠𝑖𝑛𝑐𝑒[𝑢] ← 𝑣
End
32
üAlgorithme de Bellman-Ford
ü Calcule les plus courts chemins entre un sommet particulier et les autres sommets
ü Génère un tableau d où 𝑑7 est la distance la plus courte du sommet de départ
au sommet 𝑖
ü Peut détecter un cycle/circuit absorbant
ü S’exécute en une temps de 𝜣(𝒏𝒎)
ü Facile à coder
ü Applications :
ü Protocole de routage : Routing Information Protocol (version distribuée)
ü Systèmes d’inégalités linéaires sur les différences de variables
33
Algorithm Bellman-Ford(G = (S, A), start)

Begin
d ← [|𝑆|] //𝑑? = ∞ if v ≠ 𝑠𝑡𝑎𝑟𝑡 𝑎𝑛𝑑 𝑑ghijh = 0
for k ← 1 to n-1 do
𝑑> ← 𝑑? + 𝑐
Error negative-weight cycle/circuit detected
End
34
üUn plus court chemin peut avoir au plus n-1 arcs/arête
üA la kème itération, tous les plus court chemins de longueur k ou moins

ont été calculés
üAprès n-1 itération, les distances devraient être finales

üSi non il y a forcément un cycle/circuit absorbant d’où la dernière
boucle
35
ü Systèmes d’inégalités linéaires sur les différences de variables

ü Soient m inégalités de la forme 𝒙𝒊 − 𝒙𝒋 ≤ 𝒄𝒌 , trouver 𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 satisfaisant toutes les
inégalités
ü Graphe associé :
ü Créer un nœud i pour chaque variable 𝑥7
ü Créer une source imaginaire s
ü Créer des arcs à poids nulles depuis s vers les autres sommets
ü Réécrire les inégalités sous la forme de 𝒙𝒊 ≤ 𝒄𝒌 + 𝒙𝒋
ü Pour chaque contrainte, créer un arc depuis j vers i avec un poids c
ü Exécuter Bellman-Ford sur le graphe depuis le sommet s
36
üPour chaque arc de j vers i avec un coût c, le vecteur d des plus courts
chemins satisfera 𝒅𝒊 ≤ 𝒄 + 𝒅𝒋
üPrendre 𝒙𝒊 = 𝒅𝒊 pour trouver une solution au problème

üS’il y a un circuit absorbant:
ü Soit (1, 2, …, k, 1) ce circuit absorbant
ü D’après la construction du graphe, il s’en suivra :
𝒙𝟐 ≤ 𝒄𝟏 + 𝒙𝟏 ; 𝒙𝟑 ≤ 𝒄𝟐 + 𝒙𝟐 ; … ; 𝒙𝟏 ≤ 𝒄𝒌t𝟏 + 𝒙𝒌
ü En additionnant ces inégalités et en simplifiant, il s’ensuit
𝟎 ≤ 𝒑𝒐𝒊𝒅𝒔 𝒕𝒐𝒕𝒂𝒍 𝒅𝒖 𝒄𝒊𝒓𝒄𝒖𝒊𝒕 𝒂𝒃𝒔𝒐𝒓𝒃𝒂𝒏𝒕 𝒒𝒖𝒊 𝒆𝒔𝒕 𝒏é𝒈𝒂𝒕𝒊𝒇
ü Ce qui implique que le système d’inéquations est impossible à résoudre
37
üLa solution donnée par l’algorithme de Bellman-Ford aux systèmes

d’inégalités linéaires sur les différences de variables minimise l’écart
maximal entre les variable :
𝐦𝐚𝐱(𝒙𝒊 ) − 𝐦𝐢𝐧(𝒙𝒊 )
38
üTravaux dirigés : Implémentation de l’algorithme de Dijkstra

Algorithm Dijkstra(G = (S, A), start)
Begin
𝐸 ← {𝑠𝑡𝑎𝑟𝑡} //a set to which the shortest distances are decided
d ← [|𝑆|] //𝒅𝒗 = 𝒄𝒐𝒔𝒕(𝒔𝒕𝒂𝒓𝒕, 𝒗) equals infinity if 𝒔𝒕𝒂𝒓𝒕, 𝒗 ∉ 𝑨
repeat until 𝐸 = 𝑆
find 𝑣 ∉ 𝐸 with the smallest 𝑑?
𝐸←𝐸∪ 𝑣
𝑑> ← 𝑑? + 𝑐
End
39
ü Utiliser une file de priorité Q :

for each v ∈ S do
dv ← ∞; sincev ← null
dstart ← 0; Insert(Q, start, dstart) //update priority of start with dstart
VT ← Ø
while not Empty(Q) do
u* ← DeleteMin(Q) //delete the most important priority element (minimum cost)
VT ← VT U {u*}
for each vertex u in S – VT that is adjacent to u* do
if du* + w(u*, u) < du then
du ← du* + w(u*, u); sinceu ← u*
InsertOrUpdate(Q, u, du)
40
2
a b
5 6
2
8 c
f
3 1
d
4
7
e
41
2
a b
5
8 c
f
e b(a, 2) c(a, 5) d(a, 8) e(-, ∞) f(-, ∞)

a(-, 0)
42
2
a b
5 6
2
8 c
f
b(a, 2) e c(b, 2+2) d(a, 8) e(-, ∞ ) f(b, 2+6)
43
2
a b
5 6
2
8 c
f
3 1
d
c(b, 4) e d(c, 7) e(c, 4+1) f(b, 8)
44
2
a b
5 6
2
8 c
f
3 1
d
4
7
e(c, 5) e d(c, 7) f(b, 8)
45
2
a b
5 6
2
8 c
f
3 1
d
4
7
d(c, 7) e f(b, 8)
46
2
a b
6
2
c
f
3 1
d
47
üImplémentation Operation USDL 2-3 tree Heap Binomial Fibonacci

list*
de la file de priorité
make O(1) O(1) O(1) O(1) O(1)
empty O(1) O(1) O(1) O(1) O(1)
insert O(1) O(logn) O(logn) O(logn) O(1)
find_min O(n) O(logn) O(1) O(logn) O(1)
delete_min O(n) O(logn) O(logn) O(logn) O(logn)
delete O(1) O(logn) O(logn) O(logn) O(logn)
merge O(1) O(n) O(n) O(logn) O(1)
update_key O(1) O(logn) O(logn) O(logn) O(1)
© medbecha 2010-2016 * USDL list: Unsorted Doubly Linked list
48
üComplexité au pire de l’algorithme de Dijkstra :

𝑇 𝑛, 𝑚 = Θ 𝑛 × 𝑐𝑜û𝑡 𝑑𝑒 𝑑𝑒𝑙𝑒𝑡𝑒_ min + 𝑚 × 𝑐𝑜û𝑡 𝑑𝑒 𝑖𝑛𝑠𝑒𝑟𝑡/𝑢𝑝𝑑𝑎𝑡𝑒_𝑘𝑒𝑦
Où
n = la taille maximale de la file de priorité (nombre de sommets)
m = nombre de fois où la boucle interne est exécuté (nombre

d’arcs/d’arêtes)
49
üListe linéaïre doublement chainée :

𝑇(𝑛, 𝑚) = Θ( 𝑛×𝑛 + 𝑚×1) = Θ(𝑛2)
ü Arbre 2-3 :
𝑇(𝑛, 𝑚) = Θ(𝑛× log 𝑛 + 𝑚× log 𝑛) = Θ(𝑚 log 𝑛)
üTas de Fibonacci :
𝑇(𝑛, 𝑚) = Θ(𝑛× log 𝑛 + 𝑚×1) = Θ(𝑛 log 𝑛 + 𝑚)
50
void Dijkstra( int start ){

priority_queue<pair<ull,int>, vector<pair<ull,int>>,greater<pair<ull,int>>> Q;
Q.push(make_pair(0,start));
for(auto& d : dist) { d = numeric_limits<ull>::max(); } dist[start] = 0;
for(auto& f : from) { f = -1; } from[start] = start;
while (!Q.empty()){
pair<ull,int> u=Q.top();
Q.pop();
for(pair<ull,int>& v: graph[u.second]){
if (dist[u.second]+v.first < dist[v.second]) {
dist[v.second] = dist[u.second]+ v.first;
Q.push( make_pair( dist[v.second], v.second ) );
from[v.second] = u.second;
}
}
}
}
51
üTravaux Dirigés : systèmes linéaires d’inégalités :

üLa résolution par Bellman-Ford requiert que tous les inégalités soient
de la forme 𝒙𝒊 − 𝒙𝒋 ≤ 𝒄𝒌
üQue se passe-t-il si ce n’est pas le cas :
üL’inégalité 𝒙𝒊 < 𝒙𝒋 devient 𝒙𝒊 − 𝒙𝒋 ≤ 𝟏 (ou -1 selon les cas)
üL’inégalité 𝒙𝒊 + 𝒙𝒋 > 𝟎 devient −𝒙𝒊 − 𝒙𝒋 ≤ 𝟏 (ou -1 selon les cas)
𝒙𝒊 − 𝒙𝒋 ≤ 1
üL’égalité 𝒙𝒊 = 𝒙𝒋 devient ‘
𝒙𝒋 − 𝒙𝒊 ≤ 1
52
üRésoudre le système d’inégalités suivant:
𝑥’ − 𝑥2 ≤ 0
𝑥’ − 𝑥“ ≤ −1
𝑥2 − 𝑥“ ≤ 1
𝑥” − 𝑥’ ≤ 5
𝑥– − 𝑥’ ≤ 4
𝑥– − 𝑥” ≤ −1
𝑥“ − 𝑥” ≤ −3
𝑥“ − 𝑥– ≤ −3
53
üLe graphe des contraintes :
54
üAlgorithm Bellman-Ford(G = (S, A), start)

Begin
d ← [|𝑆|] //𝒅𝒗 = ∞ 𝐢𝐟 𝒗 ≠ 𝒔𝒕𝒂𝒓𝒕 𝒂𝒏𝒅 𝒅𝒔𝒕𝒂𝒓𝒕 = 𝟎
for k ← 1 to n-1 do
𝑑> ← 𝑑? + 𝑐
//Error negative-weight cycle/circuit detected
End
55
üLa solution :
56
TRI TOPOLOGIQUE
üEntrée : un graphe orienté acyclique (DAG) G = (S, A)
üSortie : un ordre partiel des sommets tel que ∀ (𝑢, 𝑣) ∈ 𝐴 𝑢 vient avant 𝑣 dans
l’ordre
üIl peut exister plusieurs solutions :
ü {6, 1, 3, 2, 7, 4, 5, 8} et {1, 6, 2, 3, 4, 5, 7, 8} sont deux ordres possibles pour ce
graphe:
57
TRI TOPOLOGIQUE
ü Pré-calculer le degré entrant deg(𝑣) de chaque sommet 𝑣
ü Mettre tous les sommets ayant un degré zéro dans une file d’attente
ü Répéter tant que la file n’est pas vide :
ü Défiler un sommet 𝑣 de la file
ü Pour chaque arc de 𝑣 à 𝑢
ü Décrémenter deg(𝑢) (comme si on supprimait l’arc de v à u)
ü Si deg(𝑢) devient zéro alors enfiler 𝑢 dans la file d’attente
ü Les sommets sont défilés de la file d’attente dans un ordre topologique
ü Complexité : 𝜣(n+m)
58
SOUS-GRAPHES FORTEMENT CONNEXES
59
ALGORITHME DE KOSARAJU
üInitialiser un compteur 𝑐 ← 0
üTant qu’il y a des sommets sans labels:
ü Choisir un sommet v sans label arbitraire
ü Commencer un DFS récursif à partir de v
ü Marquer x comme visité
ü Appeler récursivement le DFS sur les voisins non visités de x
ü Incrémenter c et assigner à x le label c
ü Inverser la direction de tous les arcs et marquer tous les sommets comme non visités
ü Pour chaque sommet v non visité en commençant par celui avec le plus fort label
ü Commencer un DFS depuis v en marquant tous les sommets atteints comme visités les
labélisés comme appartenant au même sous-graphe fortement connexe
60
POINTS D’ARTICULATION
61
POINTS D’ARTICULATIONS
Procedure GetArticulationPoints(i, d)
visited[i] ← true ; depth[i] ← d ; low[i] ← d ; childCount ← 0 ; isArticulation ← false
for each ni in adj[i] do
if not visited[ni] then
parent[ni] ← i
GetArticulationPoints(ni, d + 1)
childCount ← childCount + 1
if low[ni] >= depth[i] then
isArticulation ← true
low[i] ← Min(low[i], low[ni])
else if ni <> parent[i] then
low[i] ← Min(low[i], depth[ni])
if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
then Output i as articulation point

Algorithmique II PDF

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique II PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Algorithmique II PDF

Transféré par

Droits d'auteur :

Formats disponibles

1

THÉORIE DES GRAPHES

üPropriétés des graphes

üReprésentations des graphes

üParcours des graphes

üProblèmes des plus courts chemins

PROPRIÉTÉS DES GRAPHES

PROPRIÉTÉS DES GRAPHES

PROPRIÉTÉS DES GRAPHES

PROPRIÉTÉS DES GRAPHES

REPRÉSENTATION DES GRAPHES

REPRÉSENTATION DES GRAPHES

REPRÉSENTATION DES GRAPHES

REPRÉSENTATION DES GRAPHES

REPRÉSENTATION DES GRAPHES

REPRÉSENTATION DES GRAPHES

üGraphe Orienté Acyclique (Directed Acyclic Graph (DAG)):

PARCOURS DES GRAPHES

PARCOURS DES GRAPHES

PARCOURS DES GRAPHES

PARCOURS DES GRAPHES

PARCOURS DES GRAPHES

PROBLÈMES DES PLUS COURTS CHEMINS

üEntrée : un graphe valué G = ( S, A )

PROBLÈMES DES PLUS COURTS CHEMINS

Les plus court chemins existent entre chaque pair de sommets

üG est non orienté et connexe ou G est orienté et fortement connexe

üG ne contient pas de cycle / circuit absorbant c.à.d. un cycle / circuit

PROBLÈMES DES PLUS COURTS CHEMINS

PROBLÈMES DES PLUS COURTS CHEMINS

Algorithm Floyd-Warshall (G = (S, A))

PROBLÈMES DES PLUS COURTS CHEMINS

üNotons 𝑓(𝑖, 𝑗, 𝑘) la plus courte distance de i à j en utilisant au plus k nœud

PROBLÈMES DES PLUS COURTS CHEMINS

üIl s’ensuit que :

üDepuis les valeurs 𝑓 . , . , 𝑘 − 1 , les valeurs 𝑓(. , . , 𝑘) sont calculés

PROBLÈMES DES PLUS COURTS CHEMINS

Procedure FloydWarshallWithPathReconstruction (G = (S, A))

PROBLÈMES DES PLUS COURTS CHEMINS

PROBLÈMES DES PLUS COURTS CHEMINS

PROBLÈMES DES PLUS COURTS CHEMINS

Algorithm Dijkstra(G = (S, A), start)

PROBLÈMES DES PLUS COURTS CHEMINS

PROBLÈMES DES PLUS COURTS CHEMINS

Algorithm Bellman-Ford(G = (S, A), start)

PROBLÈMES DES PLUS COURTS CHEMINS

üUn plus court chemin peut avoir au plus n-1 arcs/arête

üA la kème itération, tous les plus court chemins de longueur k ou moins

üAprès n-1 itération, les distances devraient être finales

PROBLÈMES DES PLUS COURTS CHEMINS

ü Systèmes d’inégalités linéaires sur les différences de variables

PROBLÈMES DES PLUS COURTS CHEMINS

üPrendre 𝒙𝒊 = 𝒅𝒊 pour trouver une solution au problème

PROBLÈMES DES PLUS COURTS CHEMINS

üLa solution donnée par l’algorithme de Bellman-Ford aux systèmes

PROBLÈMES DES PLUS COURTS CHEMINS

üTravaux dirigés : Implémentation de l’algorithme de Dijkstra

PROBLÈMES DES PLUS COURTS CHEMINS

ü Utiliser une file de priorité Q :