Université de M’sila Département d’informatique

Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)

CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

CHAPITRE 2

Rappel sur les concepts de base de la

théorie des graphes
I.1. Introduction
L’histoire de la théorie des graphes débute peut-être avec les travaux d’Euler au XVIIIe siècle et
trouve son origine dans l’étude de certains problèmes, tels que celui des ponts de Königsberg
(voir la figure 1.1 de couverture, les habitants de Königsberg se demandaient s’il était possible, en
partant d’un quartier quelconque de la ville, de traverser tous les ponts sans passer deux fois par
le même et de revenir à leur point de départ), la marche du cavalier sur l’échiquier ou le problème
de coloriage de cartes.

(a) Plan de ville de la Königsberg (b) Plan schématique des ponts de Königsberg
Figure 1.1 Les sept ponts de Königsberg
La théorie des graphes s’est alors développée dans diverses disciplines telles que la chimie, la
biologie, les sciences sociales, …. Depuis le début du XXe siècle, elle constitue une branche à part
entière des mathématiques, grâce aux travaux de König, Menger, Cayley puis de Berge et d’Erdös.
De manière générale, un graphe permet de représenter la structure, les connexions d’un ensemble
complexe en exprimant les relations entre ses éléments : réseau de communication, réseaux
routiers, interaction de diverses espèces animales, circuits électriques,. . .
Pour résoudre de nombreux problèmes concrets, on est amené à tracer sur le papier des petits
dessins qui représentent (partiellement) le problème à résoudre. Bien souvent, ces petits dessins
se composent de points et de lignes continues reliant deux à deux certains de ces points. On
appellera ces petits dessins des graphes, les points des sommets et les lignes des arcs ou arêtes,
selon que la relation binaire sous-jacente est orientée ou non.
En résumé, les graphes constituent donc une méthode de pensée qui permet de modéliser une
grande variété de problèmes en se ramenant à l’étude de sommets et d’arcs. Les derniers travaux
en théorie des graphes sont souvent effectués par des informaticiens, du fait de l’importance
qu’y revêt l’aspect algorithmique.

Dr. Dabba Ali 1/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

I.2. Histoire
L’histoire de la théorie des graphes a commencé par l’étude de certains problèmes, tels que : Le
problème des ponts de Königsberg, résolu par Euler au 1736, la marche du cavalier sur
l’échiquier, le célèbre problème de la coloration des cartes géographiques (connu aussi par le
théorème des 4 couleurs).

➢ 1847 Kirchhoff (1824-1887) développe la théorie des arbres (analyse de circuits

électriques).
➢ 1860 Cayley (1821-1895) découvrit la notion d’arbre (énumération des isomères
saturés des hydrocarbures de types CnH2n+2).
➢ 1859 Hamilton (1805-1865) Existence de chemins hamiltoniens.
➢ 1879 énoncé du problème des 4 couleurs (Möbius (1790-1868), Morgan (1806-1871),
Cayley, solution prouvée en 1976.
➢ 1936 Köning, le premier ouvrage sur les graphes.
➢ A partir de 1946 le développement intense de la théorie des graphes grâce à des
chercheurs comme Kuhn, Ford, Fulkerson, Roy, Berge et...
➢ 1958 Berge, l’ouvrage "Théorie des graphes et ses applications" donne naissance à l’ère moderne
de la théorie des graphes.

I.3. Quelques exemples de modélisation par des graphes

La notion de graphes et les problèmes liés aux graphes peuvent être rencontrés dans différentes
situations de la vie réelle ainsi que dans des problèmes d’ingénierie notamment en informatique.
Les graphes représentent, d’abord, un moyen de modélisation, ainsi qu’un moyen permettant de
raisonner sur de nombreux problèmes.
Les graphes permettent de modéliser des entités reliées par des liens. La disposition des entités et
surtout des liens (ce que l’on appelle la topologie du graphe) permet d’induire plusieurs propriétés
intéressantes. Pour illustrer cela, nous allons prendre quelques exemples introductifs.

Exemple 1.1 (modélisation d’un réseau d’amis)

Dans la vie courante, une personne est amie avec plusieurs personnes pouvant aussi être des amis
à d’autres personnes, et ainsi de suite. Dans les réseaux sociaux par exemple, ces relations
permettent d’établir des communautés et des règles s’appliquant au partage des données. Il est
intéressant de noter (et ceci peut être montré par la théorie des graphes) que dans n’importe
ensemble de groupes d’amis, il y a toujours au moins deux personnes ayant le même nombre
d’amis.

Exemple 1.2 (modélisation d’un réseaux routier)

Le réseau routier d’un pays peut être représenté par un graphe dont les sommets sont les villes. Si
l’on considère que toutes les routes sont à double sens, on utilisera un graphe non orienté et on
reliera par une arête tout couple de sommets correspondant à deux villes reliées par une route (si

Dr. Dabba Ali 2/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

l’on considère en revanche que certaines routes sont à sens unique, on utilisera un graphe
orienté). Ces arêtes pourront être valuées par la longueur des routes correspondantes. Etant
donné un tel graphe, on pourra s’intéresser, par exemple, à la résolution des problèmes suivants :

➔ Quel est le plus court chemin, en nombre de kilomètres, passant par un certain nombre de
villes données ?
➔ Quel est le chemin traversant le moins de villes pour aller d’une ville à une autre ?
➔ Est-il possible de passer par toutes les villes sans passer deux fois par une même route ?

Exemple 1.3 (modélisation d’un réseau de télécommunication)

Un réseau informatique est constitué d’un ensemble de machines (des ordinateurs, des hubs, des
switches, des routeurs, des répétiteurs, etc.) et des liaisons physiques (câbles métalliques, fibres
optiques, ondes radio, etc.). Un routeur permet d’acheminer un paquet vers la bonne sortie afin
que ce dernier puisse retrouver son chemin vers la destination. On est notamment intéressée par
connaître le chemin optimal dans le réseau (en termes de temps de transmission, énergie utilisée,
nombre de sauts, etc.) ainsi que le débit maximal du réseau, ce qui permet d’éviter des situations
agaçantes comme la congestion du réseau.

I.4. Différentes notions de graphes

D’une manière informelle, on peut définir un graphe par une représentation figurative où l’on
retrouve un ensemble de points (appelés nœuds ou sommets) reliés par un ensemble de courbes
droites ou non. Ces liens représentent généralement une relation ou une dépendance entre les
sommets. Ils sont appelés des arêtes si la relation est symétrique (on parle de graphe non-orienté),
ou des arcs sinon (on parle de graphe orienté).

I.4.1. Graphes non orientés

Définition 1.1 (Graphe non orienté)

Un graphe non orienté G est la donnée d'un couple G = (S, A) tel que :

➔ S est un ensemble fini de sommets,

➔ A est un ensemble de couples non ordonnés de sommets {si , sj}  S2.

Une paire {si , sj} est appelée une arête, et est représentée graphiquement par si − sj. On dit que
les sommets si et sj sont adjacents. L'ensemble des sommets adjacents au sommet si  S est noté
Adj(si) = {si  S, {si , sj} A}.

Exemple 1 5 6
Le graphe ci-contre représente un graphe non orienté
G = (S, A) avec S = {1, 2, 3, 4, 5, 6}
et A = {{1, 2}, {1, 5}, {5, 2}, {3, 6}}. 2 4 3

Dr. Dabba Ali 3/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

Définition 1.2 (Boucle, simple graphe, multi-graphe, ordre, taille)

➔ Une boucle est une arête reliant un sommet à lui-même.

➔ Un graphe non-orienté est dit simple s'il ne comporte pas de boucle, et s'il ne comporte
jamais plus d'une arête entre deux sommets. Un graphe non-orienté qui n'est pas simple est un
multi-graphe. Dans le cas d'un multi-graphe, A n'est plus un ensemble mais un multi-ensemble
d'arêtes.

➔ On appelle ordre d'un graphe le nombre de ses sommets, i.e. c'est card(S) ou |S|.

➔ On appelle taille d'un graphe le nombre de ses arêtes, i.e. c'est card(A) ou |A|.

I.4.2. Graphes orientés

Définition 1.3 (Graphe orienté)

Un graphe orienté G est la donnée d'un couple G = (S, A) tel que :

➔ S est un ensemble fini de sommets,

➔ A est un ensemble de couples ordonnés de sommets (si , sj)  S2.

Un couple (si , sj) est appelé un arc, et est représenté graphiquement par si → sj, si est le sommet
initial ou origine, et sj le sommet terminal ou extrémité. L'arc a = (si , sj) est dit sortant en si et
incident en sj, et sj est un successeur de si, tandis que si est un prédécesseur de sj.

➔ L'ensemble des successeurs d'un sommet si  S est noté Succ(si) = {sj  S, (si , sj)  A}.

➔ L'ensemble des prédécesseurs d'un sommet si  S est noté Pred(si) = {sj  S, (sj , si )  A}.

Exemple
1 6
Le graphe ci-contre représente un graphe orienté
2 4
G = (S, A) avec S = {1, 2, 3, 4, 5, 6}
et A = {(1, 2), (2, 4), (2, 5), (4, 1), (4, 4), (4, 5), (5, 4), (6, 3)}. 5 3

Définition 1.4 (Boucle, élémentaire, p-graphe)

➔ Une boucle est une arc reliant un sommet à lui-même.

➔ Un graphe orienté est dit élémentaire s'il ne contient pas de boucle.

➔ Un graphe orienté est un p-graphe s'il comporte au plus p arcs entre deux sommets. Le plus
souvent, on étudiera des 1-graphes.

Dr. Dabba Ali 4/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

I.5. Degré dans un graphe

Définition 1.5 (degré d'un sommet)

➔ Dans un graphe non-orienté, le degré d'un sommet est le nombre d'arêtes incidentes à ce
sommet (une boucle comptant pour 2). Dans le cas d'un graphe simple, on aura d(s) = |Adj(s)|.

➔ Dans un graphe orienté, le demi-degré extérieur ou demi-degré sortant d'un sommet s,

noté d+(s), est le nombre d'arcs partant de s, i.e. de la forme (s, v) avec v  S. Dans le cas d'un
1-graphe, on aura d+(s) = |Succ(s)|.

De même, le demi-degré intérieur ou demi-degré entrant d'un sommet s, noté d−(s), est le
nombre d'arcs arrivant en s, i.e. de la forme (v, s) avec v  S. Dans le cas d'un 1-graphe, on aura
d−(s) = |Pred(s)|.

➔ Le degré d'un sommet s est alors la somme des degré entrant et sortant :
d(s) = d+(s) + d−(s).

I.6. Différents types de graphes

Tout d'abord, on peut vouloir attribuer des valeurs aux arcs ou arêtes pour tenir compte de
contraintes : distance, coût . . .

Définition 1.6 (graphe valué)

Un graphe valué G = (S, A, ν) est un graphe (S, A) (orienté ou non-orienté) muni d'une
application ν : A →. L'application ν est appelée valuation du graphe. On peut étendre cette
valuation en posant (x, y)  S2, ν(x, y) = + si (x; y)  A.

Définition 1.7 (graphe complet)

➔ Un 1-graphe orienté élémentaire est dit complet s'il comporte un arc (si , sj) et un arc (sj, si)
pour tout couple de sommets différents si , sj  S.

➔ De même, un graphe non-orienté simple est dit complet s'il comporte une arête {si , sj} pour
toute paire de sommets différents si , sj  S.

➔ On note Kn un graphe complet d'ordre n. La taille du graphe Kn est n(n−1)/2.

Exemple
4
2
5 3
K3 : 1 K5 :

3 1 2

Dr. Dabba Ali 5/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

Définition 1.8 (sous-graphe induit, sous-graphe partiel)

Soit G = (S, A) un graphe (orienté ou non orienté) alors :

➔ Un sous-graphe induit de G est un graphe G ayant pour sommets un sous-ensemble S

des sommets de G et pour arcs/arêtes uniquement ceux de G joignant les sommets de S, ce qui
s'écrit : G = (S, A) avec S ⊂ S et A = {(x, y)  A , x  S et y  S}.

➔ Un sous-graphe partiel de G est un graphe G ayant pour sommets un sous-ensemble S

des sommets de G et pour arcs/arêtes un sous-ensemble de ceux de G joignant les sommets de
S, ce qui s'écrit : G = (S, A) avec S ⊂ S et A ⊂ {(x, y)  A , x  S et y  S}.

Exemple

G : Graphe partiel défini par A = A \ {(2, 2), (3, 2), (3, 4)} et G : Sous-graphe de G induit
par S = {1, 2, 4} :
1 1 1

2 2 3 2
3
G: G : G :
4 4 4

Définition 1.9 (clique, stable)

Soit G = (S, A) un graphe (orienté ou non orienté), alors :

➔ Une clique est un sous-graphe (induit) complet de G,

➔ Un stable est un sous-graphe induit de G sans arcs/arêtes.

Trouver une clique d'ordre k dans un graphe est un problème NP-complet, ce qui implique qu'il
n'existe pas à ce jour un algorithme résolvant ce problème de façon exacte avec une complexité
polynomiale (elle est exponentielle). Le problème consistant à trouver la plus grande clique d'un
graphe est appelé « problème de la clique maximum », et est encore plus difficile ! (il est NP-
difficile)
7 2 8
Exemple

Trouver le plus grand stable et la plus grande clique

du graphe ci-contre : 3 4
Dans le graphe G l'ensemble de sommets {1, 5, 7} induit
une clique maximum, alors que {2, 4, 5} induit
5 1 6
un stable maximum (il y en a d'autres).

Dr. Dabba Ali 6/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

I.7. Représentations des graphes

Dans les algorithmes que nous étudierons par la suite, nous utiliserons la notation illustrée dans
l’algorithme 1 pour appliquer un même traitement à tous les sommets successeurs d’un sommet
si donné.

Algorithme 1 : Exemple de notation pour appeler une procédure traiter sur tous les
successeurs d’un sommet si

1 : Pour tout sommet sj  succ(si) faire

2: traiter(sj)
3 : Fin_Pour

La complexité de cette séquence dépend bien évidemment de la structure de données utilisée

pour représenter le graphe (en supposant que la procédure traiter a une complexité constante). Il
existe deux structures de données classiques pour représenter un graphe : les matrices d’adjacence
et les listes d’adjacence.

I.7.1. Représentation par matrice d’adjacence

Soit le graphe G = (S, A) d'ordre n (n =|S|). On suppose que les sommets de S sont numérotés
de 1 à n. La représentation par matrice d'adjacence de G consiste en une matrice booléenne M de
taille n  n telle que M[i][j] = 1 si (i, j)  A, et M[i][j] = 0 sinon.
Si le graphe est valué (par exemple, di des distances sont associées aux arcs), on peut utiliser une
matrice d’entiers, de telle sorte que M[i][j] soit égal à la valuation de l’arc (i, j) si (i, j)  A. S’il
n’existe pas d’arc entre 2 sommets i et j, on peut placer une valeur particulière (par exemple 0 ou
- ou null) dans M[i][j].
Dans le cas de graphes non orientés, la matrice est symétrique par rapport à sa diagonale
descendante. Dans ce cas, on peut ne mémoriser que la composante triangulaire supérieure de la
matrice d'adjacence.
1
Exemple
2 3
Soit le G = (S, A) le graphe orienté ci-contre :
Alors la matrice d'adjacence associée à ce graphe est :
4
1 2 3 4
1 0 0 0 0
 
2 1 1 0 0
1 1 1 1
3  
1 0 
4  1 1

Dr. Dabba Ali 7/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

Taille mémoire nécessaire : la matrice d'adjacence d'un graphe ayant n sommets nécessite de
l'ordre de O(n2) emplacements mémoire. Si le nombre d'arcs est très inférieur à n2, cette
représentation est donc loin d'être optimale.
Opérations sur les matrices d'adjacence : le test de l'existence d'un arc ou d'une arête avec
une représentation par matrice d'adjacence est immédiat (il suffit de tester directement la case
correspondante de la matrice). En revanche, connaître le degré d'un sommet nécessite le parcours
de toute une ligne (ou toute une colonne) de la matrice. D'une façon plus générale, le parcours de
l'ensemble des arcs/arêtes nécessite la consultation de la totalité de la matrice, et prendra un
temps de l'ordre de n2. Si le nombre d'arcs est très inférieur à n2, cette représentation est donc
loin d'être optimale.

I.7.2. Représentation par listes d'adjacence

Soit le graphe G = (S, A) d'ordre n (n =|S|). On suppose que les sommets de S sont numérotés
de 1 à n. La représentation par listes d'adjacence de G consiste en un tableau T de n listes, une
pour chaque sommet de S. Pour chaque sommet si  S, la liste d'adjacence T[si] est une liste
(chaînée) de tous les sommets sj tels qu'il existe un arc (si , sj)  A ou une arête {si , sj}  A. Les
sommets de chaque liste d'adjacence sont généralement listés selon un ordre arbitraire.
Si le graphe est valué (par exemple, si les arêtes représentent des distances), on peut stocker dans
les listes d’adjacence, en plus du numéro de sommet, la valuation de l’arête.
Dans le cas de graphes non orientés, pour chaque arête {si , sj}, on aura sj qui appartiendra à la
liste chaînée de T[si], et aussi si qui appartiendra à la liste chaînée de T[sj].

Exemple

On considère le même graphe qu'au cas précédent, sa liste d'adjacence est :

1 1

2 2 1 2 3

3 1 4 3 2
4
4 1 2 3

Taille mémoire nécessaire : si le graphe G est orienté, la somme des longueurs des listes
d'adjacence est égale au nombre d'arcs de A, puisque l'existence d'un arc (si , sj) se traduit par la
présence de sj dans la liste d'adjacence de T[si]. En revanche, si le graphe n'est pas orienté, la
somme des longueurs de toutes les listes d'adjacence est égale à deux fois le nombre d'arêtes du
graphe, puisque si {si , sj} est une arête, alors si appartient à la liste d'adjacence de T[sj], et vice
versa. Par conséquent, la liste d'adjacence d'un graphe ayant n sommets et m arcs ou arêtes
nécessite de l'ordre de O(n + m) emplacements mémoires.

Dr. Dabba Ali 8/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

Opérations sur les listes d'adjacence : il n'existe pas de moyen plus rapide que de parcourir la
liste d'adjacence de T[si] jusqu'à trouver sj pour tester l'existence d'un arc (si , sj) ou d'une arête
{si , sj} avec une représentation par liste d'adjacence. En revanche, le calcul du degré d'un
sommet, ou l'accès à tous les successeurs d'un sommet, est très efficace : il suffit de parcourir la
liste d'adjacence associée au sommet. D'une façon plus générale, le parcours de l'ensemble des
arcs/arêtes nécessite le parcours de toutes les listes d'adjacence, et prendra un temps de l'ordre de
p, où p est le nombre d'arcs/arêtes. En revanche, le calcul des prédécesseurs d'un sommet n'est
pas aisé avec cette représentation, et nécessite le parcours de toutes les listes d'adjacences de T.
Une solution dans le cas où l'on a besoin de connaître les prédécesseurs d'un sommet est de
maintenir, en plus de la liste d'adjacence des successeurs, la liste d'adjacence des prédécesseurs.

I.7.3. Représentation matricielle des graphes valués

Un graphe valué G = (S, A, ν) peut être représenté par la matrice des valuations :

 si ( si , s j )  A
W  M n (  ) telle que Wi , j = 
v((si , s j )) si ( si , s j )  A

Exemple
6 2
A B E
Soit le G = (S, A, ν) le graphe orienté ci-contre :
-2 2 8
La matrice d'adjacence du graphe valué suivant est : 4 9

A B C E F G G C F
-1
A  6    − 2 -3
 
B      2 
 4   −1  
W =C  
E  2 8  9 
      
F 
  −3    
G 

I.8. Notions de chemin, chaîne, cycle et circuit

Définition 1.10 (chemin , circuit) [Cas des graphes orientés]

Soit G = (S, A) un graphe orienté,

➔ Un chemin d'un sommet u vers un sommet v est une séquence < s0 , s1 , s2 ,  , sk > de
sommets tels que u = s0 , v = sk et (si-1; si)  A pour tout i  {1,  , k}. On dira que le chemin
contient les sommets s0 , s1 , s2 ,  , sk et les arcs (s0, s1), (s1, s2),  , (sk-1 , sk).

➔ La longueur du chemin est le nombre d'arcs dans le chemin, c'est-à-dire k.

➔ S'il existe un chemin de u à v, on dira que v est accessible à partir de u.

➔ Un chemin est élémentaire si les sommets qu'il contient sont tous distincts.

Dr. Dabba Ali 9/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

➔ Un chemin < s0 , s1 , s2 ,  , sk > forme un circuit si s0 = sk et si le chemin comporte au

moins un arc (k ≥ 1). Ce circuit est élémentaire si, en plus, les sommets s0 , s1 , s2 ,  , sk sont
tous distincts. Une boucle est un circuit de longueur 1.

Exemple
1 2 3
Considérons par exemple le graphe orienté suivant :
Un chemin élémentaire dans ce graphe est < 1, 4, 2, 5 >.
Un chemin non élémentaire dans ce graphe est < 3, 6, 6, 6 >.
4 5 6
Un circuit élémentaire dans ce graphe est < 1, 2, 5, 4, 1 >.
Un circuit non élémentaire dans ce graphe est < 1, 2, 5, 4, 2, 5, 4, 1 >.
Dans le cas des graphes non orientés, seule la terminologie change.

Définition 1.11 (chaîne , cycle) [Cas des graphes non orientés]

Si G = (S, A) est un graphe non orienté, on parlera de chaîne au lieu de chemin, et de cycle au
lieu de circuit. Dans le cas d'un cycle, toutes les arêtes doivent être distinctes.

➔ Un graphe sans cycle est dit acyclique.

Lemme 1.1 (de König)

➔ Dans un graphe, s'il existe un chemin/chaîne d'un sommet u vers un sommet v, alors il existe
un chemin élémentaire de u vers v.

➔ La notion de longueur de chemin nous permet ensuite de définir la notion de distance dans un
graphe.

Définition 1.12 (distance , diamètre)

Soit un graphe G = (S, A). On appelle :

➔ distance d'un sommet à un autre la longueur du plus court chemin/chaîne entre ces deux
sommets, ou  s'il n'y a pas un tel chemin/chaîne :

 k si le plus court che min de x ver y est de longueur k

 x, y  S d ( x, y) = 
 sin on
➔ diamètre du graphe est la plus grande distance entre deux sommets.

Dr. Dabba Ali 10/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

I.9. Notion de connexité

I.9.1. Graphes et sous-graphes connexes

Définition 1.13 (connexité)

Un graphe non orienté est connexe si chaque sommet est accessible à partir de n'importe quel
autre. Autrement dit, si pour tout couple de sommets distincts (si, sj)  S2, il existe une chaîne
entre si et sj.

Exemple a b e f
Le graphe non orienté suivant n'est pas connexe
car il n'existe pas de chaîne entre les sommets a et e.
En revanche, le sous-graphe induit par
d c g
les sommets {a, b, c, d} est connexe.

Définition 1.14 (composante connexe)

➔ Une composante connexe d'un graphe non-orienté G est un sous-graphe G de G qui est
connexe et maximal (c'est-à-dire qu'aucun autre sous-graphe connexe de G ne contient G).

➔ Un graphe est dit connexe si et seulement si il admet une unique composante connexe.

Par exemple, le graphe précédent est composé de 2 composantes connexes : la première est le
sous-graphe induit par les sommets {a, b, c, d}, et la seconde est le sous-graphe induit par les
sommets {e, f, g}.

Définition 1.15 (point d'articulation, isthme, ensemble d'articulation)

➔ Un point d'articulation d'un graphe est un sommet dont la suppression augmente le nombre
de composantes connexes.

➔ Un isthme est une arête dont la suppression a le même effet.

➔ Un ensemble d'articulation E ⊂ S d'un graphe connexe G = (S, A) est un ensemble de

sommets tel que le sous-graphe G déduit de G par suppression des sommets de E ne soit plus
connexe

I.9.2. Graphes et sous-graphes fortement connexes

On retrouve les différentes notions de connexités dans les graphes orientés, en remplaçant
naturellement la notion de chaîne par celle de chemin : on parle de graphe fortement connexe
au lieu de connexe, de composante fortement connexe au lieu de composante connexe.
Plus précisément, un graphe orienté est fortement connexe si chaque sommet est accessible à
partir de n’importe quel autre. Autrement dit, si pour tout couple de sommets distincts (si, sj) 
S2, il existe un chemin de si vers sj, et un chemin de sj vers si.

Dr. Dabba Ali 11/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

Exemple a b a b

Le graphe de gauche est fortement connexe,

tandis que celui de droite ne l'est pas

d c d c
Le graphe non fortement connexe possède en fait quatre composantes fortement connexes : les
sous-graphes possèdent un seul sommet : {a} ou {b} ou {c} ou {d}.

Définition 1.16 (graphe réduit)

Soit G = (S, A) un graphe orienté. On appelle graphe réduit de G le graphe Gr dont les
sommets c1,, cp sont les composantes fortement connexes de G, et il existe un arc entre ci et cj
si et seulement s'il existe au moins un arc entre un sommet de Gi et un sommet de Gj dans le
graphe G. On vérifie que le graphe Gr est sans circuit.

Exemple

Un graphe (à gauche) ayant deux composantes fortement connexes, et son graphe réduit (à
droite)

a b e f

C1 C2

g
d c

Le graphe G a pour composantes connexes les sous-graphes G1, ayant pour sommets {a, b, c,
d}, et G2, ayant pour sommets {e, f, g}. Il existe un arc entre un sommet de G1 et un sommet de
G2, on a donc un arc entre c1 et c2, mais il n'existe aucun arc entre un sommet de G2 et un
sommet de G1, et il n'existe donc pas d'arc (c2, c1).

I.10. Arbres et Arborescences

Les arbres et les arborescences sont des graphes particuliers très souvent utilisés en informatique
pour représenter des données.

Définition 1.17 (arbre)

Un arbre est un graphe non orienté G qui vérifie une des conditions équivalentes suivantes :

➔ G est connexe et acyclique

➔ G est sans cycle et possède n - 1 arêtes

➔ G est connexe et admet n - 1 arêtes

Dr. Dabba Ali 12/13

 Université de M’sila Département d’informatique
Module: Optimisation des Réseaux 2ème Année Master (M2RTIC)
CHAPITRE 1 Rappel sur les concepts de base de la théorie des graphes (2023-2024)

➔ G est sans cycle, et en ajoutant une arête, on crée un et un seul cycle élémentaire,

➔ G est connexe, et en supprimant une arête quelconque, il n'est plus connexe,

➔ Il existe une chaîne et une seule entre 2 sommets quelconques de G.

Exemple
a b e f
Le graphe suivant est un arbre

g
d c

Définition 1.18 (forêt, arborescence)

➔ On appelle forêt un graphe dont chaque composante connexe est un arbre.

➔ Une arborescence est un graphe orienté sans circuit admettant une racine s0  S telle que
pour tout autre sommet si  S, il existe un chemin unique allant de s0 vers si. Si l'arborescence
comporte n sommets, alors elle comporte exactement n - 1 arcs.

Exemple a b e f

Le graphe suivant est une arborescence de racine a :

g
d c

Dr. Dabba Ali 13/13