Algorithme du tri à bulles
initialisations : tableau de données D[i] 1 i n à trier selon l’ordre croissant ; i ← 1 ;
tant que i < n, faire :
i) pour j de n à i + 1 : si D[j] < D[j − 1], échanger D[j] et D[j − 1] ;
ii) i ← i + 1.
3. Graphes
Définitions
Un graphe est la donnée d’un ensemble S , fini et non vide, de sommets et d’un
ensemble A d’arcs : un arc est une paire {a, b} de sommets. Si {a, b} est un arc,
on dit que les sommets a et b sont adjacents ou joints par un arc et l’on note
a, b
ou
b, a l’arc joignant ces sommets.
a
b
c
d
e
figure 1
On peut visualiser un graphe par un dessin : les sommets sont représentés par des
points et si deux sommets sont adjacents, on les relie par une ligne.
Ci-contre le graphe de sommets S = {a,b,c,d,e} ayant pour arcs
a, b,
a, c,
b, c,
c, d,
d, e,
b, d . Les sommets b et c sont adjacents,
de même que c et d, mais les sommets a et d ne le sont pas,
c et e non plus.
Exemple. Les liaisons aériennes assurées par une compagnie définissent un graphe :
les sommets représentent les villes desservies et deux sommets sont adjacents s’il y
a une liaison entre les villes correspondantes.
Le degré d’un sommet est le nombre d’arcs passant par ce sommet. Puisque chaque
arc passe par exactement deux sommets, la somme des degrés vaut deux fois le
nombre d’arcs.
Définitions
Soit G un graphe.
® Un chemin est une suite s 1 ,s 2 ,. . .,s n de sommets adjacents deux à deux différents ;
le premier sommet est l’origine du chemin et le dernier est l’extrémité.
® Le graphe G est connexe si deux sommets différents peuvent toujours être reliés
par un chemin.
® Soit s 1 , s 2 , . . . , s n un chemin. Si n 3 et si s n est adjacent à s 1 , on dit que
(s 1 , s 2 , . . . , s n , s 1 ) est un cycle.
Exemple. Dans le graphe de la figure 1, (a, b, c, d, e) et (a, b, d, c) sont des chemins,
(a, c, d, b, a) est un cycle ; le graphe est connexe.
78 – GRAPHES
initialisations : tableau de données D[i] 1 i n à trier selon l’ordre croissant ; i ← 1 ;
tant que i < n, faire :
i) pour j de n à i + 1 : si D[j] < D[j − 1], échanger D[j] et D[j − 1] ;
ii) i ← i + 1.
3. Graphes
Définitions
Un graphe est la donnée d’un ensemble S , fini et non vide, de sommets et d’un
ensemble A d’arcs : un arc est une paire {a, b} de sommets. Si {a, b} est un arc,
on dit que les sommets a et b sont adjacents ou joints par un arc et l’on note
a, b
ou
b, a l’arc joignant ces sommets.
a
b
c
d
e
figure 1
On peut visualiser un graphe par un dessin : les sommets sont représentés par des
points et si deux sommets sont adjacents, on les relie par une ligne.
Ci-contre le graphe de sommets S = {a,b,c,d,e} ayant pour arcs
a, b,
a, c,
b, c,
c, d,
d, e,
b, d . Les sommets b et c sont adjacents,
de même que c et d, mais les sommets a et d ne le sont pas,
c et e non plus.
Exemple. Les liaisons aériennes assurées par une compagnie définissent un graphe :
les sommets représentent les villes desservies et deux sommets sont adjacents s’il y
a une liaison entre les villes correspondantes.
Le degré d’un sommet est le nombre d’arcs passant par ce sommet. Puisque chaque
arc passe par exactement deux sommets, la somme des degrés vaut deux fois le
nombre d’arcs.
Définitions
Soit G un graphe.
® Un chemin est une suite s 1 ,s 2 ,. . .,s n de sommets adjacents deux à deux différents ;
le premier sommet est l’origine du chemin et le dernier est l’extrémité.
® Le graphe G est connexe si deux sommets différents peuvent toujours être reliés
par un chemin.
® Soit s 1 , s 2 , . . . , s n un chemin. Si n 3 et si s n est adjacent à s 1 , on dit que
(s 1 , s 2 , . . . , s n , s 1 ) est un cycle.
Exemple. Dans le graphe de la figure 1, (a, b, c, d, e) et (a, b, d, c) sont des chemins,
(a, c, d, b, a) est un cycle ; le graphe est connexe.
78 – GRAPHES