G RAPHE

Mathieu S ABLIK
 Table des matières

I Différentes notions de graphes 5

I.1 Différents problèmes à modéliser . . . . . . . . . . . . . . . . . . . . . . . . . 5
I.2 Différentes notions de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 6
I.2.1 Graphe orienté ou non . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
I.2.2 Isomorphisme de graphe . . . . . . . . . . . . . . . . . . . . . . . . . 8
I.2.3 Degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
I.2.4 Construction de graphes à partir d’un autre . . . . . . . . . . . . . . 10
I.3 Différents modes de représentation d’un graphe . . . . . . . . . . . . . . . . 10
I.3.1 Représentation sagittale . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I.3.2 Définition par propriété caractéristique . . . . . . . . . . . . . . . . . 10
I.3.3 Listes d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I.3.4 Matrices d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I.3.5 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
I.3.6 Comparaison des différentes méthodes . . . . . . . . . . . . . . . . . 12
I.4 Quelques classes de graphe importantes . . . . . . . . . . . . . . . . . . . . . 12
I.4.1 Graphes isolés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
I.4.2 Graphes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I.4.3 Graphes complets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I.4.4 Graphe biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I.4.5 Graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I.4.6 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

II Problèmes de chemins dans un graphe 15

II.1 Notion de chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.1.2 Longueur d’un chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.2 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
II.3 Graphe k-connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
II.4 Chemin Eulérien et Hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . 19
II.4.1 Chemin Eulérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
II.4.2 Chemins hamiltonien . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
II.5 Caractérisation des graphes bipartis . . . . . . . . . . . . . . . . . . . . . . . 22
TABLE DES MATIÈRES 2

III Graphes acycliques ou sans-circuits 25

III.1 Notion d’arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
III.1.1 Nombre d’arêtes d’un graphe acyclique . . . . . . . . . . . . . . . . . 25
III.1.2 Arbres et forêts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
III.1.3 Arbres orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
III.1.4 Notion de rang dans un graphe orienté sans circuit . . . . . . . . . . 28
III.2 Initiation à la théorie des jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
III.2.1 Jeux combinatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
III.2.2 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
III.2.3 Noyau d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
III.2.4 Exemples de jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
III.3 Parcours dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
III.3.1 Notion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
III.3.2 Parcours en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.3.3 Parcours en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . . 34

IV Problèmes de coloriages 37
IV.1 Coloriage de sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
IV.1.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
IV.1.2 Exemples d’applications . . . . . . . . . . . . . . . . . . . . . . . . . . 37
IV.1.3 Nombre chromatique de graphes classiques . . . . . . . . . . . . . . 38
IV.2 Résolution algorithmique pour le coloriage de sommets . . . . . . . . . . . . 38
IV.2.1 Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
IV.2.2 Algorithme de Welsh-Powell . . . . . . . . . . . . . . . . . . . . . . . 39
IV.2.3 Existe t’il un algorithme pour trouver le nombre chromatique d’un
graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
IV.3 Encadrement du nombre chromatique . . . . . . . . . . . . . . . . . . . . . . 41
IV.4 Coloration des arêtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.5 Théorie de Ramsey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

V Graphes planaires 47
V.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
V.2 Le théorème de Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
V.3 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
V.4 Croisements, épaisseur et genre . . . . . . . . . . . . . . . . . . . . . . . . . . 50

VI Un peu de théorie algébrique des graphes 53

VI.1 Matrice d’adjacence et chemin dans un graphe . . . . . . . . . . . . . . . . . 53
VI.1.1 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
VI.1.2 Nombre de chemin de longueur n . . . . . . . . . . . . . . . . . . . . 53
VI.1.3 Distance entre deux sommets et diamètre du graphe . . . . . . . . . 53
VI.2 Théorie de Perron-Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
VI.3 Deux mots sur le Page-rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

VIIProblèmes d’optimisation pour des graphes valués 55

VII.1 Recherche d’arbre couvrant de poids maximal/minimal . . . . . . . . . . . . 55
VII.1.1 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
VII.1.2 Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
VII.1.3 Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3 Table des Matières

VII.2 Problème de plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . 58

VII.2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
VII.2.2 Principe des algorithmes étudiés . . . . . . . . . . . . . . . . . . . . . 59
VII.2.3 Algorithme de Bellman-Ford-Kalaba . . . . . . . . . . . . . . . . . . . 59
VII.2.4 Algorithme de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . 61
VII.2.5 Algorithme de Dijkstra-Moore . . . . . . . . . . . . . . . . . . . . . . 62
VII.2.6 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
VII.2.7 Ordonnancement et gestion de projet . . . . . . . . . . . . . . . . . . 64
VII.3 Flots dans les transports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
VII.3.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
VII.3.2 Lemme de la coupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
VII.3.3 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . 67
TABLE DES M ATIÈRES 4
 Chapitre I
Différentes notions de graphes

I.1 Différents problèmes à modéliser

On peut considérer que l’article fondateur de la théorie des graphe fut publié par le
mathématicien suisse Leonhard Euler en 1741. Il traitait du problème des sept ponts de
Königsberg : est il possible de réaliser une promenade dans la ville de Königsberg partant
d’un point donné et revenant à ce point en passant une et une seule fois par chacun des
sept ponts de la ville ?
Cette théorie va connaitre un essor au cours du XIX ème par l’intermédiaire du pro-
blème suivant : quel est le nombre minimal de couleurs nécessaires pour colorier une
carte géographique de telle sorte que deux régions limitrophe n’ont pas la même cou-
leur ? Le théorème des quatre couleurs affirme que seulement quatre sont nécessaires. Le
résultat fut conjecturé en 1852 par Francis Guthrie, intéressé par la coloration de la carte
des régions d’Angleterre, mais ne fût démontré qu’en 1976 par deux Américains Kenneth
Appel et Wolfgang Haken. Ce fut la première fois que l’utilisation d’un ordinateur a per-
mis de conclure leur démonstration en étudiant les 1478 cas particulier auxquels ils ont
ramené le problème.
Au XX ème siècle, la théorie des graphes va connaître un essor croissant avec le déve-
loppement des réseaux dont il faut optimiser l’utilisation. On peut citer quelques exemples
de manière non exhaustive :
— réseaux de transports routier, d’eau, d’électricité : les sommets représentent les car-
refours et les arêtes les rues ;
— réseaux informatiques : les sommets représentent les ordinateurs et les arêtes les
connexions physiques ;
— réseaux sociaux : les sommets représentent les membres du groupe, deux per-
sonnes sont reliées par une arête si elles se connaissent (Facebook : graphe non
orienté, twiter : graphe orienté, combien de poignées de main on est du président ?. . .
);
— graphe du web : les sommets représentent les pages web et chaque arc correspond
a un hyperliens d’une page vers une autre ;
— réseau de transports de données (téléphonie, wifi, réseaux informatique. . . ) ;
— représentation d’un algorithme, du déroulement d’un jeu ;
— réseaux de régulation génétique ;
 Chapitre I. D IFFÉRENTES NOTIONS DE GRAPHES 6

— organisation logistique : les sommets représentent des évènements, deux évène-

ments sont reliées par une arête s’ils ne peuvent pas avoir lieu en même temps ;
— ordonnancement de projet : les sommets représentent les différentes tâches com-
posant un projet, deux tâches sont reliés par une flèche si la deuxième ne peut pas
commencer avant que la première soit terminée ;
— et beaucoup d’autres encore. . .
L’étude des graphes se réalise sous deux point de vues complémentaire. L’étude de
propriétés structurelles de graphes ou de familles de graphes et l’étude algorithmique de
certaines propriétés.

I.2 Différentes notions de graphes

I.2.1 Graphe orienté ou non
Dans les exemples que l’on a vus, un graphe est un ensemble fini de sommets reliés
par des arêtes. Ces arêtes peuvent être orientées ou non, de plus une valeur peut être
associée à chaque arête ou aux sommets.

Définition I.1. Un graphe orienté G = (S, A) est la donnée :

— d’un ensemble S dont les éléments sont des sommets ;
— d’un ensemble A ⊂ S × S dont les éléments sont les arcs.
Un arc a = (s, s0 ) est aussi noté s → s0 , s est l’origine de a et s0 l’extrémité. On dit aussi
que s0 est le successeur de s et s le prédécesseur de s0 .
On peut souhaiter qu’il y ait plusieurs arcs entre deux mêmes sommets. On parle alors
de graphe orienté multi-arcs. Formellement, G = (S, A, i, f) c’est la donnée :
— d’un ensemble S dont les éléments sont des sommets ;
— d’un ensemble A dont les éléments sont les arcs ;
— de deux fonctions i : A → S et f : A → S qui à chaque arcs a ∈ A associe son
prédécesseur i( a) et son successeur f( a).

Exemple I.1. Exemple de graphe orienté :

1 2 G = (S, A) où
— S = {1, 2, 3, 4},
— A = {(1, 2), (2, 1), (2, 4), (3, 4), (3, 3)}.

4 3

Exemple de graphe orienté multi-arcs :

a
1 2 G = (S, A, i, f) où
b
— S = {1, 2, 3, 4},
c — A = { a, b, c, d, e, f , g, h},
d f a 7→ 1 a 7→ 2
b 7→ 2 b 7→ 1
4 e 3 g c 7→ 2 c 7→ 4
— i: d 7→ 2 et f : d 7→ 4 .
e 7→ 3 e 7→ 4
f 7→ 3 f 7→ 3
g 7→ 3 g 7→ 3

Définition I.2. Un graphe non orienté G = (S, A) est la donnée :

7 I.2. Différentes notions de graphes

— d’un ensemble S dont les éléments sont les sommets du graphe,

— d’un ensemble A dont les éléments, les arêtes du graphe, sont des parties à un
ou deux éléments de S.
Le ou les sommets d’une arête sont appelés extrémités de l’arête. Les arêtes n’ayant qu’une
seule extrémité sont des boucles.
On peut de la même façon un graphe non-orienté multi-arêtes. Formellement, G =
(S, A, α) est la donnée :
— d’un ensemble S dont les éléments sont des sommets ;
— d’un ensemble A dont les éléments sont les arêtes ;
— d’une fonction α de A dans les parties à un ou deux éléments de S.

Exemple I.2. Exemple de graphe non-orienté :

1 2 G = (S, A) où
— S = {1, 2, 3, 4},
— A = {{1, 2}, {2, 4}, {3, 4}, {3}}.

4 3

Exemple de graphe non orienté multi-arêtes :

a
1 2 G = (S, A, α) où
b
— S = {1, 2, 3, 4},
c — A = { a, b, c, d, e, f , g, h},
d f a 7→ {1, 2}
b 7→ {1, 2}
4 e 3 g c 7→ {2, 4}
— α: d 7→ {2, 4} .
e 7→ {3, 4}
f 7→ {3}
g 7→ {3}

Si un arc ou une arête à ses deux extrémités constituées du même sommet, on dit que
c’est une boucle.
Un graphe est simple s’il est non-orienté, s’il a au plus une arête entre deux sommets
et s’il n’a pas de boucle.
L’ordre d’un graphe est le nombre de sommets |S| et la taille d’un graphe est le nombre
d’arêtes ou d’arcs.
On appèle valuation sur les sommets (resp. sur les arcs ou arêtes) toutes fonctions pre-
nant en argument les sommets (resp. sur les arcs ou arêtes) et renvoyant un réels ou élé-
ment dans un ensemble donné.
Soit G = (S, A) un graphe orienté, on associe le graphe non orienté G 0 = (S, A0 ) ayant
le même ensemble de sommets S et dont l’ensemble d’arêtes A0 vérifie { x, y} ∈ A0 ⇐⇒
( x, y) ∈ A ou (y, x ) ∈ A.
Exemple I.3. Les trois graphes suivants

sont associés au graphe non orienté suivant

 Chapitre I. D IFFÉRENTES NOTIONS DE GRAPHES 8

I.2.2 Isomorphisme de graphe

Deux graphes orientés G = (S, A) et G 0 = (S0 , A0 ) sont isomorphes s’il existe une appli-
cation bijective ϕ : S → S0 telle que pour tout s, s0 ∈ S on (s, s0 ) ∈ A ⇐⇒ ( ϕ(s), ϕ(s0 )) ∈ A.
L’application ϕ est alors un isomorphisme de graphes orientés.
Exemple I.4. Les deux graphes suivants sont isomorphes par l’isomorphisme ϕ : 1 7→
A, 2 7→ B, 3 7→ C, 4 7→ D, 5 7→ E.

2 D
3 B

1 A

4 E
5 C

De même, deux graphes non-orientés G = (S, A) et G 0 = (S0 , A0 ) sont isomorphes s’il

existe une application bijective ϕ : S → S0 telle que pour tout s, s0 ∈ S on {s, s0 } ∈ A ⇐⇒
{ ϕ(s), ϕ(s0 )} ∈ A. L’application ϕ est alors un isomorphisme de graphes non-orientés.

I.2.3 Degré
Pour un graphe orienté, on appèle degré entrant d’un sommet s, noté d− (s) (resp. degré
sortant d’un sommet s, noté d+ (s)) le nombre d’arcs dont le sommet est successeur (resp.
prédécesseur).
Pour un graphe non-orienté, on appelle degré d’un sommet s, noté d(s) le nombre
d’arêtes dont le sommet est une extrémité.
Théorème I.1 Lemme de la poignée de main
Soit G = (S, A) un graphe orienté. On alors les égalités suivantes :
X X
d+ (s) = d − ( s ) = | A |.
s∈S s∈S

Soit G = (S, A) un graphe non-orienté. On a alors l’égalité suivante :

X
d ( s ) = 2| A |.
s∈S

Démonstration : Pour un graphe orienté G = (S, A), chaque arc a un successeur et un prédé-
cesseur d’ou la première égalité.
Pour obtenir la deuxième égalité, il suffit d’orienté le graphe non-orienté et remarquer
que pour chaque sommet d(s) = d+ (s) + d− (s).

Une conséquence directe de ce théorème est que dans un graphe, le nombre de som-
mets dont le degré est impair est toujours pair.
Corollaire I.2
Dans un graphe non orienté, le nombre de sommets dont le degré est impair est
toujours pair.
9 I.2. Différentes notions de graphes

Démonstration : Soit G = (S, A) un graphe non orienté, on note S1 l’ensemble des sommets
impairs et S2 l’ensemble des sommets pairs. Par le lemme de la poignée de main, on a
X X
d(s) + d ( s ) = 2| A |.
s ∈ S1 s ∈ S2

Ainsi s∈S1 d(s) doit être pair. Comme chaque d(s) est impair pour s ∈ S1 , on en séduit
P
que |S1 | est pair

Soit G = (S, A) un graphe simple non orienté défini à partir de l’ensemble de som-
met S = {v1 , . . . , vn }. On note d(vi ) le degré de vi . La suite des degrés de G est la suite
(d(v1 ), . . . , d(vn )). En général, on ne tient pas compte de l’ordre des termes dans cette
suite, et par convention, on écrira ses termes dans l’ordre décroissant.
La suite des degrés du graphe suivant est (4, 4, 3, 3, 2).

Étant donnée une suite d’entiers naturels d = (d1 , . . . , dn ) telle que d1 ≥ · · · ≥ dn ,

il est naturel de se demander s’il existe un graphe simple dont la suite des degrés est d.
Lorsque c’est le cas, on dira que la suite d est graphique. Par exemple, la suite (4, 4, 3, 3, 2)
est graphique. Le théorème suivant donne un algorithme récursif pour déterminer si une
suite est graphique.
Théorème I.3 (Havel et Hakimi)
Soit n ≥ 1 et soit d = (d1 , . . . , dn ) une suite décroissante. La suite d est graphique
si et seulement si d0 = (d20 , . . . , d0n ) = (d2 − 1, d3 − 1, . . . , dd1 +1 − 1, dd1 +2 , dd1 +3 , . . . , dn )
est graphique.

Démonstration : (⇐) Supposons que la suite à n − 1 termes définie par d0 = (d20 , . . . , d0n ) =
(d2 − 1, d3 − 1, . . . , dd1 +1 − 1, dd1 +2 , dd1 +3 , . . . , dn ) est graphique. Il existe un graphe G 0 =
(S0 , A0 ) dont les sommets S0 = {v2 , . . . , vn } vérifient d(vi ) = di0 . On considère le graphe
G = (S, A) qui vérifie

S = S0 ∪ {v1 } et A = A0 ∪ {{v1 , vi } : i ∈ J2, d1 + 1K}.

La suite associé à G est la suite d = (d1 , . . . dn ), la suite est donc graphique.

(⇒) Soit d = (d1 , . . . , dn ) une suite graphique. On veut montrer qu’il existe un graphe
simple G = (S, A) où S = {v1 , ..., vn } tel que d(vi ) = di pour tout i ∈ J1, nK et telle que v1
soit adjacent à tous les sommets dans {v2 , v3 , . . . , vd1 +1 }.
Supposons par l’absurde qu’un tel graphe n’existe pas. Considérons alors un graphe
simple G = (S, A) et une numérotation des sommets S = {v1 , ..., vn } telle que d(vi ) = di et
telle que v1 soit adjacent à un maximum de sommets dans {v2 , . . . , vd1 +1 } sans que ce soit
tous. Il existe donc k ∈ {2, 3, . . . , d1 + 1} et l ∈ {d1 + 2, d1 + 3, . . . , n} tel que {v1 , vk } ∈
/ A
et {v1 , vl } ∈ A. On a deux cas
— Si d(vk ) = d(vl ), il suffit de permuter les sommets, et obtient une numérotation des
sommet qui n’est pas maximale et qui vérifie la propriété.
— Si d(vk ) > d(vl ), il existe m ∈ / {k, l } tel que vm soit adjacent à vk mais pas à vl . En
particulier v1 6= vk . Maintenant on considère le graphe G 0 = (S, A0 ) obtenu à partir de
G = (S, A) tel que

A0 = ( A \ {{v1 , vl }, {vk , vm }}) ∪ {{v1 , vk }, {vm , vl }}

 Chapitre I. D IFFÉRENTES NOTIONS DE GRAPHES 10

On obtient un graphe simple G 0 ayant pour suite des degré d tel que v1 soit adjacent à
strictement plus de sommets dans {v2 , . . . , vd1 +1 } ce qui est une contradiction

I.2.4 Construction de graphes à partir d’un autre

Soit G = (S, A) un graphe (orienté ou non).
Un sous-graphe de G est un graphe G 0 = (S0 , A0 ) tel que S0 ⊂ S et A0 ⊂ A.
Un sous-graphe G 0 = (S0 , A0 ) d’un graphe G = (S, A) est un sous-graphe induit si A0
est formé de tous les arcs (ou arêtes) de G ayant leurs extrémités dans S0 (c’est à dire
∀s, s0 ∈ S0 , (s, s0 ) ∈ A0 si et seulement si (s, s0 ) ∈ A).
Un sous-graphe G 0 = (S0 , A0 ) d’un graphe G = (S, A) est couvrant s’il contient tous les
sommets de G (c’est à dire S0 = S).
Exemple I.5. On considère un graphe G, un sous-graphe quelconque G1 , un sous-graphe
induit G2 et un sous-graphe couvrant G3 .

1 1 1 1

2 3 4 5 3 4 5 2 3 2 3 4 5

G G1 G2 G3

Soit G = (V, E) un graphe (orienté ou non). On note G 0 = G − v le graphe induit

lorsqu’on supprime de sommet v. Si e ∈ E on note G 0 = G − E le graphe G auquel on a
supprimer l’arête e et G = G 0 + e.

I.3 Différents modes de représentation d’un graphe

Compte tenu de l’essor des graphes en informatique, il est naturel de s’intéresser aux
différentes manières de les représenter. Différents modes de représentation peuvent être
envisagées suivant la nature des traitements que l’on souhaite appliquer aux graphes
considérés.

I.3.1 Représentation sagittale

La représentation sagittale est la représentation sous forme d’un dessin. Un même
graphe peut avoir des représentations sagittales en apparence très différentes.

I.3.2 Définition par propriété caractéristique

Une même propriété caractérise les relation entre les différents sommets.
Exemple I.6. On considère le graphe G = (S, A) avec S = {1, 2, 3, 4, 5, 6} et pour tout
s, s0 ∈ S on a
(s, s0 ) ∈ A ⇐⇒ s divise strictement s0 .

Sa représentation sagittale est :

 11 I.3. Différents modes de représentation d’un graphe

1 2

4 3

5 6

I.3.3 Listes d’adjacence

Un graphe peut être représenté à l’aide d’un dictionnaire : il s’agit d’une table à simple
entrée où chaque ligne correspond à un sommet et comporte la liste des successeurs (ou
des prédécesseurs) de ce sommet.
En pratique pour stocker un graphe orienté G = (S, A), on ordonne les sommets
s1 , . . . , sn et le graphe G est représenté par deux listes d’adjacences ( LS, TS) définies par :
— LS : liste de longueur | A| appelé liste des successeurs, elle contient les successeurs du
sommets s1 , puis ceux de s2 jusqu’à ceux de sn , si un sommet n’a pas de successeur,
on passe au sommet suivant.
— TS : liste de longueur |S| + 1 appelé liste des têtes successeurs qui indique la position
du premier successeur de chaque sommet dans LS. La liste TS est définit comme
suit :
— TS(1) = 1 ;
— pour si ∈ S, si si a un successeur alors TS(si ) est le numéro de la case de LS du
premier successeur de si , sinon TS(si ) = TS(si+1 ) ;
— TS(n + 1) = | A| + 1
Exemple I.7. Pour décrire un graphe, il suffit de donner le dictionnaire des successeurs ou
bien le dictionnaire des prédécesseurs.

1 2 Sommets Successeurs
1 2
2 1,4
3 3,4
4 ∅
4 3 Sommets Prédecesseurs
1 2
2 1
La représentation sous forme de liste est : 3 3
LS = (2, 1, 4, 3, 4) TS = (1, 2, 4, 6, 6) 4 2,3

I.3.4 Matrices d’adjacence

Soit G = (S, A) un graphe dont les sommets sont numérotés de 1 à n. La matrice
d’adjacence de G est la matrice carrée (mi,j )(i,j)∈[1,n]2 définie par
(
k s’il y a k arêtes allant de i à j
mi,j =
0 sinon

Si le graphe n’est pas orienté, la matrice est symétrique.

Exemple I.8. Exemples de matrices d’adjacence de graphes orientés :
 Chapitre I. D IFFÉRENTES NOTIONS DE GRAPHES 12

Ö è Ö è
1 2 0 1 0 0 1 2 0 1 0 0
1 0 0 1 1 0 0 3
M= M=
0 0 1 1 0 0 2 1
0 0 0 0 0 0 0 0

4 3 4 3

et de graphes non orientés associés :

Ö è Ö è
1 2 0 1 0 0 1 2 0 1 0 0
1 0 0 1 1 0 0 3
M= M=
0 0 1 1 0 0 2 1
0 1 1 0 0 3 1 0

4 3 4 3

I.3.5 Matrice d’incidence

La matrice d’incidence d’un graphe orienté G = (S, A) est une matrice à coefficients
dans {−1, 0, 1} indicée par l’ensemble S × A tel que pour (i, j) ∈ S × A on a mi,j = 1
si le sommet i est l’extrémité de l’arête j, mi,j = −1 si i est l’origine de j, et 0 sinon. On
remarque que, puisque chaque colonne correspond à une arête, il doit y avoir exactement
un 1 et un −1 sur chaque colonne.

I.3.6 Comparaison des différentes méthodes

On s’intéresse ici à l’espace nécessaire pour stocker un graphe G = (S, A), les diffé-
rentes méthodes ont leurs avantages et inconvénients. En voici un aperçu :

Méthode de représentation Espace de stockage Autre avantage

Liste des arcs 2| A |
Liste d’adjacence |S| + | A| + 1 - efficace pour stocker des graphes creux
- efficace pour implémenter des algorithmes de
parcours (section III.3)
Matrice d’adjacence | S |2 - efficace pour stocker des graphes denses
- donne des informations sur la longueur d’un
chemin (section II.1.2)
Matrice d’incidence |S| × | A| - utiliser pour le calcule de circuit électique

I.4 Quelques classes de graphe importantes

On s’intéresse ici à définir quelques classes de graphes non-orientés dont la plupart
sont simple (non multi-arête et sans boucle).

I.4.1 Graphes isolés

Le graphe isolé d’ordre n est un graphe à n sommets sans arête, on le note In .
 13 I.4. Quelques classes de graphe importantes

I3 I4 I5 I6 I7

I.4.2 Graphes cycliques

Le graphe cyclique d’ordre n est le graphe à n sommets S = {s1 , . . . , sn } tels que les arêtes
sont A = {{si , si+1 } : i ∈ [1, n]} ∪ {{sn , s1 }}, on le note Cn .

C3 C4 C5 C6 C7

I.4.3 Graphes complets

Le graphe complet d’ordre n est le graphe simple à n sommets dont tous les sommets
sont reliés deux à deux, on le note Kn .

K3 K4 K5 K6 K7

I.4.4 Graphe biparti

Un graphe est biparti s’il existe une partition de son ensemble de sommets en deux
sous-ensembles X et Y telle que chaque arête ait une extrémité dans X et l’autre dans Y.
On définit le graphe biparti complet entre un ensemble de n sommets et un ensemble à m
sommets comme le graphe simple tel que chaque sommet du premier ensemble est relié à
chaque sommet su deuxième ensemble. On le note Kn,m .

A B C

1 2 3

K3,3

I.4.5 Graphes planaires

Un graphe non-orienté (pas forcément simple) est planaire s’il admet une représenta-
tion sagittale dans un plan sans que les arêtes se croisent.
 Chapitre I. D IFFÉRENTES NOTIONS DE GRAPHES 14

Exemple I.9. K4 est planaire puisque on peut le représenter de la façon suivante :

K4

Est ce que K5 et K3,3 sont planaires ?

I.4.6 Arbres
Définition I.3. Un arbre se définit de manière inductive par :
— le graphe formé par un sommet est un arbre ;
— si G = (S, A) est un arbre, alors pour s ∈ S et x un élément quelconque n’appar-
tenant pas à S, le graphe G 0 = (S ∪ { x }, A ∪ {{ x, s}}) est un arbre.

Un exemple d’arbre :

Remarque I.1. Au chapitre III on verra une définition équivalente liée à la connexité.
 Chapitre II
Problèmes de chemins dans un graphe

II.1 Notion de chemin

II.1.1 Définitions
Définition II.1. Soit G = (S, A) un graphe orienté (resp. non-orienté). Un chemin (resp.
une chaîne) dans G est une suite de sommets C = (s0 , s1 , s2 , . . . , sk ) telle qu’il existe un arc
(resp. une arête) entre chaque couple de sommets successifs de C. Ce qui s’écrit :
— si G = (S, A) est orienté alors pour tout i ∈ [0, k − 1] on a (si , si+1 ) ∈ A,
— si G = (S, A) est non-orienté alors pour tout i ∈ [0, k − 1] on a {si , si+1 } ∈ A,

On appellera :
Chemin (resp. chaîne) simple : un chemin (resp. chaîne) dont tous les arcs (resp. arêtes)
sont différents.
Chemin (resp. chaîne) élémentaire : un chemin (resp. chaîne) dont tous les sommets sont
différents sauf peut être le départ et l’arrivée (pour autoriser les circuits ou cycles).
Circuit dans un graphe orienté : un chemin simple finissant à son point de départ.
Cycle dans un graphe non-orienté : une chaîne simple finissant à son point de départ.

II.1.2 Longueur d’un chemin

Longueur du chemin (de la chaîne) : nombre d’arcs (ou arêtes) du chemin.
Distance entre deux sommets : longueur du plus petit chemin (chaîne) entre ces deux som-
mets.
Diamètre d’un graphe : plus grande distance entre deux sommets de ce graphe.
Remarque II.1. Dans le cas d’un graphe valué où l’on associe un réel à chaque arcs (ou
arêtes), la longueur d’un chemin correspond à la somme des valeur de chaque arcs (ou
arêtes) du chemin.
Exemple II.1. On peut calculer le diamètre des graphes classiques :
— diamètre de Kn : 1 ;
— diamètre de Kn,m : 2 ;
— diamètre de Cn : b n2 c.
 Chapitre II. P ROBLÈMES DE CHEMINS DANS UN GRAPHE 16

II.2 Connexité
Définition II.2 (Connexité et forte connexité). Un graphe non-orienté est connexe si pour
tout couple de sommets s et s0 , il existe une chaîne reliant s à s0 .
Un graphe orienté est connexe si le graphe non orienté associé est connexe. Un graphe
orienté est fortement connexe si pour tout couple de sommets s et s0 , il existe une chemin
reliant s à s0 .

Exemple II.2 (Graphe connexe et fortement connexe). G1 est fortement connexe tandis que
G2 est connexe mais non fortement connexe.

A B A B

C C
G1 G1

Une arrête e d’un graphe connexe G = (S, A) est un pont ou isthme si X − e (graphe
obtenu en supprimant l’arête e) n’est pas connexe.
Proposition II.1
Soit G = (S, A) un graphe connexe, une arête est un pont si elle ne se trouve sur
aucun cycle.

Démonstration : ⇐ : Soit s et s0 les extrémités de e. Si e n’est pas un pont, il existe une chaîne
s = s0 , s1 , s2 , . . . sn = s0 allant de s à s0 dans G − e. Ainsi en rajoutant e on obtient un cycle
sur G.
⇒ : Supposons que e est sur un cycle C, on va montré que G − e est connexe. Soit s, s0
deux sommets de G − e, comme G est connexe il existe une chaîne reliant s à s0 dans G. Si e
n’apparait pas dans cette chaîne alors on a une chaîne dans G − e. Si e apparait dans cette
chaîne, il suffit d’enlever l’arête e et la remplacer par la partie du cycle C qui ne contient
pas e.

Pour un graphe quelconque, on peut le décomposé en sous graphe connexe. Soit G =

(S, A) un graphe non orienté, on définit la relation d’équivalence RG sur S par

sRG s0 ⇐⇒ il existe une chaîne reliant s à s0 .

Définition II.3. Etant donné un graphe G = (S, A), un sous-graphe induit par les sommet
d’une classe d’équivalence est une composante connexe de G.
Autrement dit, une composante connexe C d’un graphe G = (S, A) est un sous-
ensemble maximal de sommets tels que deux quelconques d’entre eux soient reliés par
une chaîne. Formellement, si s ∈ C alors on a :
— pour tout s0 ∈ C il existe une chaîne reliant s à s0 ,
— pour tout s0 ∈ S \ C, il n’existe pas de chaîne reliant s à s0 .
~ = (S, A) un graphe orienté, on définit la
De même pour un graphe orienté, soit G
~
relation RG~ sur S par

~ ~ s0 ⇐⇒ il existe un circuit allant de s à s0 et un circuit de s0 à s.

sR G
 17 II.3. Graphe k-connexe

~ = (S, A), un sous-graphe induit par les

Définition II.4. Etant donné un graphe orienté G
~
sommet d’une classe d’équivalence de RG~ est une composante connexe de G.
Quelques propriétés :
— Les composantes connexes (resp. fortement connexe) d’un graphe G = (S, A)
forment une partition de S.
— Un graphe est connexe (resp. fortement connexe) si et seulement s’il a une seule
composante connexe (resp. fortement connexe).
— Le sous-graphe induit par une composante connexe (resp. fortement connexe) est
connexe (resp. fortement connexe).
— La composante connexe C qui contient un sommet s ∈ S est

C = {s0 ∈ S : il existe une chaîne reliant s à s0 }

— La composante fortement connexe C qui contient un sommet s ∈ S est

C = {s0 ∈ S : il existe un chemin reliant s à s0 et un chemin reliant s0 à s}

Exemple II.3 (Composantes connexes). Les composantes connexes de G1 sont { A, C, E} et

{ B, D, F } tandis que celles de G2 sont {1}, {2, 6}, {3, 5, 7} et {4}.
3
C B 2
4

D A 1

E F 7
6
G1 G2

Exemple II.4 (Composantes fortement connexes). Les composantes fortement connexes de

G1 sont { A, B} et {C } tandis que celles de G2 sont {1, 7}, {2, 3, 5, 6} et {4}.

3
2
A B
4

5
C
7
6
G1 G2

II.3 Graphe k-connexe

Définition II.5 (Coupe de sommet). Soit G = (S, A) un graphe. Un ensemble d’articulation
est un ensemble de sommets S0 ⊂ S tel que G − S0 ne soit pas connexe.
On note κ ( G ) la taille minimale d’un ensemble d’articulation d’un graphe G :

κ ( G ) = min{|S0 | : S0 ⊂ S tel que G − S0 n’est pas connexe ou réduit à un sommet}

Un graphe G est k-connexe si κ ( G ) ≥ k.

Chapitre II. P ROBLÈMES DE CHEMINS DANS UN GRAPHE 18

Si G n’est pas connexe, on a κ ( G ) = 0. On a κ (Kn ) = n − 1 et si n ≥ 3 κ (Cn ) = 2.

Définition II.6 (Coupe d’arête ). Soit G = (S, A) un graphe. Un ensemble de coupure est un
ensemble d’arête A0 ⊂ A tel que G − A0 ne soit pas connexe.
On note λ( G ) la taille minimale d’un ensemble de coupure d’un graphe G :

λ( G ) = min{| A0 | : A0 ⊂ A tel que G − A0 n’est pas connexe}

Un graphe G est l-connexe par arête si λ( G ) ≥ l.

Exemple II.5. Si G n’est pas connexe, on a λ( G ) = 0.

On a λ(Kn ) = n − 1 et si n ≥ 3 λ(Cn ) = 2.
Théorème II.2
On a κ ( G ) ≤ λ( G ) ≤ δ( G ).

Démonstration : Si le degré minium est δ( G ) alors les δ( G ) d’un sommet réalisant ce mini-
mum réalise une coupe. On a donc λ( G ) ≤ δ( G )
La deuxième inégalité est une conséquence du Théorème de Menger. En effet, si un
ensemble A0 ⊂ A déconnecte G, on prend deux sommet s et s0 dans des composantes
connexes de G \ A. Il y a moins de | A0 | chemin distinct allant de s à s0 donc | A0 | ≥ κ ( G ).

Exemple II.6. Le graphe suivant vérifie κ ( G ) = 1, λ( G ) = 2 et δ( G ) = 3.

Proposition II.3
Soit S1 et S2 deux sous-ensemble de S d’un graphe G = (S, A) simple. Le nombre
maximal de chemin disjoints allant de S1 est égal au cardinal du plus petit ensemble
séparant S1 et S2 .

Démonstration : Soit n le cardinal d’un ensemble maximal noté N de chemins disjoints allant
de S1 à S2 et m le cardinal d’un ensemble de sommets séparant S1 et S2 .
Pour séparer S1 et S2 , il est nécessaire de supprimer un sommet sur chacun des n che-
mins. On a donc n ≤ m.
On raisonne par récurrence sur | A|. Si | A| = 0, alors N est égal à S1 ∩ S2 . Ainsi N est
un ensemble séparant donc m = n.
Supposons que A contient une arête e = {u, v} et que tout graphe avec strictement
moins d’arête vérifie le théorème. On considère le graphe G.e, appelé contraction de G
pour l’arête e, obtenu en supprimant l’arête e et en identifiant les extrémités de celle ci, on
note ve ce sommet. Soit S10 = S1 ∩ V ( G.e) et S20 = S2 ∩ V ( G.e) auquel on a éventuellement
rajouter ve suivant que u ou v appartient à S1 ou S2 . Soit m0 le cardinal d’un ensemble S0 de
taille minimale séparant S10 et S20 dans G.e. Par hypothèse de récurrence, il existe m0 chemin
intérieur disjoint de S10 à S20 . Ces chemins induisent m0 chemins disjoints de S1 à S2 dans G
donc n ≥ m0 .
/ S0 alors S0 est un ensemble séparant dans G donc m0 ≥ m donc n ≥ m.
Si ve ∈
Si ve ∈ S0 , alors S00 = S0 − {ve } ∪ {u, v} est un sous ensemble de S formé de m0 + 1
sommets qui sépare S1 et S2 . Donc m0 + 1 ≥ m. Tout chemin de S1 à S2 dans G passe
par un sommet de S00 donc tout ensemble de sommets séparant S1 et S00 sépare S1 et S2 et
19 II.3. Graphe k-connexe

contient donc au moins m sommets. Par hypothèse de récurrence, le nombre n” de chemins

disjoints de S1 à S00 dans G − e est au moins m. Soit P l’ensemble de cardinal au moins m
des extrémités de ces chemins. Un ensemble séparant S2 de P dans G − e sépare S2 de S1
dans G − e donc est de cardinal au moins m. Il existe donc m chemins disjoints de S2 à P.
On a construit ainsi m chemins distincts de S1 à S2 . Donc n ≥ m.

Théorème II.4 Théorème de Menger

Un graphe est k-connexe par les sommets si et seulement si toute paires de noeuds
distincts est reliée par au moins k chaînes dont les noeuds internes sont tous disjoints.

Démonstration : ⇐ : Si toute paire de sommet est connectée par k chemins indépendant alors
si on enlève k − 1 sommet, tout paire reste connectée. On en déduit que κ ( G ) ≥ k.
⇒ : Si un graphe est k connexe, lorsqu’on enlève k − 1 sommets, le graphe reste connexe.
Ainsi pour toute paire de sommet, d’après le résultat précédent, on peut trouver k chaines
distinctes les reliant.

Proposition II.5
On peut orienter un graphe de telle sorte qu’il soit fortement connexe si et seule-
ment si il est 2-connexe par les arêtes.