Théorie des Graphes - THG

CHAPITRE 1 : NOTIONS FONDAMENTALES

Plan
1. Notion de graphe
2. Chemins (chaines) et circuits (cycles)
3. Modes de représentation d’un graphe
4. Connexité
5. Graphes expanseurs

1. NOTION DE GRAPHE

Un graphe (orienté) est un couple ( , ) défini par :

1.1. Graphe

- Un ensemble = { , , … , } dont les éléments sontappelés sommets (ou nœuds).

- Un ensemble = { , , … , } dont les éléments sont appelés arcs. Un arc est un couple

= × = ( , )⁄ ∈ ∈
ordonné de sommets ; l’ensemble est donc obtenu par le produit cartésien :

- L’arc ( , ) du graphe a comme extrémité initiale et comme extrémité terminale.

- Une boucle est un arc (ou arête) dont l’extrémité initiale coïncide avec l’extrémité finale.
- Le nombre de sommets d’un graphe est dit ordre d’un graphe

={ , , %, &, '}
Exemple 1 :
x3 x2

= {( , ), ( , ), ( , % ), ( % , & ), ( & , % ), ( & , ' )}

x1

= 5 )*++ )
x5
Ordre du graphe
x4

Remarque :

crochets , . On parle alors de graphe non orienté.

Une arête est un arc non orienté. Une arête est représentée par un couple non ordonné noté avec des

Un p-graphe est un graphe dans lequel il existe au maximum arcs de la forme ( , ) entre deux
1.2. p-graphe

sommets quelconques et pris dans cet ordre. Si = 1, on parle alors de 1-graphe ou graphe.
x3 x2
Exemple 2 : (2-graphe)
x1

x5
x4

Dans un arc de la forme ( , ),

1.3. Successeur & prédécesseur
est appelé prédécesseur de et est dit successeur de .
et sont appelés sommets voisins (ou adjacents).

L’ensemble des successeurs de est noté !" ( ) et celui de ses prédécesseurs est noté ! (
#
):
! ( )= /( , ) ∈ ! ( )= /( , ) ∈
" #

2
 Théorie des Graphes - THG
" #

l’ensemble . " est appelé application multivoque et # application multivoque réciproque.

sont des applications qui à tout sommet de lui font correspondre un sous ensemble de

! (
" )=∅ , ! ( &)
"
={ , '}
Exemple 3 : (Voir Exemple 1)
%

! (
# )={ } , ! ( &)
#
= { %}

• L’ensemble des sommets voisins de est noté ! ( ) = ! (

" ) ∪ !# ( )
Remarque :

! ( ) respectivement ! ( ) peut être vide ;

" #
• est alors appelé sommet puits,

• Si ! ( ) = ∅, alors est un sommet isolé.

respectivement sommet source.

• Si . ⊂ alors
Propriétés :

! (.) =/ !( )
01 ∈2

: = ( , ") ⇔ ( , )
•
"
Un graphe est complètement défini par l’ensemble des sommets et l’application multivoque

Exemple 4 :

= ( , ) avec = { , , % , & , ' , E , D } et

Ce graphe peut être soit défini par :

= {( , ), ( , % ), ( % , ' ), ( & , ), ( & , ' ), ( ' , ' ), ( E , E ), ( E , D )}

•

E
⬚
ou bien par :
= ( , " ) avec "
: → J( ) (Parties ou sous-ensembles de )
*ù " ( ) = { }, "( )
= { % }, " ( % ) = { ' } , … , " ( D ) = ∅
•
'
% D
&
Aussi si . = { , , %}
( )={ '}
alors
" (.)
=/ "
, % ,
01 ∈2
1.4. Arcs adjacents et sommets adjacents

• 2 sommets sont adjacents s’ils sont distincts et qu’il existe un arc ( , ) et/ou ( , ).
• 2 arcs sont adjacents s’ils ont au moins une extrémité commune.

Exemple 5 : (Voir Exemple 4)

Les arcs ( , ) et ( & , ) sont adjacents ( commun) Les sommets et sont adjacents
3 3
Les arcs ( , % ) et ( % , ' ) sont adjacents ( % commun) Les sommets et & sont adjacents

1.5. Arcs incidents à un sommet

• Incident extérieur : on dit que l’arc
= ( , ) a comme extrémité initiale. Le nombre d’arcs incidents extérieurement à est
est incident extérieurement au sommet si l’arc

et est noté par A!" ( ). Il correspond dans le cas d’un

1-graphe au nombre de successeurs et on a : A!" ( ) = | !" ( )|
appelé demi-degré extérieur de

•
=( , ) a
Incident intérieur : on dit que l’arc est incident intérieurement au sommet si l’arc

et est noté par A! ( ). Il correspond dans le cas d’un

comme extrémité finale. Le nombre d’arcs incidents intérieurement à est
#

1-graphe au nombre de prédécesseurs et on a : A!# ( ) = | !# ( )|

appelé demi-degré intérieur de

comptée 2 fois), et est noté par : A! ( ) = A!" ( ) + A!# ( )

• Le degré d’un sommet est le nombre d’arcs ayant une extrémité en (chaque boucle étant

3
Théorie des Graphes - THG

A! A!" C A!# 3C1 4

Exemple 6 :

A! A!" C A!# 1C1 2

A! % A!" % C A!# % 0C1 1

& % A! & A!" & C A!# & 1C2 3

• Si tous les sommets ont le même degré, le graphe est dit régulier.

Exemple d’un graphe 3-régulier

• Un arc est incident à K (K ⊂L) vers l’extérieur si seulement l’extrémité initiale (et pas l’extrémité
1.6. Arcs incidents à un ensemble de sommets

finale) de cet arc ∈ à N. L’ensemble des arcs incidents extérieurement à N est noté O " N .

• Un arc est incident à K (K ⊂L) vers l’intérieur si seulement l’extrémité finale (et pas l’extrémité
initiale) de cet arc ∈ à N. L’ensemble des arcs incidents intérieurement à N est noté O # N .

• Cocycle : L’ensemble des arcs incidents à N (N ⊂ ) est appelé cocyle du graphe et est noté :
O N O" N ∪ O# N

N , ,
Exemple 7 :
'

O" N , % , , &

%
O# N %, '
'
O N , % , , & , %, '

&

1.7. Diamètre et rayon d’un graphe

Le diamètre d’un graphe est l'excentricité maximale de ses sommets, c'est-à-dire la plus grande
distance possible qui puisse exister entre deux de ses sommets. L'excentricité minimale est
appelée rayon. La distance entre deux sommets dans un graphe est définie par la longueur d'un plus
court chemin entre ces deux sommets.

Exemple 8 :

Graphe de diamètre 3. Les deux sommets les plus éloignés sont les deux extrémités supérieures.

4
Théorie des Graphes - THG
1.8. Isomorphisme de graphes
Un isomorphisme de graphes est une bijection entre les sommets de 2 graphes qui préserve les arêtes.

Exemple 9 :
Graphe G Graphe H Isomorphisme entre G et H

ƒ(a) = 1
ƒ(b) = 6
ƒ(c) = 8
ƒ(d) = 3
ƒ(g) = 5
ƒ(h) = 2
ƒ(i) = 4
ƒ(j) = 7

1.9. Graphes particuliers

C’est un graphe qui à tout couple de sommets , (avec T ) ,

Graphe complet

, , . Dans un graphe complet

& %
on a : U , V∉ ⇒U , V ∈ .
il existe l’arc et/ou l’arc

_a _b

, est dit plein ⇔ ∀ , ∈ , les arcs

Graphe plein

, , , , , ∈ * ) à . A tout graphe ,
Un graphe

,
on peut

graphe plein contient ² arcs.

lui associer un graphe plein . Pour un graphe d’ordre , le
_` _c

Le graphe complémentaire ̅ , Z d’un graphe ,

Graphe complémentaire

arcs les arcs qui ∉ à et qui ∈ à un graphe plein de . (i.e. Z [ .

a le même ensemble de sommets et comme

\ ]
\ ]
Graphe complémentaire

A ^
A ^

̅ ,Z
,

_a _b _a _b
Un graphe est dit symétrique si pour tout arc , ,
Graphe symétrique et Graphe antisymétrique

il existe l’arc , (Le graphe peut contenir des

tout arc , , l’arc ,

boucles). Il est par contre antisymétrique si pour
∉ .
_`
symétrique _` antisymétrique

5
Théorie des Graphes - THG
Graphe partiel, sous graphe et sous graphe partiel
• Un graphe d est un graphe partiel de s’il est formé par l’ensemble des sommets de et par un
sous-ensemble d’arcs de .

• Un sous-graphe e d’un graphe est constitué d’un sous-ensemble de sommets de et de tous les
arcs relatifs à ce sous-ensemble.

& % & % %
Un graphe partiel de Un sous graphe de G

• Un sous-graphe partiel ed du graphe est obtenu en enlevant à des sommets et tous les arcs
relatifs à ces sommets, ensuite enlever à nouveau certains arcs au sous-graphe obtenu.

' ' '

% % %

&
Sous graphe obtenu en enlevant Sous graphe partiel
le sommet & et les arcs relatifs
Graphe

%
,
Graphe biparti

partitionné en 2 classes 1 et 2 (i.e. 1 ∩ 2 ∅ 1∪ 2

Un graphe est biparti si l’ensemble de ses sommets peut être
) de telle

1, 2, .
sorte que 2 sommets de la même classe ne soient pas adjacents. On le note :
g &
'

Graphe planaire
Un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans
qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre.

Ce graphe est clairement C'est un graphe complet à 4 C'est un graphe Ce graphe n'est pas
planaire, car il n'existe pas sommets. Il est planaire : si on complet à 5 planaire.
d'intersection entre deux déplace le sommet 4 dans le sommets. Il n'est
arêtes. triangle 1 2 3, on constate qu'il pas planaire
n'y a plus d'intersection d'arêtes.

6
Théorie des Graphes - THG

2. CHEMINS (CHAINES) ET CIRCUITS (CYCLES)

2.1. Chemin
Un chemin est une séquence (suite) d’arcs tels que l’extrémité finale d’un arc coïncide avec l’extrémité
initiale du suivant. Un chemin peut être énuméré par la liste des sommets qui le composent.
'
Exemple 10 : E

( , ', &, %, , &, , & , % ) est un chemin

&
%

• Chemin simple

, ' , & , , & , % ) est un chemin simple.( , ' , & , , ' ) est un chemin
C’est un chemin qui ne contient pas plus d’une fois le même arc. Dans le cas contraire, c’est un chemin
composé. Le chemin
composé.

• Chemin élémentaire

chemin non élémentaire. Le chemin ( , ' , & , % , ) est un chemin élémentaire.

C’est un chemin qui ne contient pas plus d’une fois le même sommet. Dans le cas contraire, c’est un

• Chemin hamiltonien
C’est un chemin qui passe une et une seule fois par tous les sommets du graphe.( , ', &, %, , E)
est un chemin hamiltonien.

2.2. Circuit

premier arc. Dans le graphe de l’exemple 10, ( , ' , & , , & , ) est un circuit.
C’est un chemin fermé tel que l’extrémité finale du dernier arc coïncide avec l’extrémité initiale du

• Un circuit est simple si tous les arcs qui le composent sont différents. Ex : ( , ' , & , , & , % , )
• Un circuit est élémentaire si tous les sommets qu’il traverse sont différents (sauf le sommet initial
et le sommet final qui coïncident). Ex : ( , ' , & , )
• Un circuit est hamiltonien s’il passe une seule fois par tous les sommets du graphe (sauf le sommet
initial et le sommet final qui coïncident). Ex : ( , ' , & , % , , E , )

2.3. Chaine
C’est une séquence d’arêtes (arcs non orientés), chaque arête étant rattachée à une autre par l’une de
ses extrémités. Pour une chaine simple, élémentaire, hamiltonienne, ce sont les mêmes définitions que
celles des chemins, seulement au lieu des arcs il s’agit d’arêtes.

Exemple 11 :

o , , %, &, , % , & , ' p est une chaine quelconque ou composée.

o , , %, , & , ' p est une chaine simple.
-
'
o , , % , & p est une chaine élémentaire.
-

o , , % , & , ' p est une chaine hamiltonienne.

-
%
-
&

7
Théorie des Graphes - THG
2.4. Cycle

l’exemple 11, [ , , % , & , p est un cycle.

C’est une chaine fermée qui part d’un sommet et qui aboutit à ce même sommet. Dans le graphe de

Pour un cycle simple, élémentaire, hamiltonien ce sont les mêmes définitions que celles des circuits,
seulement au lieu des arcs, il s’agit d’arêtes.

Remarque : hamiltonien ⇒ élémentaire ⇒ simple.

2.5. Longueur d’un chemin (ou d’une chaine)

C’est le nombre d’arcs (ou d’arêtes) qui composent le chemin (ou la chaine).

Dans le graphe de l’exemple 10, le chemin r = ( , ' , & , % , , E ) est de longueur ℓ(r) = 5
Exemple 12 :

Dans le graphe de l’exemple 11, la chaine r = o , , % , & p est de longueur ℓ(r) = 3

3. MODES DE REPRESENTATION D’UN GRAPHE

L’essor de la théorie des graphes est essentiellement dû à l’avènement de puissants ordinateurs. Il est
donc légitime de s’intéresser à la manière de représenter les graphes au sein d’un ordinateur.
Plusieurs modes de représentation peuvent être envisagés selon la nature des traitements que l’on
souhaite appliquer au graphe considéré.

Soit le graphe = ( , ) défini par ={ , , %, &} , = {( , ) ,( , &) , ( , &) , ( & , % )}

&

3.1. Représentation en matrice booléenne (matrice d’incidence sommet–sommet)

Chaque ligne ou colonne correspond à un sommet du graphe. Chaque élément de la matrice est défini

0 )u v w \x^ U , V∉
comme suit :

=t
1 )u v w \x^ U , V ∈

% &

0 1 0 1

0 0 0 1

% 0 0 0 0

& 0 0 1 0

8
Théorie des Graphes - THG
3.2. Représentation en matrice d’incidence sommet–arc
Dans cette représentation, les lignes correspondent aux sommets et les colonnes aux arcs. Chaque

C1 )u v )*++ ) v w xé+u é u u u\v A v w \x^

élément de la matrice est défini comme suit :

y−1 )u v )*++ ) v w xé+u é {u \v A v w \x^

0 ) w uv w ) u xé+u é u u u\v u {u \v A v w \x^
( , ) ( , &) ( , &) ( & , %)

+1 +1 0 0

−1 0 +1 0

% 0 0 0 −1

& 0 −1 −1 +1

Remarque : Les boucles ne peuvent pas être représentées dans ce type de représentation.

3.3. Représentation en dictionnaire (écriture BERGE)

()*++ )) "
( ) #
( )

, & ∅

&

% ∅ &

& % ,

4. CONNEXITE
La notion de connexité est liée à l’existence de chemins dans un graphe. Elle permet essentiellement de
répondre à la problématique suivante : depuis un sommet, existe-t-il un chemin pour atteindre tout
autre sommet ? Elle permet entre autre de déterminer les éléments du graphe (sommet et/ou arc)
ayant une importance particulière selon le contexte. La notion de connexité est importante dans
plusieurs domaines tels que les réseaux (conception de réseaux fiables et résistants aux pannes), en
topologie (pour repérer les espaces connexes ou non connexes), en sociologie (pour étudier
l’interaction entre les individus)…

4.1. Transitivité
• Graphe transitif : Un graphe transitif est un graphe tel que pour tout couple de sommets |
reliés par un chemin de longueur 2, sont aussi reliés par un arc ; i.e., ( , ) est transitif si :
et

∀ _} , _~ , _• ∈ L , €} U_} , _~ V ∈ • ‚ƒ U_~ , _• V ∈ • „…†‡€ (_} , _• ) ∈ •

xi xj
Exemple 13 :
⬚
← x\ ℎ x\ )u u{

xℓ xk
9
Théorie des Graphes - THG
Notation :
" # #
Notons par (ensemble de successeurs) et (ensemble de prédécesseurs). On a :

, ,…, )= ( )∪ ( )∪ …∪ ( )= / ( )
Š

# ( , ,…, )= # ( )∪ # ( )∪…∪ # ( )= / # ( )
Š
• Fermeture transitive d’un sommet
Soit ( , ) un graphe, on définit sur les applications , %
,…, ,… telles que ∀ ∈ :
( )= U ( )V , %( )= U ( )V = ‹ U ( )VŒ , … ^.
( ) : représente l’ensemble des sommets qui peuvent être atteints à partir de
longueur ≤ à .
par un chemin de

On appelle fermeture transitive d’un sommet l’application multivoque • définie par :

•( ) = { } ∪ ( ) ∪ ( ) ∪ …∪ ( )…
• ( ) représente l’ensemble des sommets que l’on peut atteindre à partir de par un chemin de
longueur quelconque.

, #% , … , # ,… telles que ∀ ∈ :
On peut aussi définir de manière similaire les applications multivoques inverses (ou réciproques)
#

# ( )= #
U # ( )V , #% ( )= #
U # ( )V = #
‹ #
U # ( )VŒ , … ^.
# ( ) : représente l’ensemble des sommets à partir desquels on peut atteindre
longueur ≤ à .
par un chemin de

La fermeture transitive inverse d’un sommet est l’application multivoque inverse • # définie par :
•# ( ) = { } ∪ # ( ) ∪ # ( ) ∪ … ∪ # ( ) …
• # ( ) représente l’ensemble des sommets à partir desquels on peut atteindre par un chemin de
longueur quelconque. C B
Exemple 14 : A

E G

D
F

(N) = {., •} (N) = U (N)V = (., •) = (.) ∪ (•) = {‘} ∪ {., ‘} = {., ‘}
% (N)
= U ( )V = (., ‘) = {‘} ∪ {’, •} = {‘, ’, •} …
• (N) = {N} ∪ (N) ∪ (N) ∪ … ∪ (N) … = {N, ., ‘, ’, •} ∪ … ∪ (N) …
Et
# (N) = {’} # (N) = #
U # (N)V = # (’) = {‘}
#% (N) ( )V = (‘) = {., •} …
= #
U # #

• # (N) = {N} ∪ # (N) ∪ # (N) ∪ … ∪ # (N) … = {N, ., ‘, ’, •} ∪ … ∪ # (N) …

10
Théorie des Graphes - THG
• Fermeture transitive stricte d’un graphe
On appelle fermeture transitive stricte d’un graphe , ) la correspondance telle que :

∀ ∈ → •( ) = { } ∪ ( ) ∪ ( ) ∪ …∪ ( )…

• Algorithme de recherche de la fermeture transitive stricte d’un graphe “(L, ”)

Cet algorithme permet d’obtenir • ( , • ) connaissant ( , ). On pose = { , , … , } l’ensemble
des sommets du graphe , ( ) l’ensemble des successeurs du sommet et # ( ) l’ensemble des
prédécesseurs de .

• est une application qui consiste à enrichir

Principe

#
( ) à chaque élément (ou sommet) de ( ).
en joignant par un arc (lorsqu’il n’existe pas) chaque
élément (sommet) de

∈ #
( ) | ∈ ( )

• consiste à reproduire tous les "1" existants en ligne "u" sur toute ligne "–" possédant un "1" en
Si on considère un graphe représenté par une matrice booléenne (incidence sommet-sommet),

u –
colonne "u".
1 2 3 4 … … …
1
2
3
…
u 1 0 0 1 … 1 0 …

… ↓ ↓ ↓
– 1 1 1 1 … …

Application de l’algorithme
Etant donné un graphe :

1. Numéroter ses sommets dans un ordre arbitraire.

3. Appliquer • (1ère ligne de la matrice), puis • (2ème ligne de la matrice) au résultat obtenu,
2. Déterminer la matrice booléenne correspondante au graphe.

ensuite •% (3ème ligne), … et enfin • (dernière ligne).

Le résultat obtenu (final) est la fermeture transitive stricte du graphe initial .

Un "1" dans la case ( , ) de la matrice finale signifie qu’il existe un chemin de

Important :
vers dans .

11
Théorie des Graphes - THG
Exemple 15 :
Après avoir appliqué l’algorithme au graphe suivant, on détermine sa fermeture transitive stricte :

A B C D
B
A
A 1 1 1 1

C B 1 1 1 1

C 1 1 1 1
D
D 0 0 0 0

case(A , B) = 1 ⇒ Il existe un chemin de A à B

case(D , B) = 0 ⇒ Il n’existe pas de chemin de D à B

4.2. Connexité

• Graphe connexe (ou simplement connexe)

Un graphe connexe est un graphe tel qu’à partir de tout sommet on peut atteindre tout autre
sommet en passant par une chaine du graphe.

E
Exemple 16 : b
a

& %
e c

'
d
G1 est un graphe connexe G2 est un graphe non connexe
(2 composantes connexes)

• Composante connexe d’un graphe

Soit un sommet donné et ‘01 l’ensemble des sommets pouvant être reliés à par une chaine y

ensemble de la forme ‘01 .

compris aussi ; on appelle composante connexe du graphe, le sous-graphe engendré par un

, , % ) et ( , , E ) sont les 2 composantes connexes de 2.

Exemple 17 : (Graphe 2, Exemple 16)
Les deux sous graphes formés par & '

Les différentes composantes connexes du graphe ( , ) constituent une partition de classes de X ;

c'est-à-dire )u ∈ ; 1. ‘01 ≠ ∅, 2. ‘01 ≠ ‘0— ⇒ ‘01 ∩ ‘0— = ∅, 3. ∪ ‘01 =
b c
• Graphe fortement connexe
Un graphe ( , ) est fortement connexe si et
seulement si : ∀ ∈ , • ( ) = .Autrement dit,
a
de tout sommet on peut atteindre tout autre
sommet en suivant un chemin du graphe,
comme c’est le cas du graphe suivant :
d
e
12
Théorie des Graphes - THG
Remarque :
- Graphe fortement connexe ⇒ graphe connexe (et non l’inverse).
- Graphe connexe et symétrique ⇒ graphe fortement connexe.

• Composante fortement connexe

On considère un graphe , ) et la relation d’équivalence ˜ définie par :

=
∀ , ∈ ˜ ⇔š *
›v u) ^ℎ +u A œ x) xé^u x*• +

- Chaque classe d’équivalence ‘ est un sous graphe appelé composante fortement connexe.

Remarque :
- Les composantes fortement connexes constituent une partition de l’ensemble .
- Un graphe fortement connexe n’a qu’une seule composante fortement connexe.

Soit ‘01 une classe d’équivalence, alors ‘01 = • ( ) ∩ • # ( ) puisqu’il doit exister un chemin de vers
• Algorithme de Malgrange : décomposition d’un graphe en composantes fortement connexes

les autres sommets de la classe et inversement ; c'est-à-dire ∀ ∈ :

∈ ‘01 ⇔ ∃ ^ℎ +u A œ x) u œ x) +

- L’algorithme consiste à sélectionner arbitrairement un sommet et à calculer • ( ) puis • # ( ) et

Principe de définition

enfin • ( ) ∩ • # ( ) : ceci nous donne un sous-graphe fortement connexe contenant .

- On supprime alors les sommets du sous-graphe obtenu et on recommence avec un autre sommet.

correspondant à • et une ligne correspondant à • # d’un sommet considéré.

- Pratiquement, on part de la matrice booléenne représentant le graphe et on lui ajoute une colonne

Principe d’application

A B C D E F G H I J K • (N)
A 1 1 1 0
B 1 1 1 1 ×
C 1 ×
D 1 1
E 1 ×
F 1 1 1
G 1 1 2
H 1 1 1 ×
I 1 1
J 1 1 ×
K 1 3

• # (N) 0 × 2 × × 1 × × × × ×

13
Théorie des Graphes - THG
- On choisit un sommet quelconque. Prenons par exemple le sommet N, pour remplir • N , placer 0
dans la case N de • N . La ligne N porte un 1 en colonne D, on placera donc un 1 dans la case D de
• N . De même, on placera 1 dans les cases Ÿ et › de • N (ainsi le plus court chemin de N à ’, Ÿ, ›
est de longueur 1).

- On considère ensuite les lignes ’, Ÿ, ›, on placera 2 dans les cases de • N correspondantes aux

seulement un 2 pour la case , car les autres (N et ’) sont déjà remplies.

colonnes portant des 1, dans le cas où ces cases ne sont pas encore remplies. Dans notre exemple,

porte alors 3 dans de • N .

- On considère alors la ligne , elle contient 1 en colonne (déjà remplie) et 1 en colonne ; on

qui contient 1 en colonne › (déjà remplie) on voit qu’on ne peut plus

appliquer la procédure, ainsi pour terminer on met une croix dans les cases restantes vides de • N
- On examine la ligne

(il n’y a pas de chemin entre N et ces sommets).

- Pour remplir la ligne • # N , on opère de la même manière, mais en remplaçant les lignes par les
colonnes. On trouve pour N :

• N N, ’, Ÿ, , ›, }
¡ ⇒ • N ∩ • # (N) = {N , Ÿ}
• # (N) = {N , ‘ , Ÿ}

{N , Ÿ} est la première composante (1er sous graphe) fortement connexe (maximal).

- On enlève les sommets du sous graphe obtenu, puis on choisit un sommet arbitraire parmi les
sommets restants et on applique à nouveau la procédure.
A la fin, on arrive à décomposer le graphe en 7 classes d’équivalence correspondant chacune à une
composante fortement connexe maximale.
‘ = {N, Ÿ} , ‘ = {., ¢} , ‘% = { , ›, } , ‘& = {£} , ‘' = {‘} , ‘E = {’} , ‘D = {•}

Graphe réduit

¤ (‘¥ , ¤ ) est appelégraphe réduit de ( , ) s’il est défini par :

‘¥ : ensemble de composantes fortement connexe.
∈‘
(‘ , ‘ ) ∈ ¤ s’il existe 3 ∈ ‘ ¦ v • U , V ∈

Pour notre d’exemple d’application, on obtient le graphe réduit suivant qui permet de "résumer" le
graphe initial, d’analyser ses "points faibles" et de déterminer quel est le minimum d’arcs à ajouter
pour rendre le graphe fortement connexe.

‘'
‘
‘%
‘
N, Ÿ ’ , ›,
‘E

‘
., ¢
£ ‘D
‘& •

14
Théorie des Graphes - THG

5. GRAPHES EXPANSEURS
La notion de graphe expanseur a été introduite dans le but de résoudre des problèmes liés aux réseaux
et aux télécommunications. Cette propriété traduit qu’un graphe soit hautement connecté dans le sens
où, à partir d'un petit nombre de sommets (correspondant par exemple à des relais de transmission)
on peut atteindre en un « pas » d'autres sommets du graphe (par exemple des récepteurs) par de
nombreuses voies.

Soit A un sous-ensemble de sommets, on appelle frontière de A noté § N , l’ensemble des arêtes

5.1. Frontière d’une partie du graphe

partant d’un sommet de A et n’aboutissant pas à un sommet de A :

§ N , ∈ ∶ ∈N ∈ /N

Les sommets coloriés en bleu ont pour frontière l’ensemble des arêtes vertes

Le taux d’expansion ‰ est le minimum, pris sur des sous-ensembles N comportant au maximum /2
5.2. Taux d’expansion

sommets, du rapport entre le nombre d’arêtes de la frontière de N et le nombre de sommets de N ;

|§ N |
‰ min
|©|ª / |N|

Le taux d’expansion est aussi appelé nombre isopérimétrique ou constante de Cheeger.

Pour un ^ strictement positif, Le graphe G est c-expanseur si le taux d’expansion ‰ « ^. Le graphe de

5.3. Graphe expanseur

Petersen (graphe ci-dessous) est un graphe expanseur de taux 1. Pour s'en persuader, il suffit de
considérer les 5 sommets de l'étoile centrale : il n'y a que 5 arêtes qui s'en échappent, ce qui
correspond à un rapport arêtes de la frontière divisé par le nombre de sommets égal à 1.

15