Vocabulaire

Représentations matricielles
Sous-graphes
Cheminement
Encodage

Algorithmique de graphes
Notions de base

Sophie Toulouse

20 septembre 2019

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Graphe

Définition (graphe)
Un graphe est un couple (V , E ) où :
V est un ensemble de points appelés sommets du graphe
E est un ensemble de liaisons entre des paires de points, appelées
arêtes

Vocabulaire / notations :
le nombre |V | de sommets est appelé ordre du graphe
les cardinalités |V | et |E | sont usuellement notées n et m

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Illustration

v1

e1 e2
v4 e4
G = (V , E ) : v2
e6 e7
e5
e3
G est un graphe d’ordre 4 où : v3
V = {v1 , v2 , v3 , v4 }
E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 } où :
e1 = {v1 , v4 } (aussi notée v1 v4 , mais encore {v4 , v1 } ou v4 v1 )
e2 = {v1 , v2 } (aussi notée {v2 , v1 }, v1 v2 ou v2 v1 )
...

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Arêtes particulières

Définition (boucle)
Les sommets extrémités d’une arête peuvent être les mêmes. L’arête est
alors appelée boucle.

Définition (arêtes parallèles ou arête multiple)

Entre deux sommets, il peut exister plusieurs arêtes. On parle alors
d’arêtes parallèles (ou d’arête multiple).
v1

e1 e2
v4 e6 est une boucle
e4
Exemple : v2
les arêtes e3 et e7 sont
e6 e7
e5
e3
parallèles
v3
Sophie Toulouse Algorithmique de graphes
 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Adjacence, incidence

Définition (incidence et adjacence dans un graphe)

Deux sommets u, v ∈ V sont adjacents s’ils sont reliés par une arête.
Un sommet v et une arête e sont incidents si v est une extrémité de
e.
Deux arêtes sont adjacentes si elles ont une extrémité commune.

v1

e1 e2 v1 et v2 sont adjacents
v4 e4
Exemple : v2 e1 et v1 sont incidents
e6 e7
e5 e1 et e2 sont adjacentes
e3
v3

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Voisins (d’un sommet)

Définition (voisins d’un sommet)

L’ensemble des sommets adjacents à un sommet v est appelé
ensemble des voisins de v . On note Γ(v ) cet ensemble.

v1

e1
Γ(v1 ) = {v2 , v3 , v4 }
e2
v4 e4 Γ(v2 ) = {v1 , v3 }
Exemple : v2
e6 e7 Γ(v3 ) = {v1 , v2 , v4 }
e5
e3
Γ(v4 ) = {v1 , v3 , v4 }
v3

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Degré (d’un sommet)

Définition (degré)
Le degré d’un sommet est le nombre de fois qu’il est incident à une arête.
On note d(v ) le degré d’un sommet v .

v1

e1
d(v1 ) = 3
e2
v4 e4 d(v2 ) = 3
Exemple : v2
e6 e7 d(v3 ) = 4
e5
e3
d(v4 ) = 4
v3

Remarque : une boucle contribue 2 fois au degré du sommet concerné

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Graphe simple

Rappel :
une boucle est une arête dont les deux extrémités coïncident
deux arêtes sont parallèles si elles relient les deux mêmes sommets

Définition (graphe simple)

Un graphe simple est un graphe qui ne ne contient ni boucle, ni arêtes
parallèles.

Propriété
Dans un graphe simple, le degré d’un sommet v est pécisément le
nombre |Γ(v )| de ses voisins.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Graphe complet

Définition (graphe complet)

Un graphe simple est complet s’il existe une arête entre chaque paire de
sommets. Le graphe complet d’ordre n est noté Kn .

Exemples : K4 K5

Remarque : dans Kn , tous les sommets sont de même degré n − 1

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sommets, arêtes
Sous-graphes Adjacence, incidence
Cheminement Graphes particuliers
Encodage

Graphe biparti

Définition (graphe biparti)

Un graphe G = (V , E ) est biparti s’il existe une partition de son
ensemble de sommets en deux ensembles L et R tels que toute arête de
E a l’une de ses extrémités dans L et l’autre dans R.

Exemples :

Remarques :
un graphe biparti ne contient pas de boucle
siP
toute arête de G
P a une extrémité dans L et l’autre dans R, alors
v∈L d(v ) = v∈R d(v ) = |E |

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Matrice d’adjacence
Sous-graphes
Matrice d’incidence
Cheminement
Encodage

Matrice d’adjacence (entre sommets)

Définition (matrice d’adjacence)

La matrice d’adjacence associée à un graphe G = (V , E ) est une matrice
carrée |V | × |V | dont les lignes et les colonnes sont indicées par les
sommets v ∈ V . Cette matrice A(G ) = (auv )u∈V ,v∈V est définie par :

auv = nombre d’occurrences de l’arête {u, v } dans G , u, v ∈ V

Remarque : {u, v } ou {v , u}, c’est la même chose ...

Propriété
La matrice d’adjacence d’un graphe (non orienté) est symétrique.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Matrice d’adjacence
Sous-graphes
Matrice d’incidence
Cheminement
Encodage

Exemple

Rappel : A(G ) = (auv )u∈V ,v∈V où pour u, v ∈ V , auv = nombre

d’occurrences de l’arête {u, v } dans G

v1 v2
e7 e1 v1 v2 v3 v4 v5
v1 1 1 0 1 0
v5 v2 1 0 2 1 0
e6 e3 e4
e8 v3 0 2
e10 e2
e9 v4 1 1
v4 e5 v3 v5 0 0

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Matrice d’adjacence
Sous-graphes
Matrice d’incidence
Cheminement
Encodage

Matrice d’incidence (entre sommets et arêtes)

Définition (matrice d’incidence)

La matrice d’incidence associée à un graphe G = (V , E ) est une matrice
|V | × |E | dont les lignes sont indicées par les sommets v ∈ V et les
colonnes sont indicées par les arêtes e ∈ E . Cette matrice
B(G ) = (bve )v∈V ,e∈E est définie par :

 2 si e est la boucle vv
bve = 1 si e est une arête {u, v } où u 6= v , v ∈ V , e ∈ E
0 sinon


Remarques :
sur une ligne v , la somme des coefficients vaut d(v )
sur une colonne e, la somme des coefficients vaut 2
Sophie Toulouse Algorithmique de graphes
 Vocabulaire
Représentations matricielles
Matrice d’adjacence
Sous-graphes
Matrice d’incidence
Cheminement
Encodage

Exemple
v1 v2
e7 e1

v5
e6 e3 e4
e8
e10 e2
e9
v4 e5 v3

B(G ) e1 e2 e3 e4 e5 e6 e7 e8 e9 e10
v1 1 0 0 0 0 1 2 0 0 0
v2 1 1 1 1 0 0 0 0 0 0
v3 0 0
v4 0 0
v5 0 0

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Matrice d’adjacence
Sous-graphes
Matrice d’incidence
Cheminement
Encodage

Représentations matricielles et graphes particuliers

G est sans boucle ssi A(G )

G est sans boucle ssi B(G )

G est simple ssi A(G )

si G est le graphe complet, alors A(G )

si G est le graphe complet, alors B(G )

si G est biparti, alors A(G )

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sous-graphe
Sous-graphes Sous-graphe partiel
Cheminement Sous-graphe induit
Encodage

Sous-graphe
Définition (sous-graphe)
Si G = (V , E ) est un graphe, on appelle sous-graphe de G tout graphe
H = (W , F ) où W ⊆ V et F ⊆ E .

v3

Illustration : e3 e5
v1 v2 v4
e2 e4
G = e6
e1 e8 e7
(V , E ) e9
v6 v5

W = {v2 , v3 , v4 , v5 } W = {v2 , v4 , v5 } W = {v0 , v4 } W = {v2 , v4 }

F = {e4 , e6 } F = {e4 , e6 } F = {e6 } F = {e6 , v2 v4 }
OK KO (pas un graphe !) KO v0 KO v2 v4

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sous-graphe
Sous-graphes Sous-graphe partiel
Cheminement Sous-graphe induit
Encodage

Sous-graphe partiel
Définition (sous-graphe partiel)
Un sous-graphe H = (W , F ) d’un graphe G = (V , E ) où W = V est
appelé sous-graphe partiel de G .

v3

e3 e5
Illustration : v1 v2 v4
e2 e4
e6
G = (V , E ) e1 e8 e7
e9
v6 v5

H1 = (V , ∅), H2 = (V , {e2 , e6 }), H3 = (V \{v6 }, {e2 , e6 }) sont des

sous-graphes de G
H1 et H2 sont des sous-graphe partiels de G , mais pas H3

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sous-graphe
Sous-graphes Sous-graphe partiel
Cheminement Sous-graphe induit
Encodage

Sous-graphe induit (par les sommets)

Définition (sous-graphe induit)

Un sous-graphe H = (W , F ) d’un graphe G = (V , E ) est un
sous-graphe induit de G si F est précisément l’ensemble des arêtes de E
qui ont leurs deux extrémités dans W . On dit alors que H est le
sous-graphe induit par W , noté G [W ].

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Sous-graphe
Sous-graphes Sous-graphe partiel
Cheminement Sous-graphe induit
Encodage

Illustration

v3

e3 e5
v1 v2 v4
e2 e4
G = (V , E ) e1
e6
e8 e7
e9
v6 v5

H = ({v3 , v4 , v5 }, {e4 , e5 , e6 , e7 }) est un sous-graphe induit de G

H = ({v2 , v3 , v5 }, {e3 , e4 , e8 }) n’est pas un sous-graphe induit de G

si W = {v2 , v4 , v5 , v6 }, G [W ] =

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Chaîne

Définition (chaîne)
Une chaîne γ dans un graphe est une suite alternée

(v1 , e1 , v2 , e2 , v3 , e3 , . . . , vℓ , eℓ , vℓ+1 , . . . , vk , ek , vk+1 )

de sommets et d’arêtes de G vérifiant pour tout ℓ ∈ {1, . . . , k} que eℓ est

l’arête {vℓ , vℓ+1 }.

Le nombre k est appelé longueur de γ.

Les deux suites (v1 , e1 , v2 , . . . , vk , ek , vk+1 ) et (vk+1 , ek , vk , . . . , v2 , e1 , v1 )

décrivent la même chaîne.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Remarques

Remarque : une chaîne peut emprunter plusieurs fois une même arête.

Remarque : quand les arêtes {vℓ , vℓ+1 }, ℓ ∈ {1, . . . , k} existent toutes en

un seul exemplaire dans G , la chaîne est totalement spécifiée par la suite
de ses sommets. On la note alors (v1 , v2 , . . . , vk+1 ) (ou
(vk+1 , vk , . . . , v1 )).

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Illustration

v1 v2
e1
(v1 , e1 , v2 ) (ou (v1 , v2 ), mais aussi (v2 , e1 , v1 ) ou
(v2 , v1 )) est une chaîne de longueur 1
e3 (v1 , e1 , v2 , v5 , e7 , v4 ) n’est pas une chaîne
e2 e4
(v1 , e1 , v2 , e3 , v3 , e4 , v2 ) est une chaîne de
longueur 3
v5 v3
e8 (v5 , e7 , v4 , e6 , v4 , e5 , v3 , e5 , v4 , e6 , v4 ) (ou
(v5 , v4 , v4 , v3 , v4 , v4 )) est une chaîne de longueur
e5 5
e7
(v4 ) est une chaîne de longueur 0

v4 ni (v1 , e2 , v4 ), ni (v1 , v4 ) ne sont des chaînes

e6
(v2 , v3 ) ne spécifie pas une chaîne (s’agit-il de
G = (V , E ) (v2 , e3 , v3 ), ou de (v2 , e4 , v3 ) ?)

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Cycle

Définition (cycle)
Un cycle est une chaîne (v1 , e1 , v2 , . . . , vk , ek , vk+1 ) où vk+1 = v1 .

Remarque : une boucle est un cycle de longueur 1.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Illustration

v1 v2
e1

e3 la chaîne (v4 , v4 ) est un cycle de longueur 1

e2 e4
les chaînes (v4 , v4 , v4 ), (v1 , v2 , v1 ),
(v2 , e3 , v3 , e4 , v2 ) sont des cycles de longueur 2
v5 v3
la chaîne (v4 , v4 , v3 , v4 , v4 ) est un cycle de
e8 longueur 4
e5 la chaîne (v1 , e1 , v2 , e3 , v3 , e2 , v1 ) est un cycle de
e7 longueur 3
la chaîne (v1 , e1 , v2 , e3 , v3 , e2 , v1 , e2 , v3 ) n’est pas
v4 e6 un cycle

G = (V , E )

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Cycles et graphes bipartis

Théorème
Un graphe est biparti si et seulement s’il ne contient pas de cycle de
longueur impaire.

Démonstration ⇒.
Supposons que G est biparti et contient un cycle de longueur impair
(v1 , e1 , v2 , . . . , v2k+1 , e2k+1 , v1 ). Alors . . .

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Chaînes et cycles simples

Définition (chaîne simple)

Une chaîne (qui peut être un cycle) est simple si elle ne passe pas deux
fois par une même arête.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Illustration

v1 v2
e1

e3
e2 e4
le cycle (v2 , e3 , v3 , e4 , v2 ) est simple, le cycle
(v2 , e3 , v3 , e3 , v2 ) ne l’est pas
v5 v3
la chaîne (v5 , v4 , v4 , v3 ) est simple, les chaînes
e8 (v5 , v4 , v4 , v4 , v3 ) et (v5 , v4 , v4 , v3 , v4 ) ne le sont
pas
e5
e7 les cycles (v4 ) et (v4 , v4 ) sont simples, le cycle
(v4 , v4 , v4 ) ne l’est pas
v4 e6

G = (V , E )

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Chaînes et cycles eulériens, graphe eulérien

Définition (parcours eulérien)

Une chaîne (qui peut être un cycle) simple est eulérienne si elle parcourt
toutes les arêtes du graphe.

Remarque : une chaîne eulérienne est de longeur |E |

Définition (graphe eulérien)

Un graphe est eulérien s’il admet un cycle eulérien.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Illustration

v1 v2
e1

e3
e2 e4

(v2 , e1 , v1 , e2 , v3 , e3 , v2 , e4 , v3 , e8 , v3 , e5 , v4 , e6 , v4 , e7 , v5 )
v5 v3
est une chaîne eulérienne de G
e8
G n’est pas eulérien
e5
e7
G [{v2 , v3 }] est eulérien

v4 e6

G = (V , E )

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Graphes eulériens et degrés

Théorème
Un graphe est eulérien si et seulement si ses sommets sont tous de degré
pair.

Démonstration ⇒.
Par hypothèse, on peut regarder E comme un cycle simple (v1 , e1 , v2 , . . . , vm+1 = v1 ).

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Chaînes et cycles élémentaires

Définition (chaîne élémentaire)

Une chaîne γ = (v1 , e1 , v2 , . . . , vk , ek , vk+1 ) est élémentaire si, partant de
v1 , elle ne revient jamais sur un sommet déjà visité, sauf peut-être en
vk+1 qui peut être égal à v1 (auquel cas γ est un cycle élémentaire).

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Illustration

v1 v2
e1

e3
e2 e4
la chaîne (v4 , e5 , v3 , e3 , v2 , e4 , v3 ) est simple, mais
pas élémentaire
v5 v3
la chaîne (v4 , e5 , v3 , e3 , v2 ) est élémentaire
e8
la cycle (v3 , e3 , v2 , e4 , v3 , e8 , v3 ) est simple, mais
e5 pas élémentaire
e7
la cycle (v3 , e3 , v2 , e4 , v3 ) est élémentaire
v4 e6

G = (V , E )

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Chaînes et cycles élémentaires

Rappel :
Une chaîne simple ne passe pas deux fois par une même arête
Une chaîne élémentaire, quand on la parcourt, ne revient jamais sur
un sommet déjà visité (sauf s’il s’agit du premier et du dernier
sommet visités)

Propriété
Une chaîne (dont un cycle) élémentaire est simple.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Chaînes et cycles hamiltoniens, graphe hamiltonien

Définition (chaîne hamiltonienne)

Une chaîne élémentaire est hamiltonienne si elle parcourt tous les
sommets du graphe.

Remarque :
une chaîne hamiltonienne d’un sommet u à un sommet v 6= u est de
longeur |V | − 1
un cycle hamiltonien est de longeur |V |

Définition (graphe hamiltonien)

Un graphe est hamiltonien s’il admet un cycle hamiltonien.

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles Chaînes, cycles
Sous-graphes Chaînes et cycles simples
Cheminement Chaînes et cycles élémentaires
Encodage

Illustration

v1 v2
e1

e3
e2 e4

v5 v3 (v5 , e7 , v4 , e5 , v3 , e2 , v1 , e1 , v2 ) est une chaîne

e8 hamiltonienne de G

e5 G [{v1 , v2 , v3 }] est hamiltonien

e7

v4 e6

G = (V , E )

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Sous-graphes
Cheminement
Encodage

Représentation des graphes en machine

On peut – notamment – représenter E par

sa matrice d’adjacence : tableau de n × n entiers
les listes d’adjacence des sommets : on distingue deux
représentations, tabulaire ou par listes chaînées

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Sous-graphes
Cheminement
Encodage

Listes d’adjacence : avec des tableaux

on liste dans un premier tableau LS les voisins du sommet 1, puis

ceux du sommet 2, etc.
on utilise deux tableaux DEB et FIN pour stocker les indices, dans
LS, auxquels commence et s’arrête la lecture des voisins de chaque
sommet

Encombrement mémoire :
les tableaux DEB et FIN sont de dimension n
le tableau LS est de dimension
⇒ O(m + n) espace mémoire

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Sous-graphes
Cheminement
Encodage

Illustration
v1

e1 e2
v4 e4
G = (V , E ) v2
e6 e7
e5
e3
v3

On stocke dans LS les voisins de v1 , puis de v2 , ... :

1 2 3 4 5 6 7 8 9 10 11 12 13
4 2 3 1 3 3 LS

On stocke dans DEB et FIN les indices 1 et 3 pour v1 , puis 4 et 6 pour v2 , ... :
1 2 3 4
1 4 DEB
3 6 FIN

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Sous-graphes
Cheminement
Encodage

Listes d’adjacence : avec des listes chaînées

on associe à chaque sommet une liste chaînée, dont les maillons

contiennent des identifiants de sommets
on stocke ces listes dans un tableau

Encombrement mémoire :
le tableau des listes est de dimension n
le nombre total de maillons manipulés dans les listes est
⇒ O(m + n) espace mémoire

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Sous-graphes
Cheminement
Encodage

Illustration

v1

e1 e2
v4 e4
G = (V , E ) v2
e6 e7
e5
e3
v3

Sophie Toulouse Algorithmique de graphes

 Vocabulaire
Représentations matricielles
Sous-graphes
Cheminement
Encodage

Discussion

Matrice d’adjacence vs. listes d’adjacence

+ matrice adjacence : ajout/suppression d’arêtes
+ listes d’adjacence : occupation mémoire

Tableaux vs. listes chaînées

+ tableaux : parcours des listes d’adjacence
+ listes chaînées : occupation mémoire
+ listes chaînées : ajout/suppression de sommets
+ listes chaînées : ajout/suppression d’arêtes

Sophie Toulouse Algorithmique de graphes