Théorie des Graphes - THG

CHAPITRE 2 : ARBRES ET ARBORESCENCES

Plan
1. Nombre cyclomatique et nombre cocyclomatique
2. Arbres
3. Arborescences
4. Fonction ordinale

Les arbres et les arborescences sont des structures fondamentales utilisées dans de très nombreux
domaines : informatique, science sociale, statistique, intelligence artificielle,…

Etant donné un graphe avec sommets, + arcs et composantes connexes :

1. NOMBRE CYCLOMATIQUE ET NOMBRE COCYCLOMATIQUE

- La dimension de la base des cycles (cycles indépendants) est ® +[ C ; ®( ) est

- La dimension de la base des cocycles (cocycles indépendants) est -( ) = − ; -( ) est

appelé le "nombre cyclomatique" du graphe.

appelé le "nombre cocyclomatique" du graphe.

Du fait que le nombre de chemins, cycles et cocycles existants dans un graphe peut être très grand, les
nombres cyclomatique et cocyclomatique permettent de mesurer le nombre de cycles et cocycles
indépendants dans un graphe donné.
1 b c
Exemple 1 :
3 f
a
2
4 6
5 7

=6 +=7 =2
e
d

®( ) = + − + =3
-( ) = − =4
donc il existe 3 cycles élémentaires indépendants.
donc il existe 4 cocycles élémentaires indépendants.

2. ARBRES

2.1. Définitions
- Un arbre est un graphe connexe sans cycle et ayant au moins deux sommets (il peut avoir des arcs
ou des arêtes).
&
Exemple 2 : '

% E
D

¼
½
¾

- Une forêt est un graphe non connexe et sans cycle ; c’est aussi un ensemble d’arbres.

- Une forêt est un graphe dont chaque composante connexe est un arbre.

18
Théorie des Graphes - THG

]
Exemple 3 :

^
\
1er Arbre

u
Forêt

ℎ
¿
{ À v
2èmeArbre

– +

• Soit £ un graphe ayant sommets ( « 2), l’une des propriétés suivantes est suffisante pour
2.2. Propriétés

a. £ est connexe et sans cycle.

définir un arbre :

b. £ est sans cycle et possède ( − 1) arêtes (ou arcs).

c. £ est connexe et possède ( − 1) arêtes.
d. £ est sans cycle et en ajoutant une arête entre deux sommets non adjacents on crée un cycle et

e. £ est connexe et en supprimant une arête quelconque, il n’est plus connexe.

un seul.

f. Tout couple de sommets est relié par une chaine et une seule.

• Un graphe connexe de sommets, possède au moins ( − 1) arêtes (ou arcs).

Remarque :

• Un graphe sans cycle de sommets, possède au plus ( −1) arêtes (ou arcs).
• Dans un graphe sans cycle qui a sommets, + arêtes, composantes connexes, on a + = − .
• Un arbre d’ordre ( ≥ 2) possède au moins 2 sommets pendants (Un sommet pendant est un
sommet qui n’est adjacent qu’a un seul sommet).
• Un graphe quelconque admet un graphe partiel qui est un arbre si et seulement si est connexe.
Un tel arbre est appelé "arbre partiel".

2.3. Algorithme de détermination d’un arbre partiel d’un graphe connexe

a. Chercher une arête (ou un arc) dont la suppression "ne déconnecte pas" le graphe.
b. Si une telle arête existe, la supprimer du graphe puis reprendre en a.
Sinon le graphe est un arbre partiel.
La procédure s’arrête une fois qu’il n’y a plus d’arêtes à supprimer.

] ^
Exemple 4 :

\ À A
Les arêtes en gras forment l’arbre
partiel, les autres ont été éliminées.

{
19
Théorie des Graphes - THG

, ), à chaque arête (ou arc) appartenant à , on lui associe un nombre ^( ) appelé

2.4. Algorithmes de recherche d’un arbre partiel de valeur minimale

"cout" ou "valeur" ou "poids" de l’arête ; on appelle valeur totale d’un arbre partiel £( , Á) la
Soit un graphe

somme :
Â(£) = Ã ^( )
Ä∈Å
Le problème est de chercher un arbre partiel £ de tel que sa valeur totale soit minimale. Le
minimum est pris sur l’ensemble des arbres possibles de . Si toutes les arêtes ont des couts différents,
l’arbre partiel minimal est unique.

électriques. On considère un ensemble de Æ sites devant être reliés par des lignes à haute tension.
Ce problème a plusieurs applications. Nous citons à titre d’exemple la construction de lignes

peut modéliser l’ensemble des réseaux possibles par un graphe complet et valué = ( , , ‘) dans
L’objectif est de construire un réseau connectant tous les sites et ayant une longueur minimale. On

lequel est l’ensemble des sites, l’ensemble de toutes les connections possibles et ‘ une application
qui associe à toute arête (u, ¿) un coût (la distance entre u et ¿). La résolution de ce problème (réseau
optimal) revient à trouver l’arbre partiel (recouvrant) de poids minimal.
Algorithme de Kruskal
1. Ordonner les arêtes par ordre croissant sur le coût.
2. Choisir la 1ère arête qui a le cout minimum

4. A une étape – (2 < – ≤ − 1) choisir l’arête | de cout minimum et qui ne forme pas de cycles
3. Choisir la 2ème arête qui a le cout minimum parmi les arêtes restantes.

avec les (– − 1) arêtes déjà choisies.

5. Arrêter la procédure lorsque – = − 1. Ainsi le graphe £( , Á) est un arbre partiel de valeur
totale minimale.

Exemple 5 : 23

12 F 14 % & ' E

10 15
- 23 12 8 6 10
F F
- 15 24 19 14
F F
%
20
- 22 17 20

E % & - 5 13
F
13 19 17 '
24
- 7
E
6
-
7 8
F
F 22
F
F F F
5
' &

= 6 )*++ ) –= − 1 = 5 ; on s’arrête à – = 5.
F
Nous avons
Cout Arête Forme-t-elle un cycle Cout Nombre cumulé

o_c , _È p
arête concernée avec les autres arêtes ? de l’arête choisie d’arêtes choisies

o_a , _È p
5 NON 5 1

o_È , _É p
6 NON 6 2

o , &p
7 NON 7 3

o , Ep
8 OUI - -

o_a , _` p
10 OUI - -

o &, Ep
12 NON 12 4

o_b , _É p
13 OUI - -
14 NON 14 5
Le cout total de l’arbre partiel obtenu est : 5 + 6 + 7 + 12 + 14 = 44
20
Théorie des Graphes - THG
Algorithme de Sollin
On procédera par étape en joignant un sommet quelconque à son voisin le plus proche (c'est-à-dire
dont l’arête porte le plus petit cout) et on formera ainsi des sous graphes (c'est-à-dire des sous arbres
du graphe donné), chacun de ces sous-graphes n’ayant aucun sommet en commun avec un autre, puis
on considérera ces sous arbres comme des sommets et on recommencera l’algorithme jusqu’au
moment où on obtiendra un arbre du graphe donné.

Exemple 6 : (Voir exemple 5)

Commençons arbitrairement par , son voisin le plus proche est E . On formera le sous graphe E.
, E ), par exemple dont le voisin le plus proche est
, , ' , E , soit & dont le voisin le plus proche est ' .
Prenons ensuite un autre sommet (autre que
' . Prenons un autre sommet en dehors de
Prenons le dernier sommet % , son sommet le plus proche est . Nous avons ainsi obtenu 2 sous
arbres N1 et N2.

&

N
N 14
5 6
12
F F F
F
E %
'

Cherchons maintenant quelle est l’arête la plus courte entre N1 et N2. C’est o ', E p qui vaut 7. Ainsi on
obtient l’arbre optimal suivant de cout 44.

&

14 12
5 6
F F
7
F F
E %
F '

A partir de la matrice booléenne associée au graphe, construire la matrice . telle que :

2.5. Détermination du nombre d’arbres partiels d’un graphe connexe

u = ¿ \v*x) ] = A Àxé A )*++ u

Î
)u (u,
Íu ≠ ¿ \v*x) t] = −1 )u v \x^ ¿) ∈
w

Ì ] = 0 )u v \x^(u, ¿)∉
w

matrice . (Mineur = déterminant de la matrice)

Le nombre d’arbres partiels et égal au mineur de n’importe quel terme de la diagonale principale de la

\
Exemple 7 :
A B
\ ] ^ A \ ] ^ A
\ \
A
] ]
1 1 1 3 -1 -1 -1
]
^ ^
1 1 -1 2 -1 0

A A
1 1 1 -1 -1 3 -1

^
1 1 -1 0 -1 2
21
Théorie des Graphes - THG

3 −1 −1 −1
2Ï Ï+1 Ï Ï = 2 × 5 + (−2) = 8 arbres partiels
−1 2 0 2
Le déterminant (mineur (B))

Le nombre d’arêtes de chaque arbre partiel est − 1 (c'est-à-dire 3 arêtes), ainsi il faut enlever de

\ \ \
chaque combinaison deux arêtes.
\

A ] A ] A ] A ]

^ ^ ^ ^
\ \ \ \

A ] A ] A ] A ]

^ ^ ^ ^

3. ARBORESCENCE

3.1. Définitions

Dans un graphe ( , ), on appelle racine un sommet

• Racine
tel que tout autre sommet du graphe peut être
atteint par un chemin issu de .
A
] ℎ
Exemple 8 :

‡„Ð}Ñ‚ ∶ „
^
\ À

- Un graphe est dit quasi-fortement connexe, si pour tout couple de sommets ( ,

• Graphe quasi-fortement connexe

un sommet ³ d’où partent à la fois un chemin allant en et un chemin allant en .

), il existe

- Un graphe fortement connexe est donc quasi-fortement connexe,

mais la réciproque est fausse.

Soit ( , ) un graphe orienté :

• Arborescence

est une arborescence de racine ¾ ∈ si :

a. ¾ est unique et n’est l’extrémité finale d’aucun arc (u. . # ( ¾ ) = ∅).
b. ∀ , ≠ ¾ , est l’extrémité finale d’un seul arc (u. . | # ( )| = 1).
c. ne contient pas de circuit.

Toute arborescence est un arbre muni d’une racine ¾ et ∀ ∈ , ∃ un chemin allant de ¾ à .

22
Théorie des Graphes - THG

Exemple 9 :
%

& ' E
' E
¼
D
¾
% D
¼

½ ¾
&
¾

Nx]*x )^ ^ 1 Nx]*x )^ ^ 2

, ) admet une racine est qu’il soit quasi-

Remarque :
La condition nécessaire et suffisante pour qu’un graphe
fortement connexe.

Soit N un graphe d’ordre > 1, les propriétés suivantes sont équivalentes pour définir une
3.2. Propriétés

a. N est quasi-fortement connexe et sans cycles

arborescence.

b. N est fortement connexe et admet ( − 1) arcs

c. N est un arbre admettant une racine ¾
d. Il existe un sommet ¾ qui est relié à tout autre sommet par un chemin unique issu de ¾
e. N est quasi-fortement connexe et cette propriété disparait par suppression d’un arc

f. N est connexe et il existe un sommet ¾ tel que : A©# ( ¾ ) = 0 et A©# ( ) = 1 ∀ ≠ ¾

quelconque

g. N est sans cycle et l’on a : A©# ( ¾ ) = 0 et A©# ( ) = 1 ∀ ≠ ¾

4. FONCTION ORDINALE

Soit ( , ) un graphe sans circuit, on définit les sous-ensembles ƾ , Æ , Æ , … , Ƥ tels que :

4.1. Définition

ƾ = { / #
( )=∅}
Æ ={ / # ( )⊂ƾ }
Æ ={ / # ( )⊂ƾ ∪ Æ }

¤#
…

Ƥ = š / # ( )⊂ / Æ| Ó
|Š¾

Avec x est le plus petit entier tel que ( ) = ∅ (ou (Ƥ ) = ∅)

Les sous-ensembles Æ| forment une partition de et sont appelés "Niveaux".
La fonction ordinale •( ) du graphe sans circuit est défini par ∈ Æ| ⇒ • –

a. Représenter la matrice booléenne du graphe ; poser – 0

4.2. Méthode de détermination de la fonction ordinale d’un graphe sans cycle

b. Ajouter une ligne totale N| en bas de la matrice et y mettre des croix dans les cases des

c. Faire la somme par colonne et reporter le total dans la case correspondante de N| .

colonnes dont les lignes correspondantes ont été supprimées.

23
Théorie des Graphes - THG
d. Les sommets ayant leur total nul constituent le niveau Æ| , supprimer alors les lignes portant

e. Incrémenter – (– = – + 1) et aller à b.
ces sommets.

f. S’arrêter une fois que la ligne N| contient seulement des croix.

Exemple 10 :
A B C D E F G H I J K
A 1 1 1
B 1 1 1
C 1 1
D 1 1
E
F
G 1 1
H
I
J 1 1
K 1 1 1

N¾ 0 0 1 2 2 3 2 1 3 1 1 ƾ = {N, .}

N X X 0 0 2 2 1 2 3 1 0 Æ = {‘, ’, }

N X X X X 1 0 0 1 2 0 X Æ = {Ÿ, , ¢}

N% X X X X 0 X X 0 0 X X Æ% = {•, £, ›}

N& X X X X X X X X X X X

Ÿ •
‘

’ £
.

¢ ›

N0 N1 N2 N3

24
Théorie des Graphes - THG
Exemple 11 : (Contre-Exemple : Graphe avec cycle)

A B C D
A 1 1
B 1
C 1 1
D

N¾ 2 0 2 1 ƾ .

N 2 X 2 0 Æ ’

N 2 X 2 X .v*^\À ∶ xé) ^ A ^ux^ u

Remarque :
- On peut définir la fonction ordinale inverse de la même façon qu’on a défini la fonction
ordinale : seulement tout ce qui a été fait pour les lignes, sera fait pour les colonnes et
inversement.
- Une arborescence a toujours une fonction ordinale.

25